(k,g)-Cage — различия между версиями

Материал из WikiGrapp
Перейти к:навигация, поиск
(Новая страница: «'''<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 …»)
 
 
Строка 1: Строка 1:
'''<math>(k,g)</math>-Cage''' --- <math>(k,g)</math>-клетка.  
+
'''<math>\,(k,g)</math>-Cage''' — ''[[(k,g)-Клетка|<math>\,(k,g)</math>-клетка]].''
  
For a given ordered pair of integers <math>(k,g)</math>, with <math>k \geq 2</math> and <math>g
+
For a given ordered pair of integers <math>\,(k,g)</math>, with <math>k \geq 2</math> and <math>g
\geq 3</math>, a <math>k</math>-regular graph with the smallest cycle length, or girth,
+
\geq 3</math>, a <math>\,k</math>-[[regular graph]] with the smallest [[cycle]] length, or girth,
equal to <math>g</math> is said to be a <math>(k,g)</math>-graph. A '''<math>(k,g)</math>-cage''' is a
+
equal to <math>\,g</math> is said to be a <math>\,(k,g)</math>-graph. A '''<math>\,(k,g)</math>-cage''' is a
<math>(k,g)</math>-graph having the least number, <math>f(k,g)</math>, of vertices. We call
+
<math>\,(k,g)</math>-graph having the least number, <math>\,f(k,g)</math>, of [[vertex|vertices]]. We call
<math>f(k,g)</math> the ''' cage number''' of a <math>(k,g)</math>-graph. One readily
+
<math>\,f(k,g)</math> the '''[[cage number]]''' of a <math>\,(k,g)</math>-graph. One readily
observes that <math>(2,g)</math>-cages are cycles of length <math>g</math>, and
+
observes that <math>\,(2,g)</math>-cages are cycles of length <math>\,g</math>, and
<math>(k,3)</math>-cages are complete graphs of order <math>k+1</math>.
+
<math>\,(k,3)</math>-cages are [[complete graph|complete graphs]] of order <math>\,k+1</math>.
  
The unique (3,7)-cage known as the '''McGee graph''' is an example of
+
The unique <math>\,(3,7)</math>-cage known as the '''[[McGee graph]]''' is an example of
a cage that is not transitive. It has 24 vertices and its automorphism
+
a cage that is not transitive. It has <math>\,24</math> vertices and its automorphism group has order <math>\,32</math>.
group has order 32.
+
 
 +
==Литература==
 +
 
 +
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.

Текущая версия на 11:50, 24 апреля 2012

\,(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.

Литература

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