✦ LIBER ✦

Connectivity, graph minors, and subgraph multiplicity

✍ Scribed by David Eppstein

Publisher: John Wiley and Sons
Year: 1993
Tongue: English
Weight: 435 KB
Volume: 17
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190170314

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

It is well known that any planar graph contains at most O(n) complete subgraphs. We extend this to an exact characterization: G occurs O(n) times as a subgraph of any planar graph, if and only if G is three‐connected. We generalize these results to similarly characterize certain other minor‐closed families of graphs; in particular, G occurs O(n) times as a subgraph of the K~b,c~‐free graphs, b ≥ c and c ≤ 4, iff G is c‐connected. Our results use a simple Ramsey‐theoretic lemma that may be of independent interest. © 1993 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

Connected Spanning Subgraphs of 3-Connec

Connected Spanning Subgraphs of 3-Connected Planar Graphs

✍ Hikoe Enomoto; Tadashi Iida; Katsuhiro Ota 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 339 KB

Contractible subgraphs in k-connected gr

Contractible subgraphs in k-connected graphs

✍ Zemin Jin; Xingxing Yu; Xiaoyan Zhang 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 185 KB

## Abstract For a graph __G__ we define a graph __T__(__G__) whose vertices are the triangles in __G__ and two vertices of __T__(__G__) are adjacent if their corresponding triangles in __G__ share an edge. Kawarabayashi showed that if __G__ is a __k__‐connected graph and __T__(__G__) contains no ed

Contractible Subgraphs in 3-Connected Gr

Contractible Subgraphs in 3-Connected Graphs

✍ Matthias Kriesell 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 154 KB

A subgraph H of a 3-connected finite graph G is called contractible if H is connected and G&V(H) is 2-connected. This work is concerned with a conjecture of McCuaig and Ota which states that for any given k there exists an f (k) such that any 3-connected graph on at least f (k) vertices possesses a

Hamiltonicity and forbidden subgraphs in

Hamiltonicity and forbidden subgraphs in 4-connected graphs

✍ Florian Pfender 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 121 KB

## Abstract Let __T__ be the line graph of the unique tree __F__ on 8 vertices with degree sequence (3,3,3,1,1,1,1,1), i.e., __T__ is a chain of three triangles. We show that every 4‐connected {__T__, __K__~1,3~}‐free graph has a hamiltonian cycle. © 2005 Wiley Periodicals, Inc. J Graph Theory 49:

Typical Subgraphs of 3- and 4-Connected

Typical Subgraphs of 3- and 4-Connected Graphs

✍ B. Oporowski; J. Oxley; R. Thomas 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 773 KB

2-Connected Spanning Subgraphs of Planar

2-Connected Spanning Subgraphs of Planar 3-Connected Graphs

✍ D.W. Barnette 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 278 KB

We prove that every planar 3-connected graph has a 2-connected spanning subgraph of maximum valence 15 . We give an example of a planar 3 -connected graph with no spanning 2-connected subgraph of maximum valence five. i) 1994 Academic Press, Inc.