Dominating Sets in Planar Graphs

Abstract:

Motivated by an application to unstructured multigrid calculations, we
consider the problem of asymptotically minimizing the size of
dominating sets in triangulated planar graphs. Specifically, we wish
to find the smallest $eps$ such that, for $n$ sufficiently large,
every $n$-vertex planar graph contains a dominating set of size at
most $eps n$. We prove that $frac 14 le eps le frac 13$, and we
conjecture that $eps = frac 14$. For triangulated discs we obtain a
tight bound of $eps = frac 13$. The upper bound proof yields a
linear-time algorithm for finding an $n/3$ - size dominating set.