# Dominating Sets in Planar Graphs

Report ID:

TR-461-94

Authors:

Date:

May 1994

Pages:

8

Download Formats:

#### 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.