✦ LIBER ✦

Chords of Longest Cycles in Cubic Graphs

✍ Scribed by Carsten Thomassen

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 213 KB
Volume: 71
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1997.1776

No coin nor oath required. For personal study only.

✦ Synopsis

We describe a general sufficient condition for a Hamiltonian graph to contain another Hamiltonian cycle. We apply it to prove that every longest cycle in a 3-connected cubic graph has a chord. We also verify special cases of an old conjecture of Sheehan on Hamiltonian cycles in 4-regular graphs and a recent conjecture on a second Hamiltonian cycle by Triesch, Nolles, and Vygen.

📜 SIMILAR VOLUMES

Disjoint cycles with chords in graphs

✍ Ch. Sobhan Babu; Ajit A. Diwan 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 134 KB

## Abstract Let $n\_1,n\_2,\ldots,n\_k$ be integers, $n=\sum n\_i$, $n\_i\ge 3$, and let for each $1\le i\le k$, $H\_i$ be a cycle or a tree on $n\_i$ vertices. We prove that every graph __G__ of order at least __n__ with $\sigma\_2(G) \ge 2( n-k) -1$ contains __k__ vertex disjoint subgraphs $H\_1'

Longest cycles in tough graphs

✍ Jung, H.A.; Wittmann, P. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 347 KB 👁 2 views

In this article, we establish bounds for the length of a longest cycle C in a 2-connected graph G in terms of the minimum degree δ and the toughness t. It is shown that C is a Hamiltonian cycle or |C| ≥ (t + 1)δ + t.

Intersections of longest cycles in grid

Intersections of longest cycles in grid graphs

✍ Menke, B.; Zamfirescu, T.; Zamfirescu, C. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 292 KB 👁 3 views

It is well-known that the largest cycles of a graph may have empty intersection. This is the case, for example, for any hypohamiltonian graph. In the literature, several important classes of graphs have been shown to contain examples with the above property. This paper investigates a (nontrivial) cl

Intersections of Longest Cycles in k-Con

Intersections of Longest Cycles in k-Connected Graphs

✍ Guantao Chen; Ralph J Faudree; Ronald J Gould 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 279 KB

Let G be a connected graph, where k 2. S. Smith conjectured that every two longest cycles of G have at least k vertices in common. In this note, we show that every two longest cycles meet in at least ck 3Â5 vertices, where cr0.2615. ## 1998 Academic Press In this note, we provide a lower bound on

Longest paths and cycles in bipartite or

Longest paths and cycles in bipartite oriented graphs

✍ Zhang Ke Min 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 430 KB 👁 1 views

In this paper we obtain two sufficient conditions, Ore type (Theorem 1) and Dirac type (Theorem 2). on the degrees of a bipartite oriented graph for ensuring the existence of long paths and cycles. These conditions are shown to be the best possible in a sense. An oriented graph is a digraph without

Chords of longest circuits of graphs emb

Chords of longest circuits of graphs embedded in torus and Klein bottle

✍ Xuechao Li; Cun-Quan Zhang 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 177 KB

## Abstract Thomassen conjectured that every longest circuit of a 3‐connected graph has a chord. It is proved in this paper that every longest circuit of a 4‐connected graph embedded in a torus or Klein bottle has a chord. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 1–23, 2003