Reductions of 3-connected graphs with minimum degree at least four |
| |
Authors: | Sheng Bau |
| |
Institution: | 1. School of Mathematics, Statistics and Computer Science, University of Kwazulu Natal, Private Bag X01, Scottsville, South Africa;2. Institute of Discrete Mathematics, Inner Mongolia University of Nationalities, Tongliao, Chinabaus@ukzn.ac.za |
| |
Abstract: | We show that if G is a 3-connected graph of minimum degree at least 4 and with |V (G)| ≥ 7 then one of the following is true: (1) G has an edge e such that G/e is a 3-connected graph of minimum degree at least 4; (2) G has two edges uv and xy with ux, vy, vx ∈ E(G) such that the graph G/uv/xy obtained by contraction of edges uv and xy in G is a 3-connected graph of minimum degree at least 4; (3) G has a vertex x with N(x) = {x1, x2, x3, x4} and x1x2, x3x4 ∈ E(G) such that the graph (G ? x)/x1x2/x3x4 obtained by contraction of edges x1x2 and x3x4 in G – x is a 3-connected graph of minimum degree at least 4.Each of the three reductions is necessary: there exists an infinite family of 3- connected graphs of minimum degree not less than 4 such that only one of the three reductions may be performed for the members of the family and not the two other reductions. |
| |
Keywords: | 05C75 05C83 |
|
|