Contractible Non-edges in 3-Connected Graphs

✍ Scribed by Matthias Kriesell

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 495 KB
• Volume: 74
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1998.1842

✦ Synopsis

We present a reduction theorem for the class of all finite 3-connected graphs which does not make use of the traditional contraction of certain connected subgraphs.

1998 Academic Press

Contractible edges play an important role in the theory of 3-connected graphs. Besides the famous wheel theorem of Tutte, there are many results on the existence of contractible edges in subclasses of k-connected graphs, on their number, and on their distribution [1 3, 5 8].

We start with some definitions and notation: V(G) denotes the vertex set, E(G) the edge set of the finite graph G. Let |G| :=|V(G)|. An edge between the vertices x and y will be written as [x, y]. As is usual in the context of vertex connectivity we do not allow a graph to have loops or multiple edges. For all X V(G) we define N G (X) :=[ y # V(G)&X: there exists an

A wheel is a graph formed by a chordless cycle and one further vertex which is adjacent to all vertices of the cycle.

We say that T

vertices which separates G will be called a smallest separating set of G. The set of all smallest separating sets will be denoted by T G . Without any further reference we use the fact that T # T G separates T $ # T G if and only if T $ separates T.

Let S be a set of subsets of V(G). Let T # T G and suppose S T for some S # S. The union of at least one but not of all components of G&T is called a T&S-fragment of G. An S-fragment is a T&S-fragment for some T # T G . For example, F is a T&S-fragment if and only if F is a T&S-fragment. An inclusion minimal S-fragment is called an S-end; an Article No. TB981842 192 0095-8956Â98 25.00