✦ LIBER ✦

Long Cycles in 3-Connected Graphs

✍ Scribed by Guantao Chen; Xingxing Yu

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 249 KB
Volume: 86
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2002.2113

No coin nor oath required. For personal study only.

✦ Synopsis

Moon and Moser in 1963 conjectured that if G is a 3-connected planar graph on n vertices, then G contains a cycle of length at least Oðn log 3 2 Þ: In this paper, this conjecture is proved. In addition, the same result is proved for 3-connected graphs embeddable in the projective plane, or the torus, or the Klein bottle. # 2002 Elsevier Science (USA)

📜 SIMILAR VOLUMES

Long cycles in 3-connected graphs in ori

Long cycles in 3-connected graphs in orientable surfaces

✍ Laura Sheppardson; Xingxing Yu 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 157 KB 👁 1 views

## Abstract In this article, we apply a cutting theorem of Thomassen to show that there is a function __f__: N → N such that if __G__ is a 3‐connected graph on __n__ vertices which can be embedded in the orientable surface of genus __g__ with face‐width at least __f__(__g__), then __G__ contains a

Long Cycles and 3-Connected Spanning Sub

Long Cycles and 3-Connected Spanning Subgraphs of Bounded Degree in 3-Connected K1, d-Free Graphs

✍ B. Jackson; N.C. Wormald 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 238 KB

Let \(G\) be a 3-connected \(K_{1, d}\)-free graph on \(n\) vertices. We show that \(G\) contains a 3-connected spanning subgraph of maximum degree at most \(2 d-1\). Using an earlier result of ours, we deduce that \(G\) contains a cycle of length at least \(\frac{1}{2} n^{c}\) where \(c=\left(\log

Long cycles passing through a specified

Long cycles passing through a specified edge in a 3-connected graph

✍ Enomoto, Hikoe; Hirohata, Kazuhide; Ota, Katsuhiro 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB 👁 2 views

We prove the following theorem: For a connected noncomplete graph Then through each edge of G there passes a cycle of length ≥ min{|V (G)|, τ(G) -1}.

Hamiltonian cycles in 3-connected claw-f

Hamiltonian cycles in 3-connected claw-free graphs

✍ MingChu Li 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 437 KB 👁 2 views

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

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.