DIMACS TR: 94-40
Dominating Sets in Planar Graphs
Authors: Lesley R. Matheson, Robert E. Tarjan
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.
Portions of this work were presented at the Twenty-Fourth Annual
Southeastern International Conference on Graph Theory, Combinatorics,
and Computing, Boca Raton, Florida, February 22--26, 1993.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-40.ps
DIMACS Home Page