| Title: | On the weak $k$-metric dimension of Hamming graphs |
|---|
| Authors: | ID Fernández, Elena (Author)
ID Klavžar, Sandi (Author)
ID Kuziak, Dorota (Author)
ID Muñoz-Márquez, Manuel (Author)
ID Yero, Ismael G. (Author) |
|---|
| Files: |  PDF - Presentation file, download (967,09 KB)
MD5: B763044489102E3BF1A567EDEFD8DE93
 URL - Source URL, visit https://www.sciencedirect.com/science/article/pii/S1572528626000186
|
|---|
| Language: | English |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: |  IMFM - Institute of Mathematics, Physics, and Mechanics
|
|---|
| Abstract: | 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. |
|---|
| Keywords: | weak $k$-metric dimension, weak $k$-resolving set, Cartesian product, Hamming graph |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Publication date: | 01.05.2026 |
|---|
| Year of publishing: | 2026 |
|---|
| Number of pages: | 12 str. |
|---|
| Numbering: | Vol. 60, article no. 100945 |
|---|
| PID: | 20.500.12556/DiRROS-28314  |
|---|
| UDC: | 519.17:519.8 |
|---|
| ISSN on article: | 1572-5286 |
|---|
| DOI: | 10.1016/j.disopt.2026.100945 |
|---|
| COBISS.SI-ID: | 271637763 |
|---|
| Publication date in DiRROS: | 13.03.2026 |
|---|
| Views: | 216 |
|---|
| Downloads: | 169 |
|---|
| Metadata: |    |
|---|
|
:
|
Copy citation |
|---|
| | | | Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
