Английская Википедия: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 <math>GF(81)</math> and an edge for every two elements that differ by a fourth power.Шаблон: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.Шаблон: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.Шаблон:R
As well as being strongly regular it is a distance-transitive graph.Шаблон: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,Шаблон: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.Шаблон: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.Шаблон:R With the <math>3\times 3</math> Rook's graph and the Games graph, it is one of only three possible strongly regular graphs whose parameters have the form <math>\bigl((n^2+3n-1)^2,n^2(n+3),1,n(n+1)\bigr)</math>.Шаблон: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 <math>3\times 3</math> 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 In contrast, for the Brouwer–Haemers graph, the largest cliques are the triangles and the number of colors needed is 7.Шаблон:R
References
