Revisiting $d$-distance (independent) domination in trees and in bipartite graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918273625358336 |
|---|---|
| author | Bujtás, Csilla Chenoweth, Vesna Iršič Klavžar, Sandi Zhang, Gang |
| author_facet | Bujtás, Csilla Chenoweth, Vesna Iršič Klavžar, Sandi Zhang, Gang |
| contents | The $d$-distance $p$-packing domination number $γ_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 $γ_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 $γ_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 $γ_d^1(T) = \frac{n}{d+1}$ holds are characterized. It is also proved that if $T$ has $\ell$ leaves, then $γ_d^1(T) \leq \frac{n-\ell}{d}$ (provided that $n-\ell \geq d$), and $γ_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 $γ_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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_12804 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Revisiting $d$-distance (independent) domination in trees and in bipartite graphs Bujtás, Csilla Chenoweth, Vesna Iršič Klavžar, Sandi Zhang, Gang Combinatorics The $d$-distance $p$-packing domination number $γ_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 $γ_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 $γ_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 $γ_d^1(T) = \frac{n}{d+1}$ holds are characterized. It is also proved that if $T$ has $\ell$ leaves, then $γ_d^1(T) \leq \frac{n-\ell}{d}$ (provided that $n-\ell \geq d$), and $γ_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 $γ_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. |
| title | Revisiting $d$-distance (independent) domination in trees and in bipartite graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2508.12804 |