The Multiresolving Sets of Graphs with Prescribed Multisimilar Equivalence Classes
For a set W=w1,w2,…,wk of vertices and a vertex v of a connected graph G, the multirepresentation of v with respect to W is the k-multiset mr(v∣W)=dv,w1,dv,w2,…,dv,wk, where d(v,wi) is the distance between the vertices v and wi for i=1,2,…,k. The set W is a multiresolving set of G if every two disti...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2018-01-01
|
| Series: | International Journal of Mathematics and Mathematical Sciences |
| Online Access: | http://dx.doi.org/10.1155/2018/8978193 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | For a set W=w1,w2,…,wk of vertices and a vertex v of a connected graph G, the multirepresentation of v with respect to W is the k-multiset mr(v∣W)=dv,w1,dv,w2,…,dv,wk, where d(v,wi) is the distance between the vertices v and wi 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 dimM(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 dimM(G)=k. For a multiset {a1,a2,…,ak} and an integer c, we define {a1,a2,…,ak}+c,c,…,c=a1+c,a2+c,…,ak+c. A multisimilar equivalence relation RW on V(G) with respect to W is defined by u RW v if mr(u∣W)=mrv∣W+cWu,v,cWu,v,…,cWu,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. |
|---|---|
| ISSN: | 0161-1712 1687-0425 |