Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2308.16837 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911906885795840 |
|---|---|
| author | Ahmadi, Azam Sadat Soltankhah, Nasrin Samadi, Babak |
| author_facet | Ahmadi, Azam Sadat Soltankhah, Nasrin Samadi, Babak |
| contents | A $k$-limited packing partition ($k$LP partition) of a graph $G$ is a partition of $V(G)$ into $k$-limited packing sets. We consider the $k$LP partitions with minimum cardinality (with emphasis on $k=2$). The minimum cardinality is called $k$LP partition number of $G$ and denoted by $χ_{\times k}(G)$. This problem is the dual problem of $k$-tuple domatic partitioning as well as a generalization of the well-studied $2$-distance coloring problem in graphs.
We give the exact value of $χ_{\times2}$ for trees and bound it for general graphs. A section of this paper is devoted to the dual of this problem, where we give a solution to an open problem posed in $1998$. We also revisit the total limited packing number in this paper and prove that the problem of computing this parameter is NP-hard even for some special families of graphs. We give some inequalities concerning this parameter and discuss the difference between $2$TLP number and $2$LP number with emphasis on trees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_16837 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Limited packings: related vertex partitions and duality issues Ahmadi, Azam Sadat Soltankhah, Nasrin Samadi, Babak Combinatorics A $k$-limited packing partition ($k$LP partition) of a graph $G$ is a partition of $V(G)$ into $k$-limited packing sets. We consider the $k$LP partitions with minimum cardinality (with emphasis on $k=2$). The minimum cardinality is called $k$LP partition number of $G$ and denoted by $χ_{\times k}(G)$. This problem is the dual problem of $k$-tuple domatic partitioning as well as a generalization of the well-studied $2$-distance coloring problem in graphs. We give the exact value of $χ_{\times2}$ for trees and bound it for general graphs. A section of this paper is devoted to the dual of this problem, where we give a solution to an open problem posed in $1998$. We also revisit the total limited packing number in this paper and prove that the problem of computing this parameter is NP-hard even for some special families of graphs. We give some inequalities concerning this parameter and discuss the difference between $2$TLP number and $2$LP number with emphasis on trees. |
| title | Limited packings: related vertex partitions and duality issues |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2308.16837 |