Cage (graph theory)

Regular graph with fewest possible nodes for its girth

In the mathematical field of graph theory, a cage is a regular graph that has as few vertices as possible for its girth. Formally, an (r, g)-graph is defined to be a graph in which each vertex has exactly r neighbors, and in which the shortest cycle has a length of exactly g. An (r, g)-cage is an (r, g)-graph with the smallest possible number of vertices, among all (r, g)-graphs.

From Wikipedia, under CC BY-SA. More on occurri.