×

Approximations of the domination number of a graph. (English) Zbl 1390.05160

Summary: Given a graph \(G\), the domination number \(\gamma(G)\) of \(G\) is the minimum order of a set \(S\) of vertices such that each vertex not in \(S\) is adjacent to some vertex in \(S\). Equivalently, label the vertices from \(\{0,1\}\) so that the sum over each closed neighborhood is at least one; the minimum value of the sum of all labels, with this restriction, is the domination number. The fractional domination number \(\gamma_f(G)\) is defined in the same way, except that the vertex labels are chosen from \([0,1]\). Given an ordering of the vertex set of \(G\), let \(\gamma_g(G)\) be the approximation of the domination number by the standard greedy algorithm. Computing the domination number is NP-complete; however, we can bound \(\gamma\) by these two more easily computed parameters: \[ \gamma_f(G)\leq\gamma(G)\leq\gamma_g(G). \] How good are these approximations? Using techniques from the theory of hypergraphs, one can show that, for every graph \(G\) of order \(n\), \[ {\gamma_g(G)\over \gamma_f(G)}= O(\log n). \] On the other hand, we provide examples of graphs for which \(\gamma/\gamma_f= \Theta(\log n)\) and graphs for which \(\gamma_g/\gamma= \Theta(\log n)\). Lastly, we use our examples to compare two bouns on \(\gamma_g\).

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)