×

zbMATH — the first resource for mathematics

Partitioning vertices of a tournament into independent cycles. (English) Zbl 1028.05038
Summary: 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 Bollobás.

MSC:
05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bondy, J.A.; Murty, U.S.R., Graph theory with applications, (1976), Macmillan London/New York · Zbl 1134.05001
[2] Reid, K.B., Two complementary circuits in two-connected tournaments, (), 321-334 · Zbl 0573.05031
[3] Reid, K.B., Three problems on tournaments, Graph theory and its applications: east and west, Annals of the New York Academy science, 576, (1989), New York Academy of Science New York, p. 466-473 · Zbl 0792.05062
[4] Song, Z., Complementary cycles of all lengths in tournaments, J. combin. theory ser. B, 57, 18-25, (1993) · Zbl 0723.05062
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.