Distance Domination and Distance Irredundance in Graphs - Hansberg, Adriana; Meierling, Dirk; Volkmann, Lutz (The Electronic Journal of Combinatorics, 2007)
A set DV of vertices is said to be a (connected) distance k-dominating set of G if the distance between each vertex uV-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 γ_k(G) (γ_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 γ_k^t(G). For xXV, if N^k[x]-N^k[X-x] eq, 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+12ir_k(G)≥ γ_k^c(G)+2k for each connected graph G and (2k+1)ir_k(T)≥γ_k^c(T)+2k≥ |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 and Cyman, Lemańska and Raczek regarding γ_k and the first generalizes a result of Favaron and Kratsch regarding ir_1. Furthermore, we shall show that γ_k^c(G)≤3k+12γ_k^t(G)-2k for each connected graph G, thereby generalizing a result of Favaron and Kratsch regarding k=1.