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 $GF(81)$ and an edge for every two elements that differ by a fourth power.Template:R

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.Template:R 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.Template:R

As well as being strongly regular it is a distance-transitive graph.Template:R

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,Template:R 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.Template:R

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.Template:R With the $3\times 3$ Rook's graph and the Games graph, it is one of only three possible strongly regular graphs whose parameters have the form $((n^2+3n-1{)}^2,n^2(n+3),1,n(n+1))$.Template:R

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 $3\times 3$ 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.Template:R In contrast, for the Brouwer–Haemers graph, the largest cliques are the triangles and the number of colors needed is 7.Template:R