𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Vertex suppression in 3-connected graphs

✍ Scribed by Matthias Kriesell

Publisher
John Wiley and Sons
Year
2007
Tongue
English
Weight
265 KB
Volume
57
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

To suppress a vertex $v$ in a finite graph G means to delete it and add an edge from a to b if a, b are distinct nonadjacent vertices which formed the neighborhood of $v$. Let $G--x$ be the graph obtained from $G-x$ by suppressing vertices of degree at most 2 as long as it is possible; this is proven to be well defined.

Our main result states that every 3‐connected graph G has a vertex x such that $G -- x$ is 3‐connected unless G is isomorphic to $K_{3,3}$, $K_2 \times K_3$, or to a wheel $K_{1}*C_{\ell}$ for some $\ell \geq 3$. This leads to a generator theorem for 3‐connected graphs in terms of series parallel extensions. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 41–54, 2008

📜 SIMILAR VOLUMES

An 11-vertex theorem for 3-connected cub
An 11-vertex theorem for 3-connected cubic graphs
✍ R. E. L. Aldred; BauSheng; D. A. Holton; Gordon F. Royle 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 451 KB 👁 1 views

In this paper w e determine the circumstances under which a set of 11 vertices in a 3-connected cubic graph lies on a cycle. In addition, w e consider the number of such cycles that exist and characterize those graphs in which a set of 9 vertices lies in exactly two cycles.

Concept of a vertex in a matroid and 3-c
Concept of a vertex in a matroid and 3-connected graphs
✍ A. K. Kelmans 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 316 KB

## Abstract The concept of a matroid vertex is introduced. The vertices of a matroid of a 3‐connected graph are in one‐to‐one correspondence with vertices of the graph. Thence directly follows Whitney's theorem that cyclic isomorphism of 3‐connected graphs implies isomorphism. The concept of a vert

Removable edges in 3-connected graphs
Removable edges in 3-connected graphs
✍ Derek A. Holton; Bill Jackson; Akira Saito; Nicholas C. Wormald 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 404 KB

## Abstract An edge __e__ of a 3‐connected graph __G__ is said to be __removable__ if __G__ ‐ __e__ is a subdivision of a 3‐connected graph. If __e__ is not removable, then __e__ is said to be __nonremovable.__ In this paper, we study the distribution of removable edges in 3‐connected graphs and pr

Contractile Triples in 3-Connected Graph
Contractile Triples in 3-Connected Graphs
✍ W. Mccuaig; K. Ota 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 295 KB

We prove that every 3-connected graph \(G\) of order at least nine has two adjacent edges \(x y\) and \(y z\) such that the graph obtained from \(G\) by contracting \(x, y\), and \(z\) into a single vertex is also 3-connected. (i) 1994 Academic Press. Inc.

Long Cycles in 3-Connected Graphs
Long Cycles in 3-Connected Graphs
✍ Guantao Chen; Xingxing Yu 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 249 KB

Moon and Moser in 1963 conjectured that if G is a 3-connected planar graph on n vertices, then G contains a cycle of length at least Oðn log 3 2 Þ: In this paper, this conjecture is proved. In addition, the same result is proved for 3-connected graphs embeddable in the projective plane, or the torus