✦ LIBER ✦

Disjoint cycles with chords in graphs

✍ Scribed by Ch. Sobhan Babu; Ajit A. Diwan

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 134 KB
Volume: 60
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20349

No coin nor oath required. For personal study only.

✦ Synopsis

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',H_2',\ldots,H_k'$, where $H_i'=H_i$, if $H_i$ is a tree, and $H_i'$ is a cycle with $n_i-3$ chords incident with a common vertex, if $H_i$ is a cycle. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 87–98, 2009

📜 SIMILAR VOLUMES

Edge disjoint cycles in graphs

✍ Li Hao 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 419 KB

Disjoint cycles in star-free graphs

✍ Markus, Lisa R.; Snevily, Hunter S. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 322 KB 👁 3 views

A graph is claw-free if it does not contain K l , 3 as an induced subgraph. It is Kl,,-free if it does not contain K l , r as an induced subgraph. We show that if a graph is Kl,,-free ( r 2 4), only p + 2r -1 edges are needed to insure that G has t w o disjoint cycles. As an easy consequence w e ge

Edge disjoint Hamilton cycles in graphs

✍ Guojun Li 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB 👁 2 views

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

Edge-disjoint cycles in regular directed

Edge-disjoint cycles in regular directed graphs

✍ Alon, Noga; McDiarmid, Colin; Molloy, Michael 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 356 KB 👁 3 views

We prove that any k-regular directed graph with no parallel edges contains a collection of at least fl(k2) edge-disjoint cycles; we conjecture that in fact any such graph contains a collection of at least ( lCi1 ) disjoint cycles, and note that this holds for k 5 3. o 1996

Directed cycles with chords

✍ Marcus, Daniel A. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 249 KB

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.