The Multiresolving Sets of Graphs with Prescribed Multisimilar Equivalence Classes

Abstract

For a set W = w 1, w 2,., wk of vertices and a vertex v of a connected graph G, the multirepresentation of v with respect to W is the k-multiset m r (v | W) = d v, w 1, d v, w2,., d v, wk, where d (v, wi) is the distance between the vertices v and w i for i = 1,2,., k. The set W is a multiresolving set of G if every two distinct vertices of G have distinct multirepresentations with respect to W. The minimum cardinality of a multiresolving set of G is the multidimension dim m (G) of G. It is shown that, for every pair k, n of integers with k ≥ 3 and n ≥ 3 (k-1), there is a connected graph G of order n with d i m M (G) = k. For a multiset { a1, a2,., a k } and an integer c, we define { a1 a2,., ak } + c, c,., c = a1 + c, a2 + c,., a k + c. A multisimilar equivalence relation R W on V (G) with respect to W is defined by u R W v if mr(uW) = mrv W + cw u, v, cw u, v,., c wu, v for some integer cw (u, v). We study the relationship between the elements in multirepresentations of vertices that belong to the same multisimilar equivalence class and also establish the upper bound for the cardinality of a multisimilar equivalence class. Moreover, a multiresolving set with prescribed multisimilar equivalence classes is presented. © 2018 Varanoot Khemmani and Supachoke Isariyapalakul.