Sparse Spanning k-Connected Subgraphs in Tournaments

DOI10.1137/16M1064805zbMATH Open1371.05104arXiv1603.02474MaRDI QIDQ5361237FDOQ5361237

Dong Yeap Kang, Jaehoon Kim, Younjin Kim, Geewon Suh

Publication date: 27 September 2017

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

Abstract: In 2009, Bang-Jensen asked whether there exists a function $g(k)$ such that every strongly $k$-connected $n$-vertex tournament contains a strongly $k$-connected spanning subgraph with at most $kn+g(k)$ arcs. In this paper, we answer the question by showing that every strongly $k$-connected $n$-vertex tournament contains a strongly $k$-connected spanning subgraph with at most $kn+750k^{2}log(k+1)$ arcs.

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

zbMATH Keywords

connectivitytournamentsubgraph

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• Sparse Highly Connected Spanning Subgraphs in Dense Directed Graphs
• Tight bounds for powers of Hamilton cycles in tournaments
• Tournaments and Semicomplete Digraphs
• On 1-factors with prescribed lengths in tournaments
• Spanning acyclic subdigraphs and strong \(t\)-panconnectivity of tournaments
• \(k\)-ary spanning trees contained in tournaments

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

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