The partition dimension and $k$-domination number of a family of non-distance regular graph
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916001642184704 |
|---|---|
| author | Zafari, Ali Alikhani, Saeid |
| author_facet | Zafari, Ali Alikhani, Saeid |
| contents | A partition $Σ= \{S_1, S_2, \dots, S_k\}$ of the vertex set $V(G)$ is a resolving partition if every pair of distinct vertices in $G$ has a unique representation relative to $Σ$. The partition dimension, $pd(G)$, is the minimum cardinality of such a partition. Additionally, a subset $D \subseteq V(G)$ is a $k$-dominating set if every vertex in $V(G) \setminus D$ has at least $k$ neighbors in $D$; the $k$-domination number, $γ_k(G)$, denotes the minimum size of such a set. Determining these parameters is NP-complete and particularly challenging for non-distance-regular graphs. This paper consider the Toeplitz graph $T_{2n}(W)$, a family of non-distance-regular graphs. While some resolving parameters for this family have been established, its partition dimension and $k$-domination number remain unknown. We close this gap by computing both parameters for $T_{2n}(W)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_10962 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The partition dimension and $k$-domination number of a family of non-distance regular graph Zafari, Ali Alikhani, Saeid Combinatorics 05C15, 05C50 A partition $Σ= \{S_1, S_2, \dots, S_k\}$ of the vertex set $V(G)$ is a resolving partition if every pair of distinct vertices in $G$ has a unique representation relative to $Σ$. The partition dimension, $pd(G)$, is the minimum cardinality of such a partition. Additionally, a subset $D \subseteq V(G)$ is a $k$-dominating set if every vertex in $V(G) \setminus D$ has at least $k$ neighbors in $D$; the $k$-domination number, $γ_k(G)$, denotes the minimum size of such a set. Determining these parameters is NP-complete and particularly challenging for non-distance-regular graphs. This paper consider the Toeplitz graph $T_{2n}(W)$, a family of non-distance-regular graphs. While some resolving parameters for this family have been established, its partition dimension and $k$-domination number remain unknown. We close this gap by computing both parameters for $T_{2n}(W)$. |
| title | The partition dimension and $k$-domination number of a family of non-distance regular graph |
| topic | Combinatorics 05C15, 05C50 |
| url | https://arxiv.org/abs/2605.10962 |