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.

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 . 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.
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, it is one of only three possible strongly regular graphs whose parameters have the form.
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. In contrast, for the Brouwer–Haemers graph, the largest cliques are the triangles and the number of colors needed is 7.