Double Domination in Graphs

Abstract

Each vertex of a graph $G=(V,E)$ is said to dominate every vertex in its closed neighborhood. A set $S\subseteq V$ is a double dominating set for $G$ if each vertex in $V$ is dominated by at least two vertices in $S$. The smallest cardinality of a double dominating set is called the double domination number $dd(G)$. We initiate the study of double domination in graphs and present bounds and some exact values for $dd(G)$. Also, relationships between $dd(G)$ and other domination parameters are explored. Then we extend many results of double domination to multiple domination.