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) nd+1. They supported the conjecture by proving it for d \1, 2, 3\. In this paper, it is proved that γd¹ (G) nd+1 holds for any bipartite graph G of order n d+1, and any d 1. Trees T for which γd¹ (T) = nd+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.