| Brouwer - Haemers graph | |
| Vertices: | 81 |
| Edges: | 810 |
| Chromatic Number: | 7 |
| Girth: | 3 |
| Radius: | 2 |
| Diameter: | 2 |
| Properties: | |
In the mathematical field of graph theory, the Brouwer - Haemers graph is a 20-regular undirected graph with 81 vertices and 810 edges.It is a strongly regular graph, a distance-transitive graph, and a Ramanujan graph. Although its construction is folklore, it was named after Andries Brouwer and Willem H. Haemers, who proved its uniqueness as a strongly regular graph.
GF(81)
The Brouwer–Haemers graph is the unique strongly regular graph with parameters (81, 20, 1, 6). This means that it has 81 vertices, 20 edges per vertex, 1 triangle per edge, and 6 length-two paths connecting each non-adjacent pair of distinct vertices. As a strongly regular graph with the third parameter equal to 1, the Brouwer–Haemers graph has the property that every edge belongs to a unique triangle; that is, it is locally linear. Finding large dense graphs with this property is one of the formulations of the Ruzsa–Szemerédi problem.
As well as being strongly regular it is a distance-transitive graph.
Although Brouwer writes that this graph's "construction is folklore", and cites as an early reference a 1964 paper on Latin squares by Dale M. Mesner, it is named after Andries Brouwer and Willem H. Haemers, who in 1992 published a proof that it is the only strongly regular graph with the same parameters.
The Brouwer–Haemers graph is the first in an infinite family of Ramanujan graphs defined as generalized Paley graphs over fields of characteristic three. With the
3 x 3
l((n2+3n-1)2,n2(n+3),1,n(n+1)r)
It should be distinguished from the Sudoku graph, a different 20-regular 81-vertex graph. The Sudoku graph is derived from Sudoku puzzles by making a vertex for each square of the puzzle and connecting two squares by an edge when they belong to the same row, column, or
3 x 3