𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Unavoidable parallel minors of 4-connected graphs

✍ Scribed by Carolyn Chun; Guoli Ding; Bogdan Oporowski; Dirk Vertigan

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
154 KB
Volume
60
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A parallel minor is obtained from a graph by any sequence of edge contractions and parallel edge deletions. We prove that, for any positive integer k, every internally 4‐connected graph of sufficiently high order contains a parallel minor isomorphic to a variation of K~4,k~ with a complete graph on the vertices of degree k, the k‐partition triple fan with a complete graph on the vertices of degree k, the k‐spoke double wheel, the k‐spoke double wheel with axle, the (2k+1)‐rung Möbius zigzag ladder, the (2__k__)‐rung zigzag ladder, or K~k~. We also find the unavoidable parallel minors of 1‐, 2‐, and 3‐connected graphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 313‐326, 2009

📜 SIMILAR VOLUMES

Unavoidable Minors of Large 3-Connected
Unavoidable Minors of Large 3-Connected Matroids
✍ Guoli Ding; Bogdan Oporowski; James Oxley; Dirk Vertigan 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 704 KB

This paper proves that, for every integer n exceeding two, there is a number N(n) such that every 3-connected matroid with at least N(n) elements has a minor that is isomorphic to one of the following matroids: an (n+2)-point line or its dual, the cycle or cocycle matroid of K 3, n , the cycle matro

Unavoidable Minors of Large 3-Connected
Unavoidable Minors of Large 3-Connected Binary Matroids
✍ Guoli Ding; Bogdan Oporowski; James Oxley; Dirk Vertigan 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 759 KB

We show that, for every integer n greater than two, there is a number N such that every 3-connected binary matroid with at least N elements has a minor that is isomorphic to the cycle matroid of K 3, n , its dual, the cycle matroid of the wheel with n spokes, or the vector matroid of the binary matr

Edge-reconstruction of 4-connected plana
Edge-reconstruction of 4-connected planar graphs
✍ S. Fiorini; J. Lauri 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 482 KB 👁 2 views

## Abstract The object of this paper is to show that 4‐connected planar graphs are uniquely determined from their collection of edge‐deleted subgraphs.

On minors of graphs with at least 3n −4
On minors of graphs with at least 3n −4 edges
✍ M. Khalifat; Themistocles Politof; A. Satyanarayana 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 390 KB 👁 1 views

## Abstract A point disconnecting set __S__ of a graph __G__ is a nontrivial __m__‐separator, where __m__ = |__S__|, if the connected components of __G__ ‐ __S__ can be partitioned into two subgraphs, each of which has at least two points. A 3‐connected graph is quasi 4‐connected if it has no nontr