×

An improved linear connectivity bound for tournaments to be highly linked. (English) Zbl 1471.05040

Summary: A digraph 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\) is directed from \(x_i\) to \(y_i\) for \(i=1,\dots,k\). A. Pokrovskiy [J. Comb. Theory, Ser. B 115, 339–347 (2015; Zbl 1319.05063)] proved that every strongly \(452 k\)-connected tournament is \(k\)-linked. In this paper, we significantly reduce this connectivity bound and show that any \((40k-31)\)-connected tournament is \(k\)-linked.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C40 Connectivity

Citations:

Zbl 1319.05063
PDFBibTeX XMLCite
Full Text: DOI

References:

[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
[3] A. Girão, K. Popielarz, R. Snyder, \( ( 2 k + 1 )\)-connected tournaments with large minimum out-degree are \(k\)-linked, arXiv:1912.00710v1. · Zbl 1457.05042
[4] Jung, H. A., Verallgemeinerung des \(n\)-fachen Zusammenhangs für Graphen, Math. Ann., 187, 95-103 (1970) · Zbl 0184.27601
[5] Kawarabayashi, K., On the connectivity of minimum and minimal counterexamples to Hadwiger’s conjecture, J. Combin. Theory, Ser. B, 97, 1, 144-150 (2007) · Zbl 1107.05034
[6] Kawarabayashi, K.; Kostochka, A.; Yu, G., On sufficient degree conditions for a graph to be \(k\)-linked, Combin. Probab. Comput., 15, 685-694 (2006) · Zbl 1109.05061
[7] Kawarabayashi, K.; Yu, G., Connectivities for \(k\)-knitted graphs and for minimal counterexamples to Hadwiger’s conjecture, J. Combin. Theory, Ser. B, 103, 320-326 (2013) · Zbl 1301.05199
[8] 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
[9] 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, 451-469 (2016) · Zbl 1389.05058
[10] 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
[11] Ore, O., Graphs and matching theorems, Duke Math. J., 22, 4, 625-639 (1955) · Zbl 0068.16301
[12] Pokrovskiy, A., Highly linked tournaments, J. Combin. Theory, Ser. B, 115, 339-347 (2015) · Zbl 1319.05063
[13] Thomas, R.; Wollan, P., An improved linear edge bound for graph linkages, European J. Combin., 26, 309-324 (2005) · Zbl 1056.05091
[14] Thomas, R.; Wollan, P., The extremal function for 3-linked graphs, J. Combin. Theory, Ser. B, 98, 939-971 (2008) · Zbl 1171.05030
[15] Thomassen, C., Note on highly connected non-\(2\)-linked digraphs, Combinatorica, 11, 393-395 (1991) · Zbl 0746.05030
[16] Thomassen, C.; tournaments, Connectivity.in., 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 · Zbl 0546.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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.