Материал из WikiGrapp
Перейти к:навигация, поиск


For a given ordered pair of integers \,(k,g), with k \geq 2 and g
\geq 3, a \,k-regular graph with the smallest cycle length, or girth, equal to \,g is said to be a \,(k,g)-graph. A \,(k,g)-cage is a \,(k,g)-graph having the least number, \,f(k,g), of vertices. We call \,f(k,g) the cage number of a \,(k,g)-graph. One readily observes that \,(2,g)-cages are cycles of length \,g, and \,(k,3)-cages are complete graphs of order \,k+1.

The unique \,(3,7)-cage known as the McGee graph is an example of a cage that is not transitive. It has \,24 vertices and its automorphism group has order \,32.


  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.