Probability of diameter two for Steinhaus graphs

DOI10.1016/0166-218X(93)90036-NMaRDI QIDQ1208476zbMATH OpenOpenAlexFDO

Authors Neal Brand, Stephen J. Curran, Sajal K. Das, Tom Jacob

Publication date 16 May 1993

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(93)90036-n

zbMATH Keywords

adjacency matrixdiameterrandom graphSteinhaus graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80)

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.

Recommendations

• On the diameter of a class of random graphs
• Diameter of P.A. random graphs with edge-step functions
• Diameters of random bipartite graphs
• Two probabilistic results on rectilinear Steiner trees
• Diameters of random circulant graphs
• scientific article; zbMATH DE number 4055665
• scientific article; zbMATH DE number 975321
• The diameter of a random graph with bounded diameter

Cites work

• Almost all steinhaus graphs have diameter 2
• Complements of Steinhaus graphs
• scientific article; zbMATH DE number 3638844 (Why is no real title available?)
• scientific article; zbMATH DE number 975321 (Why is no real title available?)

Cited in

(5)

• Characterizations of bipartite Steinhaus graphs
• The diameters of almost all Cayley digraphs
• Almost all steinhaus graphs have diameter 2
• Properties of Classes of Random Graphs
• scientific article; zbMATH DE number 975321 (Why is no real title available?)

This page was built for publication: Probability of diameter two for Steinhaus graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1208476)