Cage

(Graph Theory)

Logo of Cage (graph theory)
skills
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

Synonyms

Cage graph

Translations

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