2025/08/18 by Bujtás, Csilla, Chenoweth, Vesna Iršič, Klavžar, Sandi +1 · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2508.12804
The d-distance p-packing domination number γdp(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 γd1(T) ≤ (n)/(d+1). They supported the conjecture by proving it for d∈ \1,2,3\. In this paper, it is proved that γd1(G) ≤ (n)/(d+1) holds for any bipartite graph G of order n ≥ d+1, and any d≥ 1. Trees T for which γd1(T) = (n)/(d+1) holds are characterized. It is also proved that if T has ℓ leaves, then γd1(T) ≤ (n-ℓ)/(d) (provided that n-ℓ ≥ d), and γd1(T) ≤ (n+ℓ)/(d+2) (provided that n≥ d). The latter result extends Favaron's theorem from 1992 asserting that γ11(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.