Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2505.19642 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910968605310976 |
|---|---|
| author | Fernandez, Elena Klavzar, Sandi Kuziak, Dorota Muñoz-Marquez, Manuel Yero, Ismael G. |
| author_facet | Fernandez, Elena Klavzar, Sandi Kuziak, Dorota Muñoz-Marquez, Manuel Yero, Ismael G. |
| contents | Given a connected graph $G$, a set of vertices $X\subset V(G)$ is a weak $k$-resolving set of $G$ if for each two vertices $y,z\in V(G)$, the sum of the values $|d_G(y,x)-d_G(z,x)|$ over all $x\in X$ is at least $k$, where $d_G(u,v)$ stands for the length of a shortest path between $u$ and $v$. The cardinality of a smallest weak $k$-resolving set of $G$ is the weak $k$-metric dimension of $G$, and is denoted by $\mathrm{wdim}_k(G)$. In this paper, $\mathrm{wdim}_k(K_n\,\square\,K_n)$ is determined for every $n\ge 3$ and every $2\le k\le 2n$. An improvement of a known integer linear programming formulation for this problem is developed and implemented for the graphs $K_n\,\square\,K_m$. Conjectures regarding these general situations are posed. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_19642 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the weak $k$-metric dimension of Hamming graphs Fernandez, Elena Klavzar, Sandi Kuziak, Dorota Muñoz-Marquez, Manuel Yero, Ismael G. Combinatorics Given a connected graph $G$, a set of vertices $X\subset V(G)$ is a weak $k$-resolving set of $G$ if for each two vertices $y,z\in V(G)$, the sum of the values $|d_G(y,x)-d_G(z,x)|$ over all $x\in X$ is at least $k$, where $d_G(u,v)$ stands for the length of a shortest path between $u$ and $v$. The cardinality of a smallest weak $k$-resolving set of $G$ is the weak $k$-metric dimension of $G$, and is denoted by $\mathrm{wdim}_k(G)$. In this paper, $\mathrm{wdim}_k(K_n\,\square\,K_n)$ is determined for every $n\ge 3$ and every $2\le k\le 2n$. An improvement of a known integer linear programming formulation for this problem is developed and implemented for the graphs $K_n\,\square\,K_m$. Conjectures regarding these general situations are posed. |
| title | On the weak $k$-metric dimension of Hamming graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2505.19642 |