Efficient Domination in Cayley Graphs

Yunping Deng

Department of Mathematics, Shanghai University of Electric Power, Shanghai, 200090, China

dyp612@hotmail.com

Abstract: An E-chain is a countable family of nested graphs, each of which has an efficient dominating set. In this paper, we construct two E-chains of circulant graphs, which are Cayley graphs on finite cyclic groups. In addition, we give a necessary and sufficient condition for the existence of efficient dominating sets in any Cayley graphs.

Keywords: Circulant graph; Cayley graph; Efficient dominating set