Article · Wikipedia archive · Last revised Jul 1, 2026

Meringer graph

In the mathematical field of graph theory, the Meringer graph is a 5-regular undirected graph with 30 vertices and 75 edges named after Markus Meringer.

Last revised
Jul 1, 2026
Read time
≈ 1 min
Length
151 w
Citations
2
Source
Wikipedia ↗
Meringer graph
Named afterMarkus Meringer
Vertices30
Edges75
Radius3
Diameter3
Girth5
Automorphisms96
Chromatic number3
Chromatic index5
PropertiesCage
Table of graphs and parameters

In the mathematical field of graph theory, the Meringer graph is a 5-regular undirected graph with 30 vertices and 75 edges named after Markus Meringer.12

It is one of the four (5,5)-cage graphs, the others being the Foster cage, the Robertson–Wegner graph, and the Wong graph.

It has chromatic number 3, diameter 3, and is 5-vertex-connected.

Algebraic properties

The characteristic polynomial of the Meringer graph is

( x − 5 ) ( x − 2 ) 9 x ( x + 2 ) 3 ( x + 3 ) 2 ( x 2 + x − 4 ) 3 ( x 2 + 2 x − 2 ) 4 . {\displaystyle (x-5)(x-2)^{9}x(x+2)^{3}(x+3)^{2}(x^{2}+x-4)^{3}(x^{2}+2x-2)^{4}.}
References

References

  1. Weisstein, Eric W. "Meringer Graph". MathWorld.
  2. Meringer, Markus (1999), "Fast generation of regular graphs and construction of cages", Journal of Graph Theory, 30 (2): 137–146, doi:10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G, MR 1665972.