GraphTheory[SpecialGraphs] - Maple Programming Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : SpecialGraphs : GraphTheory/SpecialGraphs/CageGraph

GraphTheory[SpecialGraphs]

 CageGraph
 construct cage graph

 Calling Sequence CageGraph(K, G)

Parameters

 K - degree of graph G - girth of graph

Description

 • The CageGraph(K,G) command creates the (K,G')-cage graph, that is, the smallest K-regular graph(s) with girth G.
 • If more than one graph meets these criteria, a sequence of graphs is returned.
 • In the cases where the smallest graph is not known, FAIL is returned.

Named Cage Graphs

 • Several notable cage graphs have been assigned names and can be individually accessed under these names within the SpecialGraphs subpackage. These include:
 • (3,5)-cage: PetersenGraph
 • (3,6)-cage: HeawoodGraph
 • (3,8)-cage: Tutte8CageGraph
 • (3,10)-cages: Balaban10CageGraph, HarriesGraph, and HarriesWongGraph
 • (4,5)-cage: RobertsonGraph
 • (5,5)-cages: FosterCageGraph, MeringerGraph, RobertsonWegnerGraph, and WongGraph.
 • (7,5)-cage: HoffmanSingletonGraph

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{SpecialGraphs}\right):$

This is the Petersen graph

 > $C≔\mathrm{CageGraph}\left(3,5\right)$
 ${C}{:=}{\mathrm{Graph 1: an undirected unweighted graph with 10 vertices and 15 edge\left(s\right)}}$ (1)
 > $\mathrm{DrawGraph}\left(C\right)$

A sequence of three 3-regular graphs with girth 10

 > $\mathrm{C3}≔\mathrm{CageGraph}\left(3,10\right)$
 ${\mathrm{C3}}{:=}{\mathrm{Graph 2: an undirected unweighted graph with 70 vertices and 105 edge\left(s\right)}}{,}{\mathrm{Graph 3: an undirected unweighted graph with 70 vertices and 105 edge\left(s\right)}}{,}{\mathrm{Graph 4: an undirected unweighted graph with 70 vertices and 105 edge\left(s\right)}}$ (2)

Not known

 > $\mathrm{CageGraph}\left(8,11\right)$
 ${\mathrm{FAIL}}$ (3)