Distance domination and distance irredundance in graphs (Q2372879)

Summary: A set \(D\subseteq V\) of vertices is said to be a (connected) distance \(k\)-dominating set of \(G\) if the distance between each vertex \(u\in V-D\) and \(D\) is at most \(k\) (and \(D\) induces a connected graph in \(G\)). The minimum cardinality of a (connected) distance \(k\)-dominating set in \(G\) is the (connected) distance \(k\)-domination number of \(G\), denoted by \(\gamma_k(G)\) (\(\gamma_k^c(G)\), respectively). The set \(D\) is defined to be a total \(k\)-dominating set of \(G\) if every vertex in \(V\) is within distance \(k\) from some vertex of \(D\) other than itself. The minimum cardinality among all total \(k\)-dominating sets of \(G\) is called the total \(k\)-domination number of \(G\) and is denoted by \(\gamma_k^t(G)\). For \(x\in X\subseteq V\), if \(N^k[x]-N^k[X-x]\neq\emptyset\), the vertex \(x\) is said to be \(k\)-irredundant in \(X\). A set \(X\) containing only \(k\)-irredundant vertices is called \(k\)-irredundant. The \(k\)-irredundance number of \(G\), denoted by \(ir_k(G)\), is the minimum cardinality taken over all maximal \(k\)-irredundant sets of vertices of \(G\). In this paper we establish lower bounds for the distance \(k\)-irredundance number of graphs and trees. More precisely, we prove that \({5k+1\over 2}ir_k(G)\geq \gamma_k^c(G)+2k\) for each connected graph \(G\) and \((2k+1)ir_k(T)\geq\gamma_k^c(T)+2k\geq |V|+2k-kn_1(T)\) for each tree \(T=(V,E)\) with \(n_1(T)\) leaves. A class of examples shows that the latter bound is sharp. The second inequality generalizes a result of Meierling and Volkmann (2005) and Cyman, Lemańska and Raczek (2006) regarding \(\gamma_k\) and the first generalizes a result of Favaron and Kratsch (1991) regarding \(ir_1\). Furthermore, we shall show that \(\gamma_k^c(G)\leq{3k+1\over2}\gamma_k^t(G)-2k\) for each connected graph \(G\), thereby generalizing a result of Favaron and Kratsch (1991) regarding \(k=1\).