On distance r-dominating and 2r-independent sets in sparse graphs

DOI10.1002/JGT.22426MaRDI QIDQ5379844zbMATH OpenOpenAlexFDO

Authors Zdeněk Dvořák

Publication date 14 June 2019

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

dominating setindependent setlinear programming

Mathematics Subject Classification ID

Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Linear programming (90C05)

Abstract: Dvorak (2013) gave a bound on the minimum size of a distance r dominating set in the terms of the maximum size of a distance 2r independent set and generalized coloring numbers, thus obtaining a constant factor approximation algorithm for the parameters in any class of graphs with bounded expansion. We improve and clarify this dependence using an LP-based argument inspired by the work of Bansal and Umboh (2017).

Recommendations

• On distance connected domination numbers of graphs.
• Distance domination in graphs with given minimum and maximum degree
• On the distance domination number of bipartite graphs
• A note on distance domination numbers of graphs
• Distance domination and distance irredundance in graphs

Cited in

(14)

• Constant-factor approximation of the domination number in sparse graphs
• Local planar domination revisited
• Vertex cover at distance on \(H\)-free graphs
• Improved bounds for weak coloring numbers
• Kernelization and approximation of distance-r independent sets on nowhere dense graphs
• Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
• A note of independent number and domination number of \(Q_{n, k, m}\)-graph
• Progressive algorithms for domination and independence
• Algorithmic properties of sparse digraphs
• Domination above \(r\)-independence: does sparseness help?
• Distributed distance-r covering problems on sparse high-girth graphs
• scientific article; zbMATH DE number 7764102 (Why is no real title available?)
• Distributed domination on sparse graph classes
• Near-optimal distributed dominating set in bounded arboricity graphs

This page was built for publication: On distance \(r\)-dominating and \(2r\)-independent sets in sparse graphs

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