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

The d-distance p-packing domination number γdᵖ(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¹(T) ≤ n/d+1. They supported the conjecture by proving it for d∈ \1,2,3\. In this paper, it is proved that γd¹(G) ≤ n/d+1 holds for any bipartite graph G of order n ≥ d+1, and any d≥ 1. Trees T for which γd¹(T) = n/d+1 holds are characterized. It is also proved that if T has leaves, then γd¹(T) ≤ n-/d (provided that n- ≥ d), and γd¹(T) ≤ n+/d+2 (provided that n≥ d). The latter result extends Favaron's theorem from 1992 asserting that γ₁¹(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.