zbMATH — the first resource for mathematics

Highly linked tournaments with large minimum out-degree. (English) Zbl 1428.05123
Summary: We prove that there exists a function \(f : \mathbb{N} \to \mathbb{N}\) such that for any positive integer \(k\), if \(T\) is a strongly \(4k\)-connected tournament with minimum out-degree at least \(f(k)\), then \(T\) is \(k\)-linked. This resolves a conjecture of A. Pokrovskiy [ibid. 115, 339–347 (2015; Zbl 1319.05063)] up to a factor of 2 of the required connectivity. Along the way, we show that a tournament with sufficiently large minimum out-degree contains a subdivision of a complete directed graph. This result may be of independent interest.

05C20 Directed graphs (digraphs), tournaments
05C40 Connectivity
Full Text: DOI arXiv
[1] Bang-Jensen, J., On the 2-linkage problem for semicomplete digraphs, Ann. Discrete Math., 41, 23-38 (1989) · Zbl 0664.05034
[2] Bollobás, B.; Thomason, A., Highly linked graphs, Combinatorica, 16, 313-320 (1996) · Zbl 0870.05044
[4] Jung, H. A., Verallgemeinerung des n-fachen zusammenhangs für graphen, Math. Ann., 187, 95-103 (1970) · Zbl 0184.27601
[5] 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., 109, 733-762 (2014) · Zbl 1302.05069
[6] Larman, D. G.; Mani, P., On the existence of certain configurations within graphs and the 1-skeletons of polytopes, Proc. Lond. Math. Soc., 20, 144-160 (1974) · Zbl 0201.56801
[7] Lichiardopol, N., Vertex-disjoint subtournaments of prescribed minimum outdegree or minimum semidegree: proof for tournaments of a conjecture of Stiebitz, Int. J. Comb., 2012 (2012), 9 pp. · Zbl 1236.05095
[8] Mader, W., Homomorphieeigenschaften und mittlere Kantendichte von Graphen, Math. Ann., 174, 265-268 (1967) · Zbl 0171.22405
[9] Mader, W., Degree and local connectivity in digraphs, Combinatorica, 5, 2, 161-165 (1985) · Zbl 0576.05044
[10] Pokrovskiy, A., Highly linked tournaments, J. Combin. Theory Ser. B, 115, 339-347 (2015) · Zbl 1319.05063
[11] Thomas, R.; Wollan, P., An improved extremal function for graph linkages, European J. Combin., 26, 309-324 (2005) · Zbl 1056.05091
[12] Thomassen, C., Connectivity in tournaments, (Graph Theory and Combinatorics. Graph Theory and Combinatorics, A Volume in Honour of Paul Erdős (1984), Academic Press: Academic Press London), 305-313
[13] Thomassen, C., Even cycles in directed graphs, European J. Combin., 6, 85-89 (1985) · Zbl 0606.05039
[14] Thomassen, C., Note on highly connected non-2-linked digraphs, Combinatorica, 11, 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.