TOPICS
Search

Meringer Graph


MeringerGraph

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 is illustrated above in one of its 108 degree-3 LCF notations, none of which are bilaterally symmetric.

The Meringer graph has 75 edges, girth 5, diameter 3, chromatic number 3, and is a quintic graph. The order of its automorphism group is 96. 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.

MeringerGraphMatrices

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

MeringerGraphAlmostUnitDistanceEmbeddings

The Meringer graph satisfies the rhombus constraints and contains no known unit-distance forbidden subgraph, yet appears not to be a unit-distance. A number of embeddings found from different initial embeddings by minimizing the sum of square deviations from unit edge lengths until a local minimum was reached are illustrated above.


See also

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

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

References

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.

Referenced on Wolfram|Alpha

Meringer Graph

Cite this as:

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

Subject classifications