Lower Bounds on the $p$-Domination Number in Terms of Cycles and Matching Number

Abstract

Let $G$ be a simple graph, and let $p$ be a positive integer. A subset $D\subseteq V(G)$ is a $p$-\emph{dominating set} of the graph $G$ if every vertex $v\in V(G)–D$ is adjacent to at least $p$ vertices of $D$. The $p$-\emph{domination number} ${\gamma }_p(G)$ is the minimum cardinality among the $p$-dominating sets of $G$. Note that the $1$-domination number ${\gamma }_1(G)$ is the usual \emph{domination number} $\gamma (G)$.