✦ LIBER ✦

The structure of quasi 4-connected graphs

✍ Scribed by Themistocles Politof; A. Satyanarayana

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 646 KB
Volume: 161
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(95)00229-p

No coin nor oath required. For personal study only.

✦ Synopsis

A minimal point disconnecting set S of a graph G is a nontrivial m-separator, where m = IS I, 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 nontrivial 3separators. This paper provides the following structural characterization of quasi 4-connected graphs. Every quasi 4-connected graph can be obtained from a wheel on at most six points, or a prism or a M/Sbius ladder by repeatedly (i) adding edges, (ii) splitting points, and/or (iii) replacing a triangle containing points of degree at least four by the graph obtained from K 4 by deleting an edge.

📜 SIMILAR VOLUMES

Minors of quasi 4-connected graphs

✍ Themistocles Politof; A. Satyanarayana 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 744 KB

A minimal point disconnecting set S of a graph G is a nontrivial m-separator, where m=IS), if the connected components of G-S can be partitioned into two sets each of which has at least two points. A 3-connected graph is quasi 4-connected if it has no nontrivial S-separators. Let G be a quasi 4-conn

All 4-connected Line Graphs of Claw Free

All 4-connected Line Graphs of Claw Free Graphs Are Hamiltonian Connected

✍ Matthias Kriesell 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 109 KB

Thomassen conjectured that every 4-connected line graph is hamiltonian. Here we shall see that 4-connected line graphs of claw free graphs are hamiltonian connected.

A recursive characterization of the 4-co

A recursive characterization of the 4-connected graphs

✍ Nicola Martinov 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 244 KB

We present a complete description of the set of 4-connected contraction-critical graphs.

Re-embedding structures of 4-connected p

Re-embedding structures of 4-connected projective-planar graphs

✍ Yusuke Suzuki 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 212 KB

We identify the structures of 4-connected projective-planar graphs which generate their inequivalent embeddings on the projective plane, showing two series of graphs the number of whose inequivalent embeddings is held by O(n) with respect to the number of its vertices n.

On the Structure of 3-connected Matroids

On the Structure of 3-connected Matroids and Graphs

✍ James Oxley; Haidong Wu 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 249 KB

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-conne

Unavoidable parallel minors of 4-connect

Unavoidable parallel minors of 4-connected graphs

✍ Carolyn Chun; Guoli Ding; Bogdan Oporowski; Dirk Vertigan 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB

## 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