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$-$dominatingset$ of the graph $G$ if every vertex $v\in V(G)–D$ is adjacent to at least $p$ vertices of $D$. The $p$-$dominationnumber$ ${\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 $dominationnumber$ $\gamma (G)$.
In $1985$, Fink and Jacobson showed that for every graph $G$ with $n$ vertices and $m$ edges the inequality $y$,${\gamma }_p(G)\ge n—m/p$ holds. In this paper we present a generalization of this theorem and analyze the $2$-domination number ${\gamma }_2$ in cactus graphs $G$ with respect on its relation to the matching number ${\alpha }_0$ and the number of odd or rather even cycles in $G$. Further we show that ${\gamma }_2(G)\ge \alpha (G)$ for the cactus graphs $G$ with at most one even cycle and characterize those which
fulfill ${\gamma }_2(G)=\alpha (G)$ or rather ${\gamma }_2(G)=\alpha (G)+1$.