(k,g)-Cage

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