✦ LIBER ✦

On contractible and vertically contractible elements in 3-connected matroids and graphs

✍ Scribed by Haidong Wu

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 1000 KB
Volume: 179
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(96)00385-8

No coin nor oath required. For personal study only.

✦ Synopsis

An edge e in a 3-connected graph G is contractible if the contraction G/e is still 3-connected.

The problem of bounding the number of contractible edges in a 3-connected graph has been studied by numerous authors. In this paper, the corresponding problem for matroids is considered and new graph results are obtained. An element e in a 3-connected matroid M is contractible or vertically contractible if its contraction M/e is, respectively, 3-connected or vertically 3-connected.

Cunningham and Seymour independently proved that every 3-connected matroid has a vertically contractible element. In this paper, we study the contractible and vertically contractible elements in 3-connected matroids and get best-possible lower bounds for the number of vertically contractible elements in 3-connected and minimally 3-connected matroids. We also prove generalizations of Tutte's Wheels and Whiffs Theorem for matroids and Tutte's Wheels Theorem for 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 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 Edges and Triangles in k-Co

Contractible Edges and Triangles in k-Connected Graphs

✍ Ken-ichi Kawarabayashi 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 129 KB

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

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

3-connected graphs with non-cut contract

3-connected graphs with non-cut contractible edge covers of size k

✍ Xingxing Yu 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 493 KB 👁 1 views

## Abstract In this paper, we show that if a 3‐connected graph __G__ other than __K__~4~ has a vertex subset __K__ that covers the set of contractible edges of __G__ and if |__K__| 3 and |__V(G)__| 3|__K__| − 1, then __K__ is a cutset of __G__. We also give examples to show that this result is best

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