Brouwer–Haemers graph
{{infobox graph
| name = Brouwer–Haemers graph
| image = 200px
| vertices = 81
| edges = 810
| chromatic_number = 7
| girth = 3
| radius = 2
| diameter = 2
| automorphisms = {{formatnum:233280}}
| properties = {{plainlist|1=
}} }}
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 and an edge for every two elements that differ by a fourth power.{{r|b|pv}}
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.{{r|bh}} 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.{{r|cems}}
As well as being strongly regular it is a distance-transitive graph.{{r|mw}}
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,{{r|b}} 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.{{r|bh}}
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.{{r|pv}} With the Rook's graph and the Games graph, it is one of only three possible strongly regular graphs whose parameters have the form .{{r|br}}
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.{{r|ghmu|hm}} In contrast, for the Brouwer–Haemers graph, the largest cliques are the triangles and the number of colors needed is 7.{{r|mw}}
References
{{reflist|refs=
| last = Brouwer | first = Andries | author-link = Andries Brouwer
| accessdate = 2019-02-11
| title = Brouwer–Haemers graph
| work = Descriptions of various graphs
| url = https://www.win.tue.nl/~aeb/graphs/Brouwer-Haemers.html}}
| last1 = Brouwer | first1 = A. E. | author1-link = Andries Brouwer
| last2 = Haemers | first2 = W. H.
| department = A collection of contributions in honour of Jack van Lint
| doi = 10.1016/0012-365X(92)90532-K
| journal = Discrete Mathematics
| mr = 1181899
| pages = 77–82
| title = Structure and uniqueness of the (81,20,1,6) strongly regular graph
| volume = 106/107
| year = 1992| doi-access =
}}
| last1 = Bondarenko | first1 = Andriy V.
| last2 = Radchenko | first2 = Danylo V.
| doi = 10.1016/j.jctb.2013.05.005
| issue = 4
| journal = Journal of Combinatorial Theory
| mr = 3071380
| pages = 521–531
| series = Series B
| title = On a family of strongly regular graphs with
| volume = 103
| year = 2013| arxiv = 1201.0383
| s2cid = 19220680
}}
| last1 = Clark | first1 = L. H.
| last2 = Entringer | first2 = R. C.
| last3 = McCanna | first3 = J. E.
| last4 = Székely | first4 = L. A.
| journal = The Australasian Journal of Combinatorics
| mr = 1129266
| pages = 25–31
| title = Extremal problems for local properties of graphs
| url = https://ajc.maths.uq.edu.au/pdf/4/ocr-ajc-v4-p25.pdf
| volume = 4
| year = 1991}}
| last1 = Gago-Vargas | first1 = Jesús
| last2 = Hartillo-Hermoso | first2 = Maria Isabel
| last3 = Martín-Morales | first3 = Jorge
| last4 = Ucha-Enríquez | first4 = Jose Maria
| editor1-last = Ganzha | editor1-first = Victor G.
| editor2-last = Mayr | editor2-first = Ernst W.
| editor3-last = Vorozhtsov | editor3-first = Evgenii V.
| contribution = Sudokus and Gröbner bases: Not only a divertimento
| doi = 10.1007/11870814_13
| pages = 155–165
| publisher = Springer
| series = Lecture Notes in Computer Science
| title = Computer Algebra in Scientific Computing, 9th International Workshop, CASC 2006, Chisinau, Moldova, September 11-15, 2006, Proceedings
| volume = 4194
| year = 2006| hdl = 11441/23605
| hdl-access = free
}}
| last1 = Herzberg | first1 = Agnes M. | author1-link = Agnes M. Herzberg
| last2 = Murty | first2 = M. Ram | author2-link = M. Ram Murty
| issue = 6
| journal = Notices of the American Mathematical Society
| mr = 2327972
| pages = 708–717
| title = Sudoku squares and chromatic polynomials
| url = https://www.ams.org/notices/200706/tx070600708p.pdf
| volume = 54
| year = 2007}}
{{mathworld|title=Brouwer–Haemers Graph|id=Brouwer-HaemersGraph}}
| last1 = Podestá | first1 = Ricardo A.
| last2 = Videla | first2 = Denis E.
| arxiv = 1812.03332
| title = The spectra of generalized Paley graphs and applications
| year = 2018}}
}}
{{DEFAULTSORT:Brouwer-Haemers Graph}}