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.
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. 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
In combinatorial mathematics and extremal graph theory, the Ruzsa–Szemerédi problem or (6,3)-problem asks for the maximum number of edges in a
graph in which every edge belongs to a unique triangle.
Equivalently it asks for the maximum number ...
.
As well as being strongly regular it is a
distance-transitive graph.
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, 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.
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. With the
Rook's graph and the
Games graph
In graph theory, the Games graph is the largest known locally linear strongly regular graph. Its parameters as a strongly regular graph are (729,112,1,20). This means that it has 729 vertices, and 40824 edges (112 per vertex). Each edge is in a un ...
, it is one of only three possible strongly regular graphs whose parameters have the form
.
It should be distinguished from the
Sudoku graph
In the mathematics of Sudoku, the Sudoku graph is an undirected graph whose vertices represent the cells of a (blank) Sudoku puzzle and whose edges represent pairs of cells that belong to the same row, column, or block of the puzzle. The problem ...
, 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
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
; a 9-coloring of this graph describes a solved Sudoku puzzle. In contrast, for the Brouwer–Haemers graph, the largest cliques are the triangles and the number of colors needed is 7.
References
{{DEFAULTSORT:Brouwer-Haemers Graph
Individual graphs
Strongly regular graphs