# zbMATH — the first resource for mathematics

On 1-factors with prescribed lengths in tournaments. (English) Zbl 1430.05048
Summary: We prove that every strongly $$10^{50} t$$-connected tournament contains all possible 1-factors with at most $$t$$ components and this is best possible up to constant. In addition, we can ensure that each cycle in the 1-factor contains a prescribed vertex. This answers a question by D. Kühn et al. [Combinatorica 36, No. 4, 451–469 (2016; Zbl 1389.05058)].
Indeed, we prove more results on partitioning tournaments. We prove that a strongly $$\Omega(k^4 t q)$$-connected tournament admits a vertex partition into $$t$$ strongly $$k$$-connected tournaments with prescribed sizes such that each tournament contains $$q$$ prescribed vertices, provided that the prescribed sizes are $$\Omega(n)$$. This result improves the earlier result of Kühn et al. [loc. cit.]. We also prove that for a strongly $$\Omega(t)$$-connected $$n$$-vertex tournament $$T$$ and given $$2t$$ distinct vertices $$x_1, \ldots, x_t, y_1, \ldots, y_t$$ of $$T$$, we can find $$t$$ vertex disjoint paths $$P_1, \ldots, P_t$$ such that each path $$P_i$$ connecting $$x_i$$ and $$y_i$$ has the prescribed length, provided that the prescribed lengths are $$\Omega(n)$$. For both results, the condition of connectivity being linear in $$t$$ is best possible, and the condition of prescribed sizes being $$\Omega(n)$$ is also best possible.
##### MSC:
 05C20 Directed graphs (digraphs), tournaments 05C38 Paths and cycles 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
##### Keywords:
tournament; connectivity; 1-factor; cycle; graph partition
Full Text: