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

The Meringer graph is implemented in the Wolfram Language as GraphData["MeringerGraph"].

The Meringer graph has 75 edges, girth 5, graph diameter 3, chromatic number 3, and is a quintic graph. The group 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 matrix, incidence matrix, and graph distance matrix of the graph.

MeringerGraphAlmostUnitDistanceEmbeddings

The Meringer graph satisfies the rhombus constraints and contains no known forbidden subgraph for unit-distance embeddings, yet appears not to be a unit-distance graph. A number of drawings found from different initial drawings by minimizing the sum of squared 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

References

House of Graphs. "Meringer Graph." https://houseofgraphs.org/graphs/1227.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