✦ LIBER ✦

Partitioning Vertices of a Tournament into Independent Cycles

✍ Scribed by Guantao Chen; Ronald J. Gould; Hao Li

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 108 KB
Volume: 83
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2001.2048

No coin nor oath required. For personal study only.

✦ Synopsis

Let k be a positive integer. A strong digraph G is termed k-connected if the removal of any set of fewer than k vertices results in a strongly connected digraph. The purpose of this paper is to show that every k-connected tournament with at least 8k vertices contains k vertex-disjoint directed cycles spanning the vertex set. This result answers a question posed by Bolloba s.

2001 Elsevier Science This article will generally follow the notation and terminology defined in [1]. A digraph is called strongly connected or strong if for every pari of vertices u and v there exists a directed path from u to v and a directed path from v to u. Let k be a positive integer. A digraph G is k-connected if the removal of any set of fewer than k vertices results in a strong digraph. A tournament with n vertices will also be called an n-tournament.

It is well-known that every tournament contains a hamiltonian path and every strong tournament contains a hamiltonian cycle. Reid [2] proved that if T is a 2-connected n-tournament, n 6, that is, T is not the 7-tournament that contains no transitive subtournament with 4 vertices (i.e., the quadratic residue 7-tournament), then T contains two vertex-disjoint cycles

📜 SIMILAR VOLUMES

Partition of a graph into cycles and deg

Partition of a graph into cycles and degenerated cycles

✍ Hikoe Enomoto; Hao Li 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 177 KB

Let G be a graph of order n and k any positive integer with k 6 n. It has been shown by Brandt et al. that if |G| = n ¿ 4k and if the degree sum of any pair of nonadjacent vertices is at least n, then G can be partitioned into k cycles. We prove that if the degree sum of any pair of nonadjacent vert

Partition of a bipartite graph into cycl

Partition of a bipartite graph into cycles

✍ Hong Wang 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 241 KB

Wang, H., Partition of bipartite graph into cycles, Discrete Mathematics 117 (1993) 287-291. El-Zahar (1984) conjectured that if G is a graph on n, + n, + + nk vertices with ni > 3 for 1s i < k and minimum degree 6(G)>rn,/21+rn2/21+ ... +rn,/21, then G contains k vertex-disjoint cycles of lengths n,

Partition of a bipartite hamiltonian gra

Partition of a bipartite hamiltonian graph into two cycles

✍ Denise Amar 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 480 KB

We prove the following theorem. "I'neorem. If G is a balanced bipartite graph with bipartition (A, B), [A I = IBI = n, such that for any x ~ A, y ~ B, d(x) + d(y) >>-n + 2, then for any (nl, n2), ni >I 2, n -----n I + hE, G contains two independent cycles of lengths 2nl and 2n2.

On the existence of specified cycles in

On the existence of specified cycles in a tournament

✍ Abdelhamid Benhocine; A. Pawel Wojda 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 241 KB 👁 1 views

For 2 s p s n and n 2 3, D(n, p) denotes the digraph with n vertices obtained from a directed cycle of length n by changing the orientation of p -1 consecutives edges. In this paper, we prove that every tournament of order n 2 7 contains D(n, p ) for p = 2, 3, ..., n. Furthermore, we determine the t

Partition of a directed bipartite graph

Partition of a directed bipartite graph into two directed cycles

✍ Hong Wang; Charles Little; Kee Teo 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 356 KB

Let D = (V1, V2; A) be a directed bipartite graph with II/11 = 11/21 = n ~> 2. Suppose that do(x) + do(y) >~ 3n + 1 for all xe I/1 and ye V2. Then D contains two vertex-disjoint directed cycles of lengths 2nl and 2n2, respectively, for any positive integer partition n = n~ + n2. Moreover, the condit

Cycles containing all vertices of maximu

Cycles containing all vertices of maximum degree

✍ H. J. Broersma; J. Den Van Heuvel; H. A. Jung; H. J. Veldman 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 539 KB

## Abstract For a graph __G__ and an integer __k__, denote by __V__~__k__~ the set {__v__ ∈ __V__(__G__) | __d__(__v__) ≥ __k__}. Veldman proved that if __G__ is a 2‐connected graph of order __n__ with __n__ ≤ __3k ‐ 2__ and |__V__~__k__~| ≤ __k__, then __G__ has a cycle containing all vertices of