TOPICS
Search

Zara Graph


The Zara graph is the unique graph on 126 vertices satisfying the properties that 1) every maximal clique (of which there are a total of 567) has six vertices, and 2) that if C is a maximal clique and v is a vertex outside of C, then v has exactly two neighbors in C (Blokhuis and Brouwer 1984).

The graph is strongly regular with parameters (126,45,12,18), though it is not the unique graph having such parameters. It is also both distance-regular with intersection array {45,32;1,18} and distance-transitive.

It has graph spectrum (-9)^(35)3^(90)45^1 and is therefore an integral graph. It has graph automorphism group order Aut(G)=13063680.

It is a Hamiltonian graph.

The Zara graph is implemented in the Wolfram Language as GraphData["ZaraGraph"].


See also

Distance-Regular Graph, Distance-Transitive Graph, Strongly Regular Graph

Explore with Wolfram|Alpha

References

Blokhuis, A. and Brouwer, A. E. "Uniqueness of a Zara Graph on 126 Points and Non-Existence of a Completely Regular Two-Graph on 288 Points." In Papers dedicated to J. J. Seidel (Ed. P. J. de Doelder, J. de Graaf, and J. H. van Lint). EUT Report 84-WSK-03. Eindhoven, Netherlands: Technische Hogeschool Eindhoven, pp. 6-19, 1984.DistanceRegular.org. "Zara Graph on 126 Vertices." http://www.distanceregular.org/graphs/zara126.html.Zara, F. "Graphes Lies aux Espaces Polaires." Europ. J. Combin. 5, 255-290, 1984.

Cite this as:

Weisstein, Eric W. "Zara Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ZaraGraph.html

Subject classifications