Sparse highly connected spanning subgraphs in dense directed graphs

DOI10.1017/S0963548318000469zbMATH Open1473.05109arXiv1801.01795WikidataQ128913281 ScholiaQ128913281MaRDI QIDQ5222543FDOQ5222543

Authors: Dong Yeap Kang 

Publication date: 6 April 2020

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

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.

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

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.

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)

Cites Work

• Title not available (Why is that?)
• The minimum spanning strong subdigraph problem for extended semicomplete digraphs and semicomplete bipartite digraphs
• Approximating the minimum strongly connected subgraph via a matching lower bound
• Strongly Connected Spanning Subdigraphs with the Minimum Number of Arcs in Quasi-transitive Digraphs
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
• Digraphs
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths
• Title not available (Why is that?)
• Edge disjoint Hamiltonian cycles in highly connected tournaments
• Highly linked tournaments
• Edge-Disjoint Hamiltonian Paths and Cycles in Tournaments
• Tournaments and Semicomplete Digraphs
• Title not available (Why is that?)
• 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
• Minimal n-fach zusammenhängende Digraphen. (Minimally n-connected digraphs)
• Minimally \(k\)-edge-connected directed graphs of maximal size
• Sparse spanning \(k\)-connected subgraphs in tournaments

Cited In (6)

• On sparse subgraphs preserving connectivity properties
• Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties
• Spanning k‐arc‐strong subdigraphs with few arcs in k‐arc‐strong tournaments
• Minimally \(k\)-edge-connected directed graphs of maximal size
• 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)