On the weak $k$-metric dimension of Hamming graphs

Fernández, Elena (author), Klavžar, Sandi (author), Kuziak, Dorota (author), Muñoz-Márquez, Manuel (author), Yero, Ismael G. (author)

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.

• Language: English
• Keywords: weak $k$-metric dimension, weak $k$-resolving set, Cartesian product, Hamming graph
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Publication date: 01.05.2026
• Year: 2026
• Number of pages: 12 str.
• Numbering: Vol. 60, article no. 100945
• PID: 20.500.12556/RUL-180684
• UDC: 519.17:519.8
• ISSN on article: 1572-5286
• DOI: 10.1016/j.disopt.2026.100945
• COBISS.SI-ID: 271637763
• Publication date in RUL: 13.03.2026

Record is a part of a journal

• Title: Discrete optimization
• Publisher: Elsevier
• ISSN: 1572-5286
• COBISS.SI-ID: 513620761

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Secondary language

• Language: Slovenian
• Keywords: šibka $k$-metrična dimenzija, šibka $k$-solventna množica, kartezični produkt, Hammingov graf