Some binary products and integer linear programming for k -metric dimension of graphs

A sharp upper bound and a closed formula for the k-metric dimension of the hierarchical product of graphs is proved. Also, sharp lower bounds for the k-metric dimension of the splice and link products of graphs are presented. An integer linear programming model for computing the k-metric dimension as well as a k-metric basis of a given graph is proposed. These results are applied to bound or to compute the k-metric dimension of some classes of graphs that are of interest in mathematical chemistry. (c) 2021 Elsevier Inc. All rights reserved.

Automated summary

This paper proves a sharp upper bound and a closed formula for the k-metric dimension of the hierarchical product of graphs, as well as presents sharp lower bounds for the k-metric dimension of the splice and link products of graphs. Additionally, it proposes an integer linear programming model for computing the k-metric dimension and k-metric basis of a given graph, and applies these results to certain classes of graphs of interest in mathematical chemistry.