An Extremal Problem on Contractible Edges in 3-Connected Graphs |
| |
Authors: | Joe Anderson Haidong Wu |
| |
Institution: | (1) Department of Mathematics, The University of Mississippi, University, MS, 38677 |
| |
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 vertices that are not incident to contractible edges. In this paper, we characterize all simple 3-connected graphs with exactly
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.
Research partially supported by an ONR grant under grant number N00014-01-1-0917 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|