Sparse Spanning $k$-Connected Subgraphs in Tournaments

DOI10.1137/16M1064805zbMath1371.05104arXiv1603.02474MaRDI QIDQ5361237

Dong Yeap Kang, Younjin Kim, Geewon Suh, Jae-Hoon Kim

Publication date: 27 September 2017

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

connectivitytournamentsubgraph

Mathematics Subject Classification ID

Graph polynomials (05C31) Extremal problems in graph theory (05C35) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Density (toughness, etc.) (05C42)

Related Items (4)

On 1-factors with prescribed lengths in tournaments ⋮ Sparse Highly Connected Spanning Subgraphs in Dense Directed Graphs ⋮ Tournaments and Semicomplete Digraphs ⋮ Tight bounds for powers of Hamilton cycles in tournaments

Cites Work

• Unnamed Item
• Unnamed Item
• Bipartitions of highly connected tournaments
• Highly linked tournaments
• Partition of graphs with condition on the connectivity and minimum degree
• Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs
• A linear-time algorithm for finding Hamiltonian cycles in tournaments
• Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths
• Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments
• Graph decomposition with constraints on the connectivity and minimum degree
• A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs
• Strongly Connected Spanning Subdigraphs with the Minimum Number of Arcs in Quasi-transitive Digraphs
• Edge Disjoint Hamiltonian Cycles in Highly Connected Tournaments
• Spanning k‐arc‐strong subdigraphs with few arcs in k‐arc‐strong tournaments
• Digraphs

This page was built for publication: Sparse Spanning $k$-Connected Subgraphs in Tournaments