20.500.12556/RUL-177749 Revisiting $d$-distance (independent) domination in trees and in bipartite graphs The $d$-distance $p$-packing domination number $\gamma_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\ge 1$ and $T$ is a tree of order $n \geq d+1$, then $\gamma_d^1(T) \leq \frac{n}{d+1}$. They supported the conjecture by proving it for $d\in \{1,2,3\}$. In this paper, it is proved that $\gamma_d^1(G) \leq \frac{n}{d+1}$ holds for any bipartite graph $G$ of order $n \geq d+1$, and any $d\ge 1$. Trees $T$ for which $\gamma_d^1(T) = \frac{n}{d+1}$ holds are characterized. It is also proved that if $T$ has $\ell$ leaves, then $\gamma_d^1(T) \leq \frac{n-\ell}{d}$ (provided that $n-\ell \geq d$), and $\gamma_d^1(T) \leq \frac{n+\ell}{d+2}$ (provided that $n\geq d$). The latter result extends Favaron's theorem from 1992 asserting that $\gamma_1^1(T) \leq \frac{n+\ell}{3}$. In both cases, trees that attain the equality are characterized and relevant conclusions for the $d$-distance domination number of trees derived. d-distance dominating set p-packing set trees bipartite graphs d-razdaljna dominantna množica p-pakirna množica drevesa dvodelni grafi true false true Angleški jezik Slovenski jezik Članek v reviji 2026-01-06 11:01:25 2026-01-06 11:01:29 2026-07-01 16:53:11 0000-00-00 00:00:00 2026 0 0 11 str. iss. 6, art. 114972 Vol. 349 Jun. 2026 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 0012-365X 10.1016/j.disc.2025.114972 263511811 1-s2.0-S0012365X25005801-main.pdf 1-s2.0-S0012365X25005801-main.pdf 1 1924260CC0740AB42C566A497D6648C5 9d62c630842a6d01aeae6d52211aa270b3a25b51dc55b41a17938fe1856a267a 1f71b086-eae7-11f0-bf92-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=225039 https://www.sciencedirect.com/science/article/pii/S0012365X25005801 1 ac85a2aa-eae6-11f0-bf92-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=225036 Fakulteta za matematiko in fiziko 0 0 0