Brouwer–Haemers graph

Brouwer–Haemers graph
Vertices	81
Edges	810
Radius	2
Diameter	2
Girth	3
Automorphisms	233,280
Chromatic number	7
Properties	strongly regular distance-transitive Ramanujan locally linear
Table of graphs and parameters

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.

Construction

The Brouwer–Haemers graph has several related algebraic constructions. One of the simplest is as a degree-4 generalized Paley graph: it can be defined by making a vertex for each element in the finite field ${\displaystyle GF(81)}$ and an edge for every two elements that differ by a fourth power.[1][2]

Properties

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.[3] 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.[4]

As well as being strongly regular it is a distance-transitive graph.[5]

History

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,[1] 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.[3]

Related graphs

The Brouwer–Haemers graph is the first in an infinite family of Ramanujan graphs defined as generalized Paley graphs over fields of characteristic three.[2] With the ${\displaystyle 3\times 3}$ Rook's graph and the Games graph, it is one of only three possible strongly regular graphs whose parameters have the form ${\displaystyle {\bigl (}(n^{2}+3n-1)^{2},n^{2}(n+3),1,n(n+1){\bigr )}}$.[6]

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 ${\displaystyle 3\times 3}$ block of the puzzle. It has many 9-vertex cliques and requires 9 colors in any graph coloring; a 9-coloring of this graph describes a solved Sudoku puzzle.[7][8] In contrast, for the Brouwer–Haemers graph, the largest cliques are the triangles and the number of colors needed is 7.[5]

References

1. Brouwer, Andries, "Brouwer–Haemers graph", Descriptions of various graphs, retrieved 2019-02-11
2. Podestá, Ricardo A.; Videla, Denis E. (2018), The spectra of generalized Paley graphs and applications, arXiv:1812.03332
3. Brouwer, A. E.; Haemers, W. H. (1992), "Structure and uniqueness of the (81,20,1,6) strongly regular graph", A collection of contributions in honour of Jack van Lint, Discrete Mathematics, 106/107: 77–82, doi:10.1016/0012-365X(92)90532-K, MR 1181899
4. Clark, L. H.; Entringer, R. C.; McCanna, J. E.; Székely, L. A. (1991), "Extremal problems for local properties of graphs" (PDF), The Australasian Journal of Combinatorics, 4: 25–31, MR 1129266
5. Weisstein, Eric W. "Brouwer–Haemers Graph". MathWorld.
6. Bondarenko, Andriy V.; Radchenko, Danylo V. (2013), "On a family of strongly regular graphs with ${\displaystyle \lambda =1}$", Journal of Combinatorial Theory, Series B, 103 (4): 521–531, arXiv:1201.0383, doi:10.1016/j.jctb.2013.05.005, MR 3071380, S2CID 19220680
7. Gago-Vargas, Jesús; Hartillo-Hermoso, Maria Isabel; Martín-Morales, Jorge; Ucha-Enríquez, Jose Maria (2006), "Sudokus and Gröbner bases: Not only a divertimento", in Ganzha, Victor G.; Mayr, Ernst W.; Vorozhtsov, Evgenii V. (eds.), Computer Algebra in Scientific Computing, 9th International Workshop, CASC 2006, Chisinau, Moldova, September 11-15, 2006, Proceedings, Lecture Notes in Computer Science, vol. 4194, Springer, pp. 155–165, doi:10.1007/11870814_13, hdl:11441/23605
8. Herzberg, Agnes M.; Murty, M. Ram (2007), "Sudoku squares and chromatic polynomials" (PDF), Notices of the American Mathematical Society, 54 (6): 708–717, MR 2327972