×

zbMATH — the first resource for mathematics

Complementary cycles of all lengths in tournaments. (English) Zbl 0723.05062
K. B. Reid discussed a problem, originally posed by Bollobas, as follows:
Problem 1. Let m be a positive integer. What is the least integer g(m) so that all but a finite number of g(m)-connected tournaments contain m vertex-disjoint cycles that include all vertices?
Clearly, \(g(1)=1\). Reid proved that \(g(2)=2\). For \(m\geq 3\), the problem remains open. Reid has proved that \(m\leq g(m)\leq 3m-4\). This paper poses a further problem.
Let \(n_ 1,n_ 2,...,n_ m\), be m positive integers. If they satisfy (A) \(n_ i\geq 3\), \(i=1,2,...,m\) and \(\sum^{m}_{i=1}n_ i=n\), we say that they are a solution of (A).
Problem 2. Let m be a positive integer. What is the least integer f(m) so that, for any solution of (A), all but a finite number of f(m)-connected tournaments contain m vertex-disjoint cycles of lengths \(n_ 1,n_ 2,...,n_ m?\)
Clearly, \(f(1)=g(1)\) and g(m)\(\leq f(m)\). This paper makes the following conjecture.
Conjecture 3. For all m, \(g(m)=f(m)\). We prove that \(f(2)=2\). This implies the conjecture holds for \(m=1\) or 2.

MSC:
05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
PDF BibTeX XML Cite
Full Text: DOI