Revisiting d-distance (independent) domination in trees and in bipartite graphs

The d -distance p -packing domination number γ d p ( G ) of G is the minimum size of a set of vertices of G which is both a d -distance dominating set and a p -packing. In 1994, Beineke and Henning conjectured that if d ≥ 1 and T is a tree of order n ≥ d + 1 , then γ d 1 ( T ) ≤ n d + 1 . They supported the conjecture by proving it for d ∈ { 1 , 2 , 3 } . In this paper, it is proved that γ d 1 ( G ) ≤ n d + 1 holds for any bipartite graph G of order n ≥ d + 1 , and any d ≥ 1 . Trees T for which γ d 1 ( T ) = n d + 1 holds are characterized. It is also proved that if T has ℓ leaves, then γ d 1 ( T ) ≤ n − ℓ d (provided that n − ℓ ≥ d ), and γ d 1 ( T ) ≤ n + ℓ d + 2 (provided that n ≥ d ). The latter result extends Favaron's theorem from 1992 asserting that γ 1 1 ( T ) ≤ n + ℓ 3 . In both cases, trees that attain the equality are characterized and relevant conclusions for the d -distance domination number of trees derived.