𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Generating Internally Four-Connected Graphs

✍ Scribed by Thor Johnson; Robin Thomas

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
257 KB
Volume
85
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

A graph is a minor of another if the first can be obtained from a subgraph of the second by contracting edges. A graph G is internally 4-connected if it is simple, 3-connected, has at least five vertices, and if for every partition (A, B) of the edgeset of G, either |A| [ 3 or |B| [ 3 or at least four vertices of G are incident with an edge in A and an edge in B. We prove that if H and G are internally 4-connected graphs such that they are not isomorphic, H is a minor of G, and they do not belong to a family of exceptional graphs, then there exists a graph HOE such that HOE is isomorphic to a minor of G and either HOE is obtained from H by splitting a vertex or HOE is an internally 4-connected graph obtained from H by means of one of four possible constructions. This is a first step toward a more comprehensive theorem along the same lines.

📜 SIMILAR VOLUMES

A characterization of weakly four-connec
A characterization of weakly four-connected graphs
✍ Tibor Jordán 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 106 KB

## Abstract A graph __G__ = (__V__, __E__) is called weakly four‐connected if __G__ is 4‐edge‐connected and __G__ − __x__ is 2‐edge‐connected for all __x__ ∈ __V__. We give sufficient conditions for the existence of ‘splittable’ vertices of degree four in weakly four‐connected graphs. By using thes

On Four-Connecting a Triconnected Graph
On Four-Connecting a Triconnected Graph
✍ Tsan-sheng Hsu 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 328 KB

We consider the problem of finding a smallest set of edges whose addition four-connects a triconnected graph. This is a fundamental graph-theoretic problem that has applications in designing reliable networks and improving statistical Ž Ž . . database security. We present an O n и ␣ m, n q m -time a

Generating all planer graphs regular of
Generating all planer graphs regular of degree four
✍ Paolo Manca 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 225 KB 👁 1 views

## Abstract All planar connected graphs regular of degree four can be generated from the graph of the octahedron, using four operations.

Generating all 3-connected 4-regular pla
Generating all 3-connected 4-regular planar graphs from the octahedron graph
✍ H. J. Broersma; A. J. W. Duijvestijn; F. Göbel 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 384 KB 👁 1 views

## Abstract We prove that all 3‐connected 4‐regular planar graphs can be generated from the Octahedron Graph, using three operations. We generated these graphs up to 15 vertices inclusive. Moreover, by including a fourth operation we obtain an alternative to a procedure by Lehel to generate all con

Long paths through four vertices in a 2-
Long paths through four vertices in a 2-connected graph
✍ Barovich, Mark V. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 252 KB 👁 2 views

Let G be a 2-connected graph, let u and v be distinct vertices in V (G), and let X be a set of at most four vertices lying on a common (u