Brouwer–Haemers graph

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.

Brouwer–Haemers graph
Vertices81
Edges810
Radius2
Diameter2
Girth3
Automorphisms233,280
Chromatic number7
Properties
Table of graphs and parameters

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 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 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]

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
  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 ", Journal of Combinatorial Theory, Series B, 103 (4): 521–531, arXiv:1201.0383, doi:10.1016/j.jctb.2013.05.005, MR 3071380
  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, 4194, Springer, pp. 155–165, doi:10.1007/11870814_13
  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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.