TOPICS
Search

Graph Excision


GraphExcision

Let a tree S be a subgraph of a cubic graph G. The graph excision G circleminus S is the graph resulting from removing the tree, then merging the edges. For example, if in the Tutte 8-cage (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.

GraphExcisedCubicSymmetric

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


See also

Cage Graph, Cubic Symmetric Graph

Portions of this entry contributed by Ed Pegg, Jr. (author's link)

Explore with Wolfram|Alpha

References

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

Referenced on Wolfram|Alpha

Graph Excision

Cite this as:

Pegg, Ed Jr. and Weisstein, Eric W. "Graph Excision." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GraphExcision.html

Subject classifications