Global Domination in Planar Graphs

Abstract

For any graph $G=(V,E)$, $D\subseteq V$ is a global dominating set if $D$ dominates both $G$ and its complement $\overline{G}$. The global domination number ${\gamma }_g(G)$ of a graph $G$ is the fewest number of vertices required of a global dominating set. In general,$max\{\gamma (G),\gamma (\overline{G})\}\le {\gamma }_g(G)\le \gamma (G)+\gamma (\overline{G}),$ where $\gamma (G)$ and $\gamma (\overline{G})$ are the respective domination numbers of $G$ and $\overline{G}$. We show that when $G$ is a planar graph, ${\gamma }_g(G)\le max\{\gamma (G)+1,4\}.$