×

Bounds of the 2-domination number of graphs. (English) Zbl 1113.05072

Let \(p\) be a positive integer. A set \(S\) of vertices of a graph \(G=(V, E)\) is a \(p\)-dominating set of \(G\) if, for every vertex \(v\in V\setminus S\), \(| N(v) \cap S| \geq p\). The \(p\)-domination number \(\gamma_p(G)\) is the minimum cardinality among the \(p\)-dominating sets of \(G\). Among others, the authors show that \(\gamma_2(G)\leq\frac{| V| +\gamma_1(G)}{2}\) for all graphs \(G\) with minimum degree \(\geq 2\), and that \(\gamma_2(G)\) is at least the independence number of \(G\) for all block graphs \(G\) and all graphs \(G\) with at most one cycle.

MSC:

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