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

Bujtás, Csilla (avtor), Iršič Chenoweth, Vesna (avtor), Klavžar, Sandi (avtor), Zhang, Gang (avtor)

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.

• Jezik: Angleški jezik
• Ključne besede: d-distance dominating set, p-packing set, trees, bipartite graphs
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Datum objave: 01.06.2026
• Leto izida: 2026
• Št. strani: 11 str.
• Številčenje: Vol. 349, iss. 6, art. 114972
• PID: 20.500.12556/RUL-177749
• UDK: 519.17
• ISSN pri članku: 0012-365X
• DOI: 10.1016/j.disc.2025.114972
• COBISS.SI-ID: 263511811
• Datum objave v RUL: 06.01.2026

Gradivo je del revije

• Naslov: Discrete mathematics
• Skrajšan naslov: Discrete math.
• Založnik: Elsevier
• ISSN: 0012-365X
• COBISS.SI-ID: 1118479

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: d-razdaljna dominantna množica, p-pakirna množica, drevesa, dvodelni grafi