Sparse spanning k-connected subgraphs in tournaments

DOI10.1137/16M1064805MaRDI QIDQ5361237zbMATH OpenFDO

Authors Dong Yeap Kang, Younjin Kim, Geewon Suh, Jaehoon 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

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

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.

Recommendations

• Sparse highly connected spanning subgraphs in dense directed graphs
• Spanning k‐arc‐strong subdigraphs with few arcs in k‐arc‐strong tournaments
• Highly linked tournaments
• Spanning Eulerian subdigraphs avoiding \(k\) prescribed arcs in tournaments
• Spanning local tournaments in locally semicomplete digraphs

Cites work

• scientific article; zbMATH DE number 4164908 (Why is no real title available?)
• A linear-time algorithm for finding Hamiltonian cycles in tournaments
• A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs
• Digraphs
• Edge disjoint Hamiltonian cycles in highly connected tournaments
• Graph decomposition with constraints on the connectivity and minimum degree
• Highly linked tournaments
• Network flows. Theory, algorithms, and applications.
• Partition of graphs with condition on the connectivity and minimum degree
• Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs
• Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths
• Spanning k‐arc‐strong subdigraphs with few arcs in k‐arc‐strong tournaments
• Strongly Connected Spanning Subdigraphs with the Minimum Number of Arcs in Quasi-transitive Digraphs

Cited in

(9)

• Tight bounds for powers of Hamilton cycles in tournaments
• Spanning k‐arc‐strong subdigraphs with few arcs in k‐arc‐strong tournaments
• Sparse highly connected spanning subgraphs in dense directed graphs
• 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
• On the spanning connectivity of tournaments
• Spanning Eulerian subdigraphs avoiding \(k\) prescribed arcs 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)