The Multiresolving Sets of Graphs with Prescribed Multisimilar Equivalence Classes

Abstract EN

For a set W = w 1 , w 2 , … , 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 ∣ W ) = d v , w 1 , d v , w 2 , … , d v , w k , where d ( v , w i ) 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 d i m 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 { a 1 , a 2 , … , a k } and an integer c , we define { a 1 , a 2 , … , a k } + c , c , … , c = a 1 + c , a 2 + 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 m r ( u ∣ W ) = m r v ∣ W + c W u , v , c W u , v , … , 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.