Highly linked tournaments

DOI10.1016/J.JCTB.2015.05.005zbMATH Open1319.05063arXiv1406.7552OpenAlexW433207136MaRDI QIDQ491002FDOQ491002

Alexey Pokrovskiy

Publication date: 21 August 2015

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: 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 Bollob'as and Thomason says that every $22k$-connected (undirected) graph is $k$-linked. It is desirable to obtain analogues for directed graphs as well. Although Thomassen showed that the Bollob'as-Thomason Theorem does not hold for general directed graphs, he 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(klogk)$ by K"uhn, Lapinskas, Osthus, and Patel, who also conjectured that a linear bound should hold. We prove this conjecture, by showing that every strongly $452k$-connected tournament is $k$-linked.

Full work available at URL: https://arxiv.org/abs/1406.7552

Recommendations

• An improved linear connectivity bound for tournaments to be highly linked
• Highly linked tournaments with large minimum out-degree
• \((2k+1)\)-connected tournaments with large minimum out-degree are \(k\)-linked
• Every \((13k - 6)\)-strong tournament with minimum out-degree at least \(28k - 13\) is \(k\)-linked
• Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments

zbMATH Keywords

connectivity of tournamentslinkage structureslinkedness

Mathematics Subject Classification ID

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

Cites Work

• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• An improved linear edge bound for graph linkages
• Sorting in \(c \log n\) parallel steps
• Highly linked graphs
• Eine Verallgemeinerung des \(n\)-fachen Zusammenhangs für Graphen
• Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments
• Bipartitions of highly connected tournaments
• Title not available (Why is that?)
• Title not available (Why is that?)
• Highly connected non-2-linked digraphs
• On the Existence of Certain Configurations within Graphs and the 1-Skeletons of Polytopes

Cited In (15)

• Subdivisions of digraphs in tournaments
• Sparse Highly Connected Spanning Subgraphs in Dense Directed Graphs
• Every \((13k - 6)\)-strong tournament with minimum out-degree at least \(28k - 13\) is \(k\)-linked
• Characterization of \(k\)-subconnected graphs
• Sparse Spanning $k$-Connected Subgraphs in Tournaments
• Bipartitions of highly connected tournaments
• Strong complete minors in digraphs
• Title not available (Why is that?)
• Tournaments and Semicomplete Digraphs
• \((2k+1)\)-connected tournaments with large minimum out-degree are \(k\)-linked
• On 1-factors with prescribed lengths in tournaments
• Highly linked tournaments with large minimum out-degree
• Title not available (Why is that?)
• Improved results on linkage problems
• An improved linear connectivity bound for tournaments to be highly linked

This page was built for publication: Highly linked tournaments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q491002)