تسجيل الدخول

تسجيل

Graph Excision

المؤلف:  Biggs, N

المصدر:  "Constructions for Cubic Graphs with Large Girth." Elec. J. Combin. 5, Aug. 31, 1998.

الجزء والصفحة:  ...

10-4-2022

2222

Graph Excision

 

Let a tree  be a subgraph of a cubic graph . The graph excision  is the graph resulting from removing the tree, then merging the edges. For example, if in the Levi graph (left figure) the tree formed by the 6 interior points (middle figure) is excised, the McGee graph (right figure) results. Similarly, excising the Heawood graph gives the Petersen graph, and excising the generalized hexagon (i.e., the unique 12-cage graph) gives the Balaban 11-cage (Biggs 1998).

The reverse of excision is insertion. Both operations are used in the analysis of cages.

The following table gives some cubic symmetric graphs with named edge-excised graphs, illustrated above.

graph	edge-excised graph
utility graph	tetrahedral graph
cubical graph	3-prism graph
Petersen graph	4-Möbius ladder
Heawood graph	12-cubic graph 84
Möbius-Kantor graph	14-cubic graph 503
dodecahedral graph	cubic polyhedral graph Cp34

---

REFERENCES

Biggs, N. "Constructions for Cubic Graphs with Large Girth." Elec. J. Combin. 5, Aug. 31, 1998.