✦ LIBER ✦

Directed cycles with chords

✍ Scribed by Marcus, Daniel A.

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 249 KB
Volume: 31
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199905)31:1<17::aid-jgt3>3.0.co;2-q

No coin nor oath required. For personal study only.

✦ Synopsis

Using a variation of Thomassen's admissible triples technique, we give an alternative proof that every strongly 2-arc-connected directed graph with two or more vertices contains a directed cycle that has at least two chords, while at the same time establishing a more general result.

📜 SIMILAR VOLUMES

Directed Cycles with Two Chords and Stro

Directed Cycles with Two Chords and Strong Spanning Directed Subgraphs with Few Arcs

✍ Carsten Thomassen 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 314 KB

We prove the conjecture of D. A. Marcus (1981) that every strongly 2-arcconnected directed graph has a directed cycle with at least two chords. As a consequence, every strongly 2-arc-connected directed graph with m arcs has a spanning strong directed subgraph with less than 2 3 m arcs. The constant

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 and their chords

✍ Cun-Quan Zhang 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 386 KB

Thomassen conjectured that any longest cycle of a 3-connected graph has a chord. In this paper, we will show that the conjecture is true for a planar graph if it is cubic or 6 2 4.

Cycles with a chord are graceful

✍ C. Delorme; M. Maheo; H. Thuillier; K. M. Koh; H. K. Teo 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 162 KB

## Abstract In this paper, we prove that every cycle plus a chord is graceful, thus answering a conjecture of R. Bodendiek, H. Schumacher, and H. Wegner.

Chords of Longest Cycles in Cubic Graphs

✍ Carsten Thomassen 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 213 KB

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

Disjoint Directed Cycles

✍ Noga Alon 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 295 KB

It is shown that there exists a positive = so that for any integer k, every directed graph with minimum outdegree at least k contains at least =k vertex disjoint cycles. On the other hand, for every k there is a digraph with minimum outdegree k which does not contain two vertex or edge disjoint cycl