Brouwer–Haemers graph

Brouwer–Haemers graph
Vertices81
Edges810
Radius2
Diameter2
Girth3
Automorphisms233,280
Chromatic number7
Properties
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

[edit]

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 and an edge for every two elements that differ by a fourth power.[1][2]

Properties

[edit]

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

[edit]

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]

[edit]

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 Rook's graph and the Games graph, it is one of only three possible strongly regular graphs whose parameters have the form .[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 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

[edit]
  1. ^ a b Brouwer, Andries, "Brouwer–Haemers graph", Descriptions of various graphs, retrieved 2019-02-11
  2. ^ a b Podestá, Ricardo A.; Videla, Denis E. (2018), The spectra of generalized Paley graphs and applications, arXiv:1812.03332
  3. ^ a b 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. ^ a b Weisstein, Eric W. "Brouwer–Haemers Graph". MathWorld.
  6. ^ Bondarenko, Andriy V.; Radchenko, Danylo V. (2013), "On a family of strongly regular graphs with ", 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