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

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

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.

• Jezik: Angleški jezik
• Ključne besede: weak $k$-metric dimension, weak $k$-resolving set, Cartesian product, Hamming graph
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Datum objave: 01.05.2026
• Leto izida: 2026
• Št. strani: 12 str.
• Številčenje: Vol. 60, article no. 100945
• PID: 20.500.12556/RUL-180684
• UDK: 519.17:519.8
• ISSN pri članku: 1572-5286
• DOI: 10.1016/j.disopt.2026.100945
• COBISS.SI-ID: 271637763
• Datum objave v RUL: 13.03.2026

Gradivo je del revije

• Naslov: Discrete optimization
• Založnik: Elsevier
• ISSN: 1572-5286
• COBISS.SI-ID: 513620761

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: šibka $k$-metrična dimenzija, šibka $k$-solventna množica, kartezični produkt, Hammingov graf