Dominating Sets in Planar Graphs
Report ID: TR-461-94Author: Matheson, Lesley R. / Tarjan, Robert E.
Date: 1994-06-00
Pages: 8
Download Formats: |Postscript|
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.