DIMACS TR: 94-40

Dominating Sets in Planar Graphs

Authors: Lesley R. Matheson, Robert E. Tarjan


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