✦ LIBER ✦

Longest cycles in 3-connected graphs contain three contractible edges

✍ Scribed by Nathaniel Dean; Robert L. Hemminger; Katsuhiro Ota

Publisher: John Wiley and Sons
Year: 1989
Tongue: English
Weight: 221 KB
Volume: 13
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190130105

No coin nor oath required. For personal study only.

✦ Synopsis

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 undirected simple graphs. An edge of a 3-connected graph is called contractible if its contraction results in a 3-connected graph; otherwise it is called noncontractible. Note that in a 3-connected graph of order at least five, an edge uu is noncontractible if and only if there exists a 3-cutset containing both u and u. We call such a 3-cutset one associated with the edge uu.

Other terminology is as in [2].

It easily follows from results of Tutte [5] that every 3-connected graph on at least five vertices contains a contractible edge. Thomassen [4] gave a simpler proof of this (and then used it in his elegant induction proof of Kuratowski's Theorem). Using methods similar to Thomassen's, Dean, Hemminger, and Toft [3] improved on this by showing that, in the same setting, longest (x,y)-paths contain at least one contractible edge if xy is an edge. In this paper, we use different methods to get the best result of this type; namely, with two small excep-

📜 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

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

Covering contractible edges in 3-connect

Covering contractible edges in 3-connected graphs. II. Characterizing those with covers of size three

✍ Robert L. Hemminger; Xingxing Yu 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 272 KB 👁 1 views

## Abstract It is shown that if __G__ is a 3‐connected graph with |__V(G)__| ≥ 10, then, with the exception of one infinite class based on __K__~3,__p__~, it takes at least four vertices to cover the set of contractible edges of __G__. © 1993 John Wiley & Sons, Inc.

A degree sum condition for longest cycle

A degree sum condition for longest cycles in 3-connected graphs

✍ Tomoki Yamashita 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 110 KB 👁 1 views

## Abstract For a graph __G__, we denote by __d__~__G__~(__x__) and κ(__G__) the degree of a vertex __x__ in __G__ and the connectivity of __G__, respectively. In this article, we show that if __G__ is a 3‐connected graph of order __n__ such that __d__~__G__~(__x__) + __d__~__G__~(__y__) + __d__~__

Relative length of longest paths and cyc

Relative length of longest paths and cycles in 3-connected graphs

✍ Rao Li; Akira Saito; R.H. Schelp 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB 👁 2 views

## Abstract For a graph __G__, let __p(G)__ denote the order of a longest path in __G__ and __c(G)__ the order of a longest cycle in __G__, respectively. We show that if __G__ is a 3‐connected graph of order __n__ such that $\textstyle{\sum^{4}\_{i=1}\,{\rm deg}\_{G}\,x\_{i} \ge {3\over2}\,n + 1}$

Cycles containing 12 vertices in 3-conne

Cycles containing 12 vertices in 3-connected cubic graphs

✍ Sheng Bau; Derek Holton 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 436 KB

## Abstract A necessary and sufficient condition is obtained for a set of 12 vertices in any 3‐connected cubic graph to lie on a common cycle.