2021/01/25 by Klavžar, Sandi, Rahbarnia, Freydoon, Tavakoli, Mostafa
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2101.10012
Let G be a connected graph. For an ordered set S=\v1,…, v_ℓ\⊆ V(G), the vector rG(v|S) = (dG(v1,v), …, dG(v_ℓ,v)) is called the metric S-representation of v. If for any pair of different vertices u,v∈ V(G), the vectors r(v|S) and r(u|S) differ in at least k positions, then S is a k-metric generator for G. A smallest k-metric generator for G is a k-\em metric basis for G, its cardinality being the k-metric dimension of G. A sharp upper bound and a closed formulae 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 and 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.