Premium
Almost all steinhaus graphs have diameter 2
Author(s) -
Brand Neal
Publication year - 1992
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190160304
Subject(s) - combinatorics , mathematics , conjecture , adjacency matrix , graph , discrete mathematics
A Steinhaus graph is a graph with n vertices whose adjacency matrix ( a i, j ) satisfies the condition that a i, j a a‐‐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.