𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Nonseparating Induced Cycles Consisting of Contractible Edges in k -Connected Graphs

✍ Scribed by Egawa, Yoshimi; Inoue, Katsumi; Kawarabayashi, Ken-ichi

Book ID
118196960
Publisher
Society for Industrial and Applied Mathematics
Year
2008
Tongue
English
Weight
175 KB
Volume
21
Category
Article
ISSN
0895-4801

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Nonseparating cycles in K-Connected grap
Nonseparating cycles in K-Connected graphs
✍ Carsten Thomassen πŸ“‚ Article πŸ“… 1981 πŸ› John Wiley and Sons 🌐 English βš– 192 KB πŸ‘ 1 views

## Abstract We show that every __k__‐connected graph with no 3‐cycle contains an edge whose contraction results in a __k__‐connected graph and use this to prove that every (__k__ + 3)‐connected graph contains a cycle whose deletion results in a __k__‐connected graph. This settles a problem of L. Lo

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