Meringer Graph


The Meringer graph is one of the four (5,5)-cage graphs, discovered by Meringer (1999) after it had long been thought that only three such cages existed. Like the other (5,5)-cages, the Meringer graph has 30 nodes. It has 75 edges, girth 5, diameter 3, chromatic number 3, and is a quintic graph. The order of its automorphism group is 96. It is illustrated above in a number of degree-3 LCF notations, of which at least 108 distinct of which exist.


The plots above show the adjacency, incidence, and distance matrices of the graph.

The graph spectrum of the Meringer graph is (-3)^2(-1-sqrt(3))^4(1/2(-1-sqrt(17)))^3(-2)^30^1(-1+sqrt(3))^4(1/2(-1+sqrt(17)))^32^95^1.

See also

Cage Graph, Foster Cage, Robertson-Wegner Graph, Wong Graph

Explore with Wolfram|Alpha


Meringer, M. "Fast Generation of Regular Graphs and Construction of Cages." J. Graph Th. 30, 137-146, 1999.Pisanski, T. and Randić, M. "Bridges between Geometry and Graph Theory." In Geometry at Work: A Collection of Papers Showing Applications of Geometry (Ed. C. A. Gorini). Washington, DC: Math. Assoc. Amer., pp. 174-194, 2000.

Cite this as:

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

Subject classifications