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
Keywords:
tournaments; vertex-disjoint cycles
Full Text: