Probability of diameter two for Steinhaus graphs
type: Item
instance of: scholarly article
title: Probability of diameter two for Steinhaus graphs
zbMATH Open document ID: 0795.05125
DOI: 10.1016/0166-218X(93)90036-N
author: Neal Brand
author: Stephen J. Curran
author: Sajal K. Das
author: Tom Jacob
published in: Discrete Applied Mathematics
publication date: 1993-05-16T00:00:00Z
review text: A Steinhaus graph with adjacency matrix \((a_{ij})_{i,j=1, \dots, n}\) is defined inductively by taking \(a_{ij}\) as independent Bernoulli \((p_ j)\) for \(j=2, \dots, n\) and \(a_{ij} = a_{i-1,j-1} + a_{i- 1,j} \pmod 2\) for \(j=i+1,\dots,n\) and \(i=2,\dots,n-1\). It is shown under some conditions on the \(p_ j\) that the diameter of the graph is 2 with a probability tending to 1 as \(n\) tends to infinity.
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 166471
zbMATH Keywords: random graph
zbMATH Keywords: Steinhaus graph
zbMATH Keywords: adjacency matrix
zbMATH Keywords: diameter
MaRDI profile type: Publication
cites work: Q4197800
cites work: Almost all steinhaus graphs have diameter 2
cites work: Q5283983
cites work: Complements of Steinhaus graphs
full work available at URL: 0166-218x(93)90036-n
OpenAlex ID: W2093304883
Recommended article: On the diameter of a class of random graphs
Recommended article: Diameter of P.A. random graphs with edge‐step functions
Recommended article: Diameters of random bipartite graphs
Recommended article: Two probabilistic results on rectilinear Steiner trees
Recommended article: Diameters of random circulant graphs
Recommended article: Q3791189
Recommended article: Q5283983
Recommended article: The diameter of a random graph with bounded diameter
description: scientific article; zbMATH DE number 166471