Connected Domination in Plane Triangulations

Abstract

A set of vertices of a graph $G$ such that each vertex of $G$ is either in the set or is adjacent to a vertex in the set is called a dominating set of $G$. If additionally, the set of vertices induces a connected subgraph of $G$ then the set is a connected dominating set of $G$. The domination number $\gamma (G)$ of $G$ is the smallest number of vertices in a dominating set of $G$, and the connected domination number ${\gamma }_c(G)$ of $G$ is the smallest number of vertices in a connected dominating set of $G$. We find the connected domination numbers for all triangulations of up to thirteen vertices. For $n\ge 15$, $n\equiv 0$ (mod 3), we find graphs of order $n$ and ${\gamma }_c=\frac{n}{3}$. We also show that the difference ${\gamma }_c(G)-\gamma (G)$ can be arbitrarily large.

12 pages, 10 figures, 1 table