### 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 ε such that, for n sufficiently large, every n-vertex planar graph contains a dominating set of size at most εn. We prove that 1/4 ≤s ε ≤ 1/3, and we conjecture that ε = 1/4. For triangulated discs we obtain a tight bound of ε = 1/3. The upper bound proof yields a linear-time algorithm for finding an (n/3)-size dominating set.

Original language | English (US) |
---|---|

Pages (from-to) | 565-568 |

Number of pages | 4 |

Journal | European Journal of Combinatorics |

Volume | 17 |

Issue number | 6 |

DOIs | |

State | Published - Aug 1996 |

### All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics

## Fingerprint Dive into the research topics of 'Dominating sets in planar graphs'. Together they form a unique fingerprint.

## Cite this

Matheson, L. R., & Tarjan, R. E. (1996). Dominating sets in planar graphs.

*European Journal of Combinatorics*,*17*(6), 565-568. https://doi.org/10.1006/eujc.1996.0048