Graph girth g(G): length of shortest cycle. g=∞ for forests. g(K_n)=3, g(K_{m,n})=4 (m,n≥2), g(Petersen)=5. A (d,g)-cage is the smallest d-regular graph with girth g. Moore bound limits graph size given degree and girth.
How to Use
Select graph:
- g(G): Girth
- Moore: Size bound
- Cage: Smallest regular
Moore Bound
For d-regular graph with girth g: n ≤ M(d,g). For odd g=2k+1: M = 1+d·((d-1)^k-1)/(d-2). For even g=2k: M = 2·((d-1)^k-1)/(d-2). Graphs meeting this bound are Moore graphs. Only 5 known Moore graphs!
Cage Graphs
(d,g)-cage: smallest d-regular graph with girth g. (3,5)-cage = Petersen (10 vertices). (3,6)-cage = Heawood (14). Finding cages is a major open problem. Many cages are unknown.
Step-by-Step Instructions
- 1Select graph.
- 2Compute girth.
- 3Check Moore.
- 4Find cage.
- 5Compare graphs.