Domination number of annulus triangulations

Abstract

An {\em annulus triangulation} $G$ is a 2-connected plane graph with two disjoint faces $f_1$ and $f_2$ such that every face other than $f_1$ and $f_2$ are triangular, and that every vertex of $G$ is contained in the boundary cycle of $f_1$ or $f_2$. In this paper, we prove that every annulus triangulation $G$ with $t$ vertices of degree 2 has a dominating set with cardinality at most $\lfloor \frac{|V(G)|+t+1}{4} \rfloor$ if $G$ is not isomorphic to the octahedron. In particular, this bound is best possible.

Keywords

• dominating set
• triangulation
• coloring
• plane graph