| Naslov: | Revisiting $d$-distance (independent) domination in trees and in bipartite graphs |
|---|
| Avtorji: | ID Bujtás, Csilla (Avtor)
ID Iršič Chenoweth, Vesna (Avtor)
ID Klavžar, Sandi (Avtor)
ID Zhang, Gang (Avtor) |
|---|
| Datoteke: |  PDF - Predstavitvena datoteka, prenos (856,17 KB)
MD5: 3378D59F4DD51C214FE3BE26D6F03864
 URL - Izvorni URL, za dostop obiščite https://www.sciencedirect.com/science/article/pii/S0012365X25005801
|
|---|
| Jezik: | Angleški jezik |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: |  IMFM - Inštitut za matematiko, fiziko in mehaniko
|
|---|
| Povzetek: | 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. |
|---|
| Ključne besede: | d-distance dominating set, p-packing set, trees, bipartite graphs |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 01.06.2026 |
|---|
| Leto izida: | 2026 |
|---|
| Št. strani: | 11 str. |
|---|
| Številčenje: | Vol. 349, iss. 6, article no. 114972 |
|---|
| PID: | 20.500.12556/DiRROS-24967  |
|---|
| UDK: | 519.17 |
|---|
| ISSN pri članku: | 0012-365X |
|---|
| DOI: | 10.1016/j.disc.2025.114972 |
|---|
| COBISS.SI-ID: | 263511811 |
|---|
| Opomba: |
|
|---|
| Datum objave v DiRROS: | 06.01.2026 |
|---|
| Število ogledov: | 383 |
|---|
| Število prenosov: | 185 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
