Total Efficient Domination and Cayley Graphs

Abstract

A set $S\subseteq V$ is a dominating set of a graph $G=(V,E)$ if each vertex in $V$ is either in $S$ or is adjacent to a vertex in $S$. A vertex is said to dominate itself and all its neighbors. A set $S\subseteq V$ is a $totaldominatingset$ of a graph $G=(V,E)$ if each vertex in $V$ is adjacent to a vertex in $S$. In total domination, a vertex no longer dominates itself. These two types of domination can be thought of as representing the vertex set of a graph as the union of the closed (domination) and open (total domination) neighborhoods of the vertices in the set $S$. A set $S\subseteq V$ is a $total,efficientdominatingset$ (also known as an $efficientopendominatingset$) of a graph $G=(V,E)$ if each vertex in $V$ is adjacent to exactly one vertex in $S$. In 2002, Gavlas and Schultz completely classified all cycle graphs that admit a total, efficient dominating set. This paper extends their result to two classes of Cayley graphs.