The multiresolving sets of graphs with prescribed multisimilar equivalence classes (Q2330269)

Summary: For a set \(W = \{w_1, w_2, \dots, w_k\}\) 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 \mid W) = \{d (v, w_1), d (v, w_2),\dots, d (v, w_k)\}\), where \(d(v, w_i)\) is the distance between the vertices \(v\) and \(w_i\) for \(i = 1,2, \dots, 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 \(\operatorname{dim}_M(G)\) of \(G\). It is shown that, for every pair \(k, n\) of integers with \(k \geq 3\) and \(n \geq 3(k - 1)\), there is a connected graph \(G\) of order \(n\) with \(\operatorname{dim}_M(G) = k\). For a multiset \(\{a_1, a_2, \dots, a_k \}\) and an integer \(c\), we define \(\{a_1, a_2, \dots, a_k \} +\{c,c, \dots, c\} =\{a_1 + c, a_2 + c, \dots, a_k + c\}\). A multisimilar equivalence relation \(R_W\) on \(V(G)\) with respect to \(W\) is defined by \(u R_W v\) if \(m r(u \mid W) = m r (v\mid W) + \{c_W (u, v), c_W (u,v), \dots, c_W (u,v)\}\) for some integer \(c_W(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.