New bounds on the k-domination number and the k-tuple domination number

DOI10.1016/J.AML.2006.03.006MaRDI QIDQ2463933zbMATH OpenOpenAlexFDO

Authors Dieter Rautenbach, Lutz Volkmann

Publication date 6 December 2007

Published in Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.aml.2006.03.006

zbMATH Keywords

\(k\)-domination \(k\)-tuple domination domination

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Review text

The \(k\)-domination number \(\gamma_k(G)\) of a graph \(G\) is the cardinality of the smallest set \(D\) of vertices of \(G\) such that every vertex \(v\in V(G)\setminus D\) has at least \(k\) neighbors in \(D\); the \(k\)-tuple domination number \(\gamma_{\times k}\) is the smallest cardinility of a set \(D\) such that every vertex \(v\) of \(G\) has at least \(k\) neighbors in \(D\) (counting itself if \(v\in D\)). The authors prove the following two upper bounds on \(\gamma_k(G)\) and \(\gamma_{\times k}(G)\) for graph \(G\) with minimum degree \(\delta\) satisfying \(\frac{\delta+1}{\ln(\delta+1)}\geq 2k\): \[ \begin{aligned} \gamma_k(G) &\leq \frac{n}{\delta+1}\left(k\ln(\delta+1)+\sum_{i=0}^{k-1} \frac{1}{i!(\delta+1)^{k-1-i}}\right) \quad\text{and}\\ \gamma_{\times k}(G) &\leq \frac{n}{\delta+1}\left(k\ln(\delta+1)+\sum_{i=0}^{k-1} \frac{k-i}{i!(\delta+1)^{k-1-i}}\right).\end{aligned} \] The authors also provide a conjecture on a possible upper bound on \(\gamma_{\times k}(G)\) involving the degree sequence of a graph \(G\) which they verify for \(k=3\) as the case \(k=2\) is an earlier result of \textit{J. Harant} and \textit{M. A. Henning} [Discuss. Math., Graph Theory 25, 29--34 (2005; Zbl 1073.05049)].

Recommendations

Cites work

Cited in

(42)

This page was built for publication: New bounds on the \(k\)-domination number and the \(k\)-tuple domination number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2463933)