Locating-domination, 2-domination and independence in trees.
Mostafa Blidia, Odile Favaron, Rahma Lounes · 2008
A set D of vertices in a graph G is 2-dominating if every vertex not in D has at least two neighbors in D and locating-dominating if for every two vertices u, v not in D, the sets N(u) ∩ D and N(v) ∩ D are non-empty and different. The minimum cardinality of a 2-dominating set (locating dominating set) is denoted by γ2(G) (γL(G)). It is known that every tree T with n ≥ 2 vertices, ℓ leaves, s support vertices and independence number β(T), satisfies γL(T) ≤ (n + ℓ − s)/2 ≤ β(T) ≤ γ2(T). We show that β(T)+γL(T) ≤ n + ℓ − s and that γ2(T)=(n + ℓ − s)/2 if and only if γL(T)=γ2(T). Moreover, γ2(G) ≤ 2γL(G) for every bipartite graph and γ2(G) ≤ 2γL(G) − 1ifG is a tree with n ≥ 3.