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