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) \).