Almost all steinhaus graphs have diameter 2
Neal Brand · Journal of Graph Theory · 1992
Abstract A Steinhaus graph is a graph with n vertices whose adjacency matrix (ai, j) satisfies the condition that ai, j aa‐‐1, j‐‐1 + a i‐‐1, j (mod 2) for each 1 < i < j ≤ n. It is clear that a Steinhaus graph is determined by its first row. In [3] Bringham and Dutton conjecture that almost all Steinhaus graphs have diameter 2. That is, as n approaches infinity, the ratio of the number of Steinhaus graphs with n vertices having diameter 2 to the total number of Steinhaus graphs approaches 1. Here we prove Bringham and Dutton's conjecture.