On the weak k-metric dimension of Hamming graphs

2025/05/26 by Elena Fernández, Sandi Klavžar, Fernandez, Elena +7
Computer Science · #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.2505.19642

Abstract

Given a connected graph G, a set of vertices X⊂ V(G) is a weak k-resolving set of G if for each two vertices y,z∈ V(G), the sum of the values |d_G(y,x)-d_G(z,x)| over all x∈ 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 wdim_k(G). In this paper, wdim_k(K_n \square K_n) is determined for every n≥ 3 and every 2≤ k≤ 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.

Citations

• Resolving vertices of graphs with differences
• Metric dimension related parameters in graphs: A survey on combinatorial, computational and applied results
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and its Applications
• The k-metric dimension of a graph

Related

• Weak total resolving sets in graphs
• Extremal Graph Theory for Metric Dimension and Girth
• A characterization of some graphs with metric dimension two
• Resolving vertices of graphs with differences
• On the strong metric dimension of composed graphs