| Naslov: | The $d$-distance $p$-packing domination number: complexity, cycles, and trees |
|---|
| 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 (634,30 KB)
MD5: 9F797C466E3B0F834BA95DCB376B70E7
 URL - Izvorni URL, za dostop obiščite https://link.springer.com/article/10.1007/s00010-026-01266-w
|
|---|
| Jezik: | Angleški jezik |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: |  IMFM - Inštitut za matematiko, fiziko in mehaniko
|
|---|
| Povzetek: | A set of vertices $X\subseteq V(G)$ is a $d$-distance dominating set if for every $u\in V(G)\setminus X$ there exists $x\in X$ such that $d(u,x) \le d$, and $X$ is a $p$-packing if $d(u,v) \ge p+1$ for every different $u,v\in X$. 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. It is proved that for every two fixed integers $d$ and $p$ with $2 \le d$ and $0 \le p \leq 2d-1$, the decision problem whether $\gamma_d^p(G) \leq k$ holds is NP-complete for bipartite planar graphs. A necessary and sufficient condition for the existence of a $d$-distance $p$-packing dominating set in $C_n$ is obtained and $\gamma_d^p(C_n)$ determined for every $d$, $p$, and $n$. For a tree $T$ on $n$ vertices with $\ell$ leaves and $s$ support vertices it is proved that (i) $\gamma_2^0(T) \geq \frac{n-\ell-s+4}{5}$, (ii) $\left \lceil \frac{n-\ell-s+4}{5} \right \rceil \leq \gamma_2^2(T) \leq \left \lfloor \frac{n+3s-1}{5} \right \rfloor$, and if $d \geq 2$, then (iii) $\gamma_d^2(T) \leq \frac{n-2\sqrt{n}+d+1}{d}$. Inequality (i) improves an earlier bound due to Meierling and Volkmann, and independently Raczek, Lema\'nska, and Cyman, while (iii) extends an earlier result for $\gamma_2^2(T)$ due to Henning. Sharpness of the bounds is discussed and established in most cases. It is also proved that every connected graph $G$ contains a spanning tree $T$ such that $\gamma_2^2(T) \leq \gamma_2^2(G)$. |
|---|
| Ključne besede: | d-distance dominating set, p-packing set, dominating set, trees, planar graphs |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 01.04.2026 |
|---|
| Leto izida: | 2026 |
|---|
| Št. strani: | 22 str. |
|---|
| Številčenje: | Vol. 100, iss. 2, article no. 25 |
|---|
| PID: | 20.500.12556/DiRROS-27714  |
|---|
| UDK: | 519.17 |
|---|
| ISSN pri članku: | 0001-9054 |
|---|
| DOI: | 10.1007/s00010-026-01266-w |
|---|
| COBISS.SI-ID: | 269190659 |
|---|
| Datum objave v DiRROS: | 23.02.2026 |
|---|
| Število ogledov: | 175 |
|---|
| Število prenosov: | 86 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
