(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 …»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

[math]\displaystyle{ (k,g) }[/math]-Cage --- [math]\displaystyle{ (k,g) }[/math]-клетка.

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

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.