(k,g)-Cage

Материал из WikiGrapp
Версия от 15:24, 24 февраля 2011; Glk (обсуждение | вклад) (Новая страница: «'''<math>(k,g)</math>-Cage''' --- <math>(k,g)</math>-клетка. For a given ordered pair of integers <math>(k,g)</math>, with <math>k \geq 2</math> and <math>g …»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к:навигация, поиск

(k,g)-Cage --- (k,g)-клетка.

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.