Abstract | ||
---|---|---|
An edge e in a 3-connected graph G is contractible if the contraction G/e is still 3-connected. The existence of contractible edges is a very useful induction tool. Let G be a simple 3-connected graph with at least five vertices. Wu [7] proved that G has at most [InlineMediaObject not available: see fulltext.] vertices that are not incident to contractible edges. In this paper, we characterize all simple 3-connected graphs with exactly [InlineMediaObject not available: see fulltext.] vertices that are not incident to contractible edges. We show that all such graphs can be constructed from either a single vertex or a 3-edge-connected graph (multiple edges are allowed, but loops are not allowed) by a simple graph operation. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1007/s00373-006-0661-4 | Graphs and Combinatorics |
Keywords | Field | DocType |
connected graph | Discrete mathematics,Topology,Combinatorics,Multigraph,Cycle graph,Neighbourhood (graph theory),Mixed graph,Multiple edges,Mathematics,Path graph,Edge-graceful labeling,Complement graph | Journal |
Volume | Issue | ISSN |
22 | 2 | 1435-5914 |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Joe Anderson | 1 | 1 | 0.82 |
Haidong Wu | 2 | 26 | 8.43 |