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.)
Full Text:
References:
 [1] Abbasi, S., The Solution of the El-Zahar Problem (1998), Rutgers University, PhD thesis [2] 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 [3] 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 [4] 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 [5] Bang-Jensen, J.; Gutin, G., Classes of Directed Graphs, Springer Monographs in Mathematics (2018), Springer · Zbl 1398.05002 [6] Bollobás, B.; Thomason, A., Highly linked graphs, Combinatorica, 16, 3, 313-320 (1996) · Zbl 0870.05044 [7] Camion, P., Chemins et circuits hamiltoniens des graphes complets, C. R. Acad. Sci. Paris, 249, 2151-2152 (1959) · Zbl 0092.15801 [8] 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 [9] 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 [10] 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 [11] Hajnal, P., Partition of graphs with condition on the connectivity and minimum degree, Combinatorica, 3, 1, 95-99 (1983) · Zbl 0529.05030 [12] Kang, D. Y., Sparse highly connected spanning subgraphs in dense directed graphs, Combin. Probab. Comput., 28, 3, 423-464 (2019) [13] 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 [14] 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 [15] Kim, J.; Kühn, D.; Osthus, D., Bipartitions of highly connected tournaments, SIAM J. Discrete Math., 30, 2, 895-911 (2016) · Zbl 1336.05050 [16] 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 [17] 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 [18] 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 [19] 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 [20] Moon, J. W., On subtournaments of a tournament, Canad. Math. Bull., 9, 297-301 (1966) · Zbl 0141.41204 [21] Pokrovskiy, A., Highly linked tournaments, J. Combin. Theory Ser. B, 115, 339-347 (2015) · Zbl 1319.05063 [22] Pokrovskiy, A., Edge disjoint Hamiltonian cycles in highly connected tournaments, Int. Math. Res. Not. IMRN, 2, 429-467 (2017) · Zbl 1405.05097 [23] 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 [24] 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 [25] Song, Z. M., Complementary cycles of all lengths in tournaments, J. Combin. Theory Ser. B, 57, 1, 18-25 (1993) · Zbl 0723.05062 [26] Stiebitz, M., Decomposition of graphs and digraphs, (KAM Series in Discrete Mathematics-Combinatorics-Operations Research-Optimization (1995)), 95-309 [27] Stiebitz, M., Decomposing graphs under degree constraints, J. Graph Theory, 23, 3, 321-324 (1996) · Zbl 0865.05058 [28] Thomassen, C., Hamiltonian-connected tournaments, J. Combin. Theory Ser. B, 28, 2, 142-163 (1980) · Zbl 0435.05026 [29] Thomassen, C., Graph decomposition with constraints on the connectivity and minimum degree, J. Graph Theory, 7, 2, 165-167 (1983) · Zbl 0515.05045 [30] Thomassen, C., Connectivity in tournaments, (Graph Theory and Combinatorics. Graph Theory and Combinatorics, Cambridge, 1983 (1984), Academic Press: Academic Press London), 305-313 [31] 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.