(Graph Theory)

Logo of Cage (graph theory)
Graph Theory
Link to Dbpedia

What is Cage (graph theory)?

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 (r,g)-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. It is known that an (r,g)-graph exists for any combination of r ≥ 2 and g ≥ 3. An (r,g)-cage is an (r,g)-graph with the fewest possible number of vertices, among all (r,g)-graphs. 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 vertices, and any cage with even girth g must have at least vertices. Any (r,g)-graph with exactly this many vertices is by definition a Moore graph and therefore automatically a cage. There may exist multiple cages for a given combination of r and g. For instance there are three nonisomorphic (3,10)-cages, each with 70 vertices : the Balaban 10-cage, the Harries graph and the Harries–Wong graph. But there is only one (3,11)-cage : the Balaban 11-cage (with 112 vertices).

Technology Types

familygraph familygraph theoryregular graphsocial group


Cage graph


Jaula (teoría de grafos) (es)Клетка (теория графов) (ru)Клітка (теорія графів) (uk)ケージ (グラフ理論) (ja)

Tech Info

Source: [object Object]
 — Date merged: 11/6/2021, 1:32:43 PM
 — Date scraped: 5/20/2021, 6:16:31 PM