Cage

From Graph
Revision as of 04:09, 29 May 2012 by Vipul (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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.