Premium
On distance r ‐dominating and 2 r ‐independent sets in sparse graphs
Author(s) -
Dvořák Zdeněk
Publication year - 2019
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22426
Subject(s) - mathematics , dominating set , combinatorics , independent set , bounded function , class (philosophy) , constant (computer programming) , set (abstract data type) , discrete mathematics , upper and lower bounds , graph , computer science , mathematical analysis , artificial intelligence , vertex (graph theory) , programming language
Dvořák [European J. Combin. 34 (2013), pp. 833–840] gave a bound on the minimum size of a distance r ‐dominating set in terms of the maximum size of a distance 2 r ‐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 a linear programming (LP)‐based argument inspired by the work of Bansal and Umboh [Inform. Process. Lett. 122 (2017), pp. 21–24].