Sparse highly connected spanning subgraphs in dense directed graphs

DOI10.1017/S0963548318000469MaRDI QIDQ5222543zbMATH OpenWikidataFDO

Authors Dong Yeap Kang

Publication date 6 April 2020

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

densitydigraphspanning subgraph$k$-arc-connected directed multigraph$k$-connected digraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Density (toughness, etc.) (05C42)

Abstract: Mader proved that every strongly $k$-connected $n$-vertex digraph contains a strongly $k$-connected spanning subgraph with at most $2kn-2k^2$ edges, where the equality holds for the complete bipartite digraph ${DK}_{k,n-k}$. For dense strongly $k$-connected digraphs, this upper bound can be significantly improved. More precisely, we prove that every strongly $k$-connected $n$-vertex digraph $D$ contains a strongly $k$-connected spanning subgraph with at most $kn+800k(k+overlineDelta(D))$ edges, where $overlineDelta(D)$ denotes the maximum degree of the complement of the underlying undirected graph of a digraph $D$. Here, the additional term $800k(k+overlineDelta(D))$ is tight up to multiplicative and additive constants. As a corollary, this implies that every strongly $k$-connected $n$-vertex semicomplete digraph contains a strongly $k$-connected spanning subgraph with at most $kn+800k^2$ edges, which is essentially optimal since $800k^2$ cannot be reduced to the number less than $k(k-1)/2$. We also prove an analogous result for strongly $k$-arc-connected directed multigraphs. Both proofs yield polynomial-time algorithms.

Recommendations

• Sparse spanning \(k\)-connected subgraphs in tournaments
• Spanning k‐arc‐strong subdigraphs with few arcs in k‐arc‐strong tournaments
• Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties
• On sparse subgraphs preserving connectivity properties
• Directed proper connection number and almost spanning subgraphs.

Cites work

• scientific article; zbMATH DE number 3572198 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 878899 (Why is no real title available?)
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
• Approximating the minimum strongly connected subgraph via a matching lower bound
• Digraphs
• Edge disjoint Hamiltonian cycles in highly connected tournaments
• Edge-Disjoint Hamiltonian Paths and Cycles in Tournaments
• Highly linked tournaments
• Minimal n-fach zusammenhängende Digraphen. (Minimally n-connected digraphs)
• Minimally \(k\)-edge-connected directed graphs of maximal size
• 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
• Sparse spanning \(k\)-connected subgraphs in tournaments
• Strongly Connected Spanning Subdigraphs with the Minimum Number of Arcs in Quasi-transitive Digraphs
• The minimum spanning strong subdigraph problem for extended semicomplete digraphs and semicomplete bipartite digraphs
• Tournaments and Semicomplete Digraphs

Cited in

(6)

• On sparse subgraphs preserving connectivity properties
• Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties
• Minimally \(k\)-edge-connected directed graphs of maximal size
• Spanning k‐arc‐strong subdigraphs with few arcs in k‐arc‐strong tournaments
• On 1-factors with prescribed lengths in tournaments
• Sparse spanning \(k\)-connected subgraphs in tournaments

This page was built for publication: Sparse highly connected spanning subgraphs in dense directed graphs

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