Lower Bounds on the \(p\)-Domination Number in Terms of Cycles and Matching Number

Adriana Hansberg1, Lutz Volkmann1
1Lehrstuhl II fiir Mathematik, RWTH Aachen University, 52056 Aachen, Germany

Abstract

Let \( G \) be a simple graph, and let \( p \) be a positive integer. A subset \( D \subseteq V(G) \) is a \( p \)-\({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 \)-\({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 \({domination\; number}\) \( \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) \geq 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) \geq \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\).

Keywords: Domination; p-domination; Multiple domination; Cac- tus graph; Matching number