Brouwer-Haemers Graph


The Brouwer-Haemers graph is the unique strongly regular graph on 81 vertices with parameters nu=81, k=20, lambda=1, mu=6 (Brouwer and Haemers 1992, Brouwer). It is also distance-regular with intersection array {20,18;1,6}, as well as distance-transitive.

This graph can be constructed with vertices corresponding to polynomials in the finite field GF(81) where two points are adjacent when their difference is a fourth power (Brouwer), making it a quartic analog of the cyclotomic graphs and Paley graphs.

It is also the local graph of the generalized quadrangle GQ(3,9), i.e., the vertex-induced subgraph on GQ(3,9) by the neighbors of any single vertex.

It has graph spectrum (-7)^(20)2^(60)20^1 and is therefore an integral graph. It has graph automorphism group order Aut(G)=233280 and chromatic number 7.

The Brouwer-Haemers graph is implemented in the Wolfram Language as GraphData["BrouwerHaemersGraph"].

See also

Cyclotomic Graph, Generalized Quadrangle, Paley Graph, Strongly Regular Graph

Explore with Wolfram|Alpha


Brouwer, A. E. "Brouwer-Haemers Graph.", A. E. and Haemers, W. H. "Structure and Uniqueness of the (81,20,1,6) Strongly Regular Graph." Discr. Math. 106/107, 77-82, "Brouwer-Haemers Graph." Dam, E. R. and Haemers, W. H. "Which Graphs Are Determined by Their Spectrum?" Lin. Algebra Appl. 373, 139-162, 2003.

Cite this as:

Weisstein, Eric W. "Brouwer-Haemers Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications