@techreport{TR-IC-13-22,
number = {IC-13-22},
author = {PatrĂcia F. Hongo and C. N. Campos},
title = {{Dominating sets in planar graphs}},
month = {September},
year = {2013},
institution = {Institute of Computing, University of Campinas},
note = {In English, 18 pages.
\par\selectlanguage{english}\textbf{Abstract}
A dominating set of a graph $G$ is a subset $D\subseteq V(G)$
such that each vertex of $G$ is in $D$ or is adjacent to a
vertex in $D$. The cardinality of a minimum size dominating set
for $G$ is denoted by $\gamma(G)$. In 1996, Tarjan and Matheson
proved that $\gamma(G)\leq n/3$ for triangulated discs and
conjectured that $\gamma(G) \leq n/4$ for triangulated planar
graphs with sufficiently large $n$. In the present work, we
verify the conjecture for two simple classes of triangulated
planar graphs.
}
}