# 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:
##### References:
  Abbasi, S., The Solution of the El-Zahar Problem (1998), Rutgers University, PhD thesis  Amar, D.; Raspaud, A., Covering the vertices of a digraph by cycles of prescribed length, Discrete Math., 87, 2, 111-118 (1991) · Zbl 0764.05070  Bang-Jensen, J.; Guo, Y.; Yeo, A., Complementary cycles containing prescribed vertices in tournaments, Discrete Math., 214, 1-3, 77-87 (2000) · Zbl 0945.05029  Bang-Jensen, J.; Gutin, G., Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics (2009), Springer-Verlag London, Ltd.: Springer-Verlag London, Ltd. London · Zbl 1170.05002  Bang-Jensen, J.; Gutin, G., Classes of Directed Graphs, Springer Monographs in Mathematics (2018), Springer · Zbl 1398.05002  Bollobás, B.; Thomason, A., Highly linked graphs, Combinatorica, 16, 3, 313-320 (1996) · Zbl 0870.05044  Camion, P., Chemins et circuits hamiltoniens des graphes complets, C. R. Acad. Sci. Paris, 249, 2151-2152 (1959) · Zbl 0092.15801  Chen, G.; Gould, R. J.; Li, H., Partitioning vertices of a tournament into independent cycles, J. Combin. Theory Ser. B, 83, 2, 213-220 (2001) · Zbl 1028.05038  Girão, A.; Snyder, R., Highly linked tournaments with large minimum out-degree, J. Combin. Theory Ser. B, 139, 251-266 (2019) · Zbl 1428.05123  Guo, Y., Spanning local tournaments in locally semicomplete digraphs, 4th Twente Workshop on Graphs and Combinatorial Optimization. 4th Twente Workshop on Graphs and Combinatorial Optimization, Enschede, 1995. 4th Twente Workshop on Graphs and Combinatorial Optimization. 4th Twente Workshop on Graphs and Combinatorial Optimization, Enschede, 1995, Discrete Appl. Math., 79, 1-3, 119-125 (1997) · Zbl 0884.05047  Hajnal, P., Partition of graphs with condition on the connectivity and minimum degree, Combinatorica, 3, 1, 95-99 (1983) · Zbl 0529.05030  Kang, D. Y., Sparse highly connected spanning subgraphs in dense directed graphs, Combin. Probab. Comput., 28, 3, 423-464 (2019)  Kang, D. Y.; Kim, J.; Kim, Y.; Suh, G., Sparse spanning k-connected subgraphs in tournaments, SIAM J. Discrete Math., 31, 3, 2206-2227 (2017) · Zbl 1371.05104  Keevash, P.; Sudakov, B., Triangle packings and 1-factors in oriented graphs, J. Combin. Theory Ser. B, 99, 1, 709-727 (2009) · Zbl 1208.05038  Kim, J.; Kühn, D.; Osthus, D., Bipartitions of highly connected tournaments, SIAM J. Discrete Math., 30, 2, 895-911 (2016) · Zbl 1336.05050  Kühn, D.; Lapinskas, J.; Osthus, D.; Patel, V., Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments, Proc. Lond. Math. Soc. (3), 109, 3, 733-762 (2014) · Zbl 1302.05069  Kühn, D.; Osthus, D., Partitions of graphs with high minimum degree or connectivity, J. Combin. Theory Ser. B, 88, 1, 29-43 (2003) · Zbl 1045.05075  Kühn, D.; Osthus, D.; Townsend, T., Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths, Combinatorica, 36, 4, 451-469 (2016) · Zbl 1389.05058  Lichiardopol, N., Vertex-disjoint subtournaments of prescribed minimum outdegree or minimum semidegree: proof for tournaments of a conjecture of Stiebitz, Int. J. Comb., Article 273416 pp. (2012) · Zbl 1236.05095  Moon, J. W., On subtournaments of a tournament, Canad. Math. Bull., 9, 297-301 (1966) · Zbl 0141.41204  Pokrovskiy, A., Highly linked tournaments, J. Combin. Theory Ser. B, 115, 339-347 (2015) · Zbl 1319.05063  Pokrovskiy, A., Edge disjoint Hamiltonian cycles in highly connected tournaments, Int. Math. Res. Not. IMRN, 2, 429-467 (2017) · Zbl 1405.05097  Reid, K. B., Two complementary circuits in two-connected tournaments, (Cycles in Graphs. Cycles in Graphs, Burnaby, B.C., 1982. Cycles in Graphs. Cycles in Graphs, Burnaby, B.C., 1982, North-Holland Math. Stud., vol. 115 (1985), North-Holland: North-Holland Amsterdam), 321-334  Reid, K. B., Three problems on tournaments, (Graph Theory and Its Applications: East and West. Graph Theory and Its Applications: East and West, Jinan, 1986. Graph Theory and Its Applications: East and West. Graph Theory and Its Applications: East and West, Jinan, 1986, Ann. New York Acad. Sci., vol. 576 (1989), New York Acad. Sci.: New York Acad. Sci. New York), 466-473 · Zbl 0792.05062  Song, Z. M., Complementary cycles of all lengths in tournaments, J. Combin. Theory Ser. B, 57, 1, 18-25 (1993) · Zbl 0723.05062  Stiebitz, M., Decomposition of graphs and digraphs, (KAM Series in Discrete Mathematics-Combinatorics-Operations Research-Optimization (1995)), 95-309  Stiebitz, M., Decomposing graphs under degree constraints, J. Graph Theory, 23, 3, 321-324 (1996) · Zbl 0865.05058  Thomassen, C., Hamiltonian-connected tournaments, J. Combin. Theory Ser. B, 28, 2, 142-163 (1980) · Zbl 0435.05026  Thomassen, C., Graph decomposition with constraints on the connectivity and minimum degree, J. Graph Theory, 7, 2, 165-167 (1983) · Zbl 0515.05045  Thomassen, C., Connectivity in tournaments, (Graph Theory and Combinatorics. Graph Theory and Combinatorics, Cambridge, 1983 (1984), Academic Press: Academic Press London), 305-313  Thomassen, C., Highly connected non-2-linked digraphs, Combinatorica, 11, 4, 393-395 (1991) · Zbl 0746.05030
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.