Almost all steinhaus graphs have diameter 2

✍ Scribed by Neal Brand

• Publisher: John Wiley and Sons
• Year: 1992
• Tongue: English
• Weight: 300 KB
• Volume: 16
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190160304

✦ Synopsis

Abstract

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.