Highly linked tournaments

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

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

(16)

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