Cage

From Graph
Jump to: navigation, search

Definition

Suppose and are positive integers, with . Consider the collection of all finite undirected graphs that are -regular graphs and have girth . A -cage is a graph in this collection that has the minimum possible number of vertices, i.e., there is no graph in the collection with fewer vertices.

If is not explicitly specified, then we are referring to the case , i.e., to cubic graphs.