On $d$-distance $p$-packing domination number in strong products
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916987234418688 |
|---|---|
| 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 a graph $G$ is the cardinality of a smallest set of vertices of $G$ which is both a $d$-distance dominating set and a $p$-packing. If no such set exists, then we set $γ_d^p(G) = \infty$. For an arbitrary strong product $G\boxtimes H$ it is proved that $γ_d^p(G\boxtimes H) \le γ_d^p(G) γ_d^p(H)$. By proving that $γ_d^p(P_m \boxtimes P_n) = \left \lceil \frac{m}{2d+1} \right \rceil \left \lceil \frac{n}{2d+1} \right \rceil$, and that if $γ_d^p(C_n) < \infty$, then $γ_d^p(P_m \boxtimes C_n) = \left \lceil \frac{m}{2d+1} \right \rceil \left \lceil \frac{n}{2d+1} \right \rceil$, the sharpness of the upper bound is demonstrated. On the other hand, infinite families of strong toruses are presented for which the strict inequality holds. For instance, we present strong toruses with difference $2$ and demonstrate that the difference can be arbitrarily large if only one factor is a cycle. It is also conjectured that if $γ_d^p(G) = \infty$, then $γ_d^p(G\boxtimes H) = \infty$ for every graph $H$. Several results are proved which support the conjecture, in particular, if $γ_d^p(C_m)= \infty$, then $γ_d^p(C_m \boxtimes C_n)=\infty$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_02749 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On $d$-distance $p$-packing domination number in strong products Bujtás, Csilla Chenoweth, Vesna Iršič Klavžar, Sandi Zhang, Gang Combinatorics The $d$-distance $p$-packing domination number $γ_d^p(G)$ of a graph $G$ is the cardinality of a smallest set of vertices of $G$ which is both a $d$-distance dominating set and a $p$-packing. If no such set exists, then we set $γ_d^p(G) = \infty$. For an arbitrary strong product $G\boxtimes H$ it is proved that $γ_d^p(G\boxtimes H) \le γ_d^p(G) γ_d^p(H)$. By proving that $γ_d^p(P_m \boxtimes P_n) = \left \lceil \frac{m}{2d+1} \right \rceil \left \lceil \frac{n}{2d+1} \right \rceil$, and that if $γ_d^p(C_n) < \infty$, then $γ_d^p(P_m \boxtimes C_n) = \left \lceil \frac{m}{2d+1} \right \rceil \left \lceil \frac{n}{2d+1} \right \rceil$, the sharpness of the upper bound is demonstrated. On the other hand, infinite families of strong toruses are presented for which the strict inequality holds. For instance, we present strong toruses with difference $2$ and demonstrate that the difference can be arbitrarily large if only one factor is a cycle. It is also conjectured that if $γ_d^p(G) = \infty$, then $γ_d^p(G\boxtimes H) = \infty$ for every graph $H$. Several results are proved which support the conjecture, in particular, if $γ_d^p(C_m)= \infty$, then $γ_d^p(C_m \boxtimes C_n)=\infty$. |
| title | On $d$-distance $p$-packing domination number in strong products |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2510.02749 |