Highly linked tournaments

DOI10.1016/J.JCTB.2015.05.005MaRDI QIDQ491002zbMATH OpenOpenAlexFDO

Authors Alexey Pokrovskiy

Publication date 21 August 2015

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

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

zbMATH Keywords

connectivity of tournamentslinkage structureslinkedness

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 3869359 (Why is no real title available?)
• scientific article; zbMATH DE number 4085689 (Why is no real title available?)
• An improved linear edge bound for graph linkages
• Eine Verallgemeinerung des n-fachen Zusammenhangs für Graphen
• Highly connected non-2-linked digraphs
• Highly linked graphs
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• On the Existence of Certain Configurations within Graphs and the 1-Skeletons of Polytopes
• Sorting in \(c \log n\) parallel steps

Cited in

(19)

• Subdivisions of digraphs in tournaments
• Every (13k - 6)-strong tournament with minimum out-degree at least 28k - 13 is k-linked
• Characterization of \(k\)-subconnected graphs
• Strong complete minors in digraphs
• scientific article; zbMATH DE number 1992747 (Why is no real title available?)
• Sparse highly connected spanning subgraphs in dense directed graphs
• Counterexamples to the linkage conjecture for tournaments
• Tournaments and Semicomplete Digraphs
• A new connectivity bound for a tournament to be highly linked
• On the k-linkage problem for generalizations of 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
• Sparse spanning \(k\)-connected subgraphs in tournaments
• Edge disjoint Hamiltonian cycles in highly connected tournaments
• scientific article; zbMATH DE number 3959460 (Why is no real title available?)
• Improved results on linkage problems
• An improved linear connectivity bound for tournaments to be highly linked
• Intrinsic linking and knotting in tournaments

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)