Partitioning vertices of a tournament into independent cycles.

*(English)*Zbl 1028.05038Summary: 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

\textit{G. Chen} et al., J. Comb. Theory, Ser. B 83, No. 2, 213--220 (2001; Zbl 1028.05038)

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.