1 Answers
In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth.
Formally, an -graph is defined to be a graph in which each vertex has exactly r neighbors, and in which the shortest cycle has length exactly g. An -cage is an -graph with the smallest possible number of vertices, among all -graphs. A -cage is often called a g-cage.
It is known that an -graph exists for any combination of r ≥ 2 and g ≥ 3. It follows that all -cages exist.
If a Moore graph exists with degree r and girth g, it must be a cage. Moreover, the bounds on the sizes of Moore graphs generalize to cages: any cage with odd girth g must have at least
5 views
Answered