𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Contractible Subgraphs in 3-Connected Graphs

✍ Scribed by Matthias Kriesell

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
154 KB
Volume
80
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

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 contractible subgraph on k vertices. We prove this for k 4 and consider restrictions to maximal planar graphs, Halin graphs, line graphs of 6-edge-connected graphs, 5-connected graphs of bounded degree, and AT-free graphs.

πŸ“œ SIMILAR VOLUMES

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 Non-edges in 3-Connected Gr
Contractible Non-edges in 3-Connected Graphs
✍ Matthias Kriesell πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 495 KB

We present a reduction theorem for the class of all finite 3-connected graphs which does not make use of the traditional contraction of certain connected subgraphs. ## 1998 Academic Press Contractible edges play an important role in the theory of 3-connected graphs. Besides the famous wheel theore

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.

Longest cycles in 3-connected graphs con
Longest cycles in 3-connected graphs contain three contractible edges
✍ Nathaniel Dean; Robert L. Hemminger; Katsuhiro Ota πŸ“‚ Article πŸ“… 1989 πŸ› John Wiley and Sons 🌐 English βš– 221 KB πŸ‘ 1 views

We show that if G is a 3-connected graph of order at least seven, then every longest path between distinct vertices in G contains at least two contractible edges. An immediate corollary is that longest cycles in such graphs contain at least three contractible edges. We consider only finite undirect

Connected subgraphs with small degree su
Connected subgraphs with small degree sums in 3-connected planar graphs
✍ Enomoto, Hikoe; Ota, Katsuhiro πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 213 KB πŸ‘ 2 views

It is well-known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3-connected planar graph has an edge xy such that deg(x) + deg(y) ≀ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we sh