zbMATH — the first resource for mathematics

Highly linked tournaments. (English) Zbl 1319.05063
Summary: A (possibly directed) graph is \(k\)-linked if for any two disjoint sets of vertices \(\{x_1,\dots,x_k\}\) and \(\{y_1,\dots,y_k\}\) there are vertex disjoint paths \(P_1,\dots,P_k\) such that \(P_i\) goes from \(x_i\) to \(y_i\). A theorem of B. Bollobás and A. Thomason [Combinatorica 16, No. 3, 313–320 (1996; Zbl 0870.05044)] says that every 22\(k\)-connected (undirected) graph is \(k\)-linked. It is desirable to obtain analogues for directed graphs as well. Although C. Thomassen [“Note on highly connected non-2-linked digraphs”, Combinatorica 11, No. 3, 393–395 (1991)] showed that the Bollobás-Thomason theorem does not hold for general directed graphs, he [“Connectivity in tournaments”, in: B. Bollobás (ed.), Graph theory and combinatorics. Proceedings of the Cambridge combinatorial conference, in honour of Paul Erdős. London: Academic Press. 305–313 (1984)] proved an analogue of the theorem for tournaments – there is a function \(f(k)\) such that every strongly \(f(k)\)-connected tournament is \(k\)-linked. The bound on \(f(k)\) was reduced to \(O(k\log k)\) by D. Kühn et al. [Proc. Lond. Math. Soc. (3) 109, No. 3, 733–762 (2014; Zbl 1302.05069)], who also conjectured that a linear bound should hold. We prove this conjecture, by showing that every strongly \(452k\)-connected tournament is \(k\)-linked.

05C20 Directed graphs (digraphs), tournaments
05C40 Connectivity
Full Text: DOI arXiv
[1] Ajtai, M.; Komlós, J.; Szemerédi, E., Sorting in \(c \log n\) parallel steps, Combinatorica, 3, 1-19, (1983) · Zbl 0523.68048
[2] Bang-Jensen, J., On the 2-linkage problem for semicomplete digraphs, Ann. Discrete Math., 41, 23-38, (1989) · Zbl 0664.05034
[3] 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.; Kim, J.; Osthus, D., Bipartitions of highly connected tournaments, (2014) · Zbl 1346.05094
[6] 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
[7] Kühn, D.; Osthus, D.; Townsend, T., Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths, Combinatorica, (2014), in press
[8] 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
[9] Mader, W., Homomorphieeigenschaften und mittlere kantendichte von graphen, Math. Ann., 174, 265-268, (1967) · Zbl 0171.22405
[10] A. Pokrovskiy, Edge disjoint Hamiltonian cycles in highly connected tournaments, preprint, 2014.
[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, (Bollobás, B., Graph Theory and Combinatorics, a Volume in Honour of Paul Erdős, (1984), Academic Press London), 305-313
[13] 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.