✦ LIBER ✦

Contractible Edges and Triangles in k-Connected Graphs

✍ Scribed by Ken-ichi Kawarabayashi

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 129 KB
Volume: 85
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2001.2096

No coin nor oath required. For personal study only.

✦ Synopsis

It is proved that if G is a k-connected graph which does not contain K - 4 , then G has an edge e or a triangle T such that the graph obtained from G by connecting e or by contracting T is still k-connected. By using this theorem, we prove some theorems which are generalizations of earlier work. In addition, we give a condition for a k-connected graph to have a k-contractible edge, which implies two theorems proved by C.

📜 SIMILAR VOLUMES

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

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

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

Contractible elements in k-connected gra

Contractible elements in k-connected graphs not containing some specified graphs

✍ Shinya Fujita; Ken-ichi Kawarabayashi 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 162 KB

In [15] , Thomassen proved that any triangle-free k-connected graph has a contractible edge. Starting with this result, there are several results concerning the existence of contractible elements in k-connected graphs which do not contain specified subgraphs. These results extend

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

Covering contractible edges in 3-connect

Covering contractible edges in 3-connected graphs. I: Covers of size three are cutsets

✍ Akira Saito 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 397 KB 👁 1 views

## Abstract An edge of a 3‐connected graph is said to be __contractible__ if its contraction results in a 3‐connected graph. In this paper, a covering of contractible edges is studied. We give an alternative proof to the result of Ota and Saito (__Scientia__ (A) 2 (1988) 101–105) that the set of co