Материал из WikiGrapp
Версия от 11:50, 24 апреля 2012; KEV (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к:навигация, поиск


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.