Abstract | ||
---|---|---|
An edge e of a simple 3-connected graph G is essential if neither the deletion G\e nor the contraction G/e is both simple and 3-connected. Tutte’s Wheels Theorem proves that the only simple 3-connected graphs with no non-essential edges are the wheels. In earlier work, as a corollary of a matroid result, the authors determined all simple3-connected graphs with at most two non-essential edges. This paper specifies all such graphs with exactly three non-essential edges. As a consequence, with the exception of the members of 10 classes of graphs, all 3-connected graphs have at least four non-essential edges. |
Year | DOI | Venue |
---|---|---|
2004 | 10.1007/s00373-004-0552-5 | Graphs and Combinatorics |
Keywords | Field | DocType |
wheels theorem,3-connected graph,simple3-connected graph,edge e,matroid result,contraction g,non-essential edge,3-connected graphs,earlier work,deletion g,non-essential edges,theorem proving,connected graph | Pseudoforest,Topology,Odd graph,Discrete mathematics,Indifference graph,Combinatorics,Clique-sum,Chordal graph,Pathwidth,1-planar graph,Mathematics,Dense graph | Journal |
Volume | Issue | ISSN |
20 | 2 | 0911-0119 |
Citations | PageRank | References |
1 | 0.48 | 3 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
James Oxley | 1 | 397 | 57.57 |
Haidong Wu | 2 | 1 | 0.48 |