Reductions of 3-connected graphs with minimum degree at least four

  • Sheng Bau
Keywords: 3-connected graph, cyclically 4-edge connected, minimum degree, contraction, minor inclusion

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, vxE(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) has a vertex x with N(x) = {x1, x2, x3, x4} and x1x2, x3x4E(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: 3-connected graph, cyclically 4-edge connected, minimum degree, contraction, minor inclusion

Published
2018-07-17
Section
Articles

Journal Identifiers


eISSN: 1727-933X
print ISSN: 1607-3606