✦ LIBER ✦

On the Structure of 3-connected Matroids and Graphs

✍ Scribed by James Oxley; Haidong Wu

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 249 KB
Volume: 21
Category: Article
ISSN: 0195-6698
DOI: 10.1006/eujc.2000.0407

No coin nor oath required. For personal study only.

✦ Synopsis

An element e of a 3-connected matroid M is essential if neither the deletion M\e nor the contraction M/e is 3-connected. Tutte's Wheels and Whirls Theorem proves that the only 3-connected matroids in which every element is essential are the wheels and whirls. In this paper, we consider those 3-connected matroids that have some non-essential elements, showing that every such matroid M must have at least two such elements. We prove that the essential elements of M can be partitioned into classes where two elements are in the same class if M has a fan, a maximal partial wheel, containing both. We also prove that if an essential element e of M is in more than one fan, then that fan has three or five elements; in the latter case, e is in exactly three fans. Moreover, we show that if M has a fan with 2k or 2k + 1 elements for some k ≥ 2, then M can be obtained by sticking together a (k + 1)-spoked wheel and a certain 3-connected minor of M. The results proved here will be used elsewhere to completely determine all 3-connected matroids with exactly two non-essential elements.

📜 SIMILAR VOLUMES

Characterizing 3-connected planar graphs

Characterizing 3-connected planar graphs and graphic matroids

✍ Manoel Lemos; Talmage James Reid; Haidong Wu 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 98 KB

## Abstract A well‐known result of Tutte states that a 3‐connected graph __G__ is planar if and only if every edge of __G__ is contained in exactly two induced non‐separating circuits. Bixby and Cunningham generalized Tutte's result to binary matroids. We generalize both of these results and give n

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

2-connected 7-coverings of 3-connected g

2-connected 7-coverings of 3-connected graphs on surfaces

✍ Ken-ichi Kawarabayashi; Atsuhiro Nakamoto; Katsuhiro Ota 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 116 KB 👁 1 views

## Abstract An __m__‐__covering__ of a graph __G__ is a spanning subgraph of __G__ with maximum degree at most __m__. In this paper, we shall show that every 3‐connected graph on a surface with Euler genus __k__ ≥ 2 with sufficiently large representativity has a 2‐connected 7‐covering with at most

Cyclability of 3-connected graphs

✍ Amel Harkat-Benhamdine; Hao Li; Feng Tian 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 151 KB 👁 1 views

On convex embeddings of planar 3-connect

On convex embeddings of planar 3-connected graphs

✍ Kelmans, Alexander 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB 👁 2 views

A well-known Tutte's theorem claims that every 3-connected planar graph has a convex embedding into the plane. Tutte's arguments also show that, moreover, for every nonseparating cycle C of a 3-connected graph G, there exists a convex embedding of G such that C is a boundary of the outer face in thi

On the Connectivity Function of a Binary

On the Connectivity Function of a Binary Matroid

✍ Manoel Lemos 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 210 KB

In this paper, we shall consider the following problem: up to duality, is a connected matroid reconstructible from its connectivity function? Cunningham conjectured that this question has an affirmative answer, but Seymour gave a counter-example for it. In the same paper, Seymour proved that a conne