# The Multiresolving Sets of Graphs with Prescribed Multisimilar Equivalence Classes

Authors: Varanoot Khemmani; Supachoke Isariyapalakul
Journal: International Journal of Mathematics and Mathematical Sciences
 (2018)

---

## Abstract

For a setW
=
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.


---

## Body

## 1. Introduction

Thedistance  d
(
u
,
v
) between two vertices u and v in a connected graph G is the length of a shortest u
-
v path in G. For an ordered set W
=
w
1
,
w
2
,
…
,
w
k
⊆
V
(
G
) and a vertex v of G, the k-vector (1)
r
v
∣
W
=
d
v
,
w
1
,
d
v
,
w
2
,
…
,
d
v
,
w
kis referred to as therepresentation of  v with respect to
W. The ordered set W is called aresolving set of G if every two distinct vertices of G have distinct representations with respect to W. A resolving set of a minimum cardinality is called aminimum resolving set or abasis of G and this cardinality is thedimension  dim
⁡
(
G
) of G.To illustrate these concepts, consider a connected graphG of Figure 1 with V
(
G
)
=
u
,
v
,
w
,
x
,
y
,
z. Considering the ordered set W
1
=
w
,
z, there are six representations of the vertices of G with respect to W
1:(2)
r
u
∣
W
1
=
2,3
,
r
v
∣
W
1
=
3,2
,
r
w
∣
W
1
=
0,3
,
r
x
∣
W
1
=
1,2
,
r
y
∣
W
1
=
2,1
,
r
z
∣
W
1
=
3,0
.Since there is no 1-element resolving set of G, it follows that W
1 is a basis of G, and so dim
⁡
(
G
)
=
2.Figure 1
A connected graphG.The concepts of resolving sets and minimum resolving sets have previously appeared in [1–4]. Slater in [3, 4] introduced these ideas and used alocating set for what we have called a resolving set. He referred to the cardinality of a minimum resolving set in a connected graph as itslocating number. He described the usefulness of these ideas when working with US sonar and coast guard LORAN (long range aids to navigation) stations. Harary and Melter [2] discovered these concepts independently as well but used the termmetric dimension rather than locating number, the terminology that we have adopted. These concepts were rediscovered by Johnson [5] of the Pharmacia Company while attempting to develop a capability of large datasets of chemical graphs. More applications of these concepts to navigation of robots in networks and other areas are discussed in [6–9].Amultiset is a generalization of the concept of a set, which is like a set except that its members need not to be distinct. For example, the set {
1,1
,
2
} is the same as the set {
1,2
} but not so for the multiset. The multiset M
=
5,5
,
6
,
a
,
a
,
a
,
a
,
b
,
b
,
b has 10 elements of 4 different types: 2 of type 5, 1 of type 6, 4 of type a, and 3 of type b. So, the multiset is usually indicated by specifying the number of times different types of elements occur in it. Therefore, the multiset M can be written by M
=
2
·
5,1
·
6,4
·
a
,
3
·
b. The numbers 2,1
,
4, and 3 are called therepetition numbers of the multiset M. In particular, a set is a multiset having all repetition numbers equal to 1.As described in [1], all connected graphs G contain an ordered set W such that each vertex of G is distinguished by a k-vector, known as a representation, consisting of its distance from the vertices in W. It may also occur that some graph contains a set W
′ with property that the vertices of graph have uniquely distinct k-multisets containing their distances from each of the vertices in W
′. The goal of this paper is to study the existence of such a set of connected graphs.For a setW
=
w
1
,
w
2
,
…
,
w
k of vertices and a vertex v of a connected graph G, we refer to the k-multiset (3)
m
r
v
∣
W
=
d
v
,
w
1
,
d
v
,
w
2
,
…
,
d
v
,
w
kas themultirepresentation of
v
with respect to
W. The set W is called amultiresolving setof G if every two distinct vertices have distinct multirepresentations with respect to W. A multiresolving set of a minimum cardinality is called aminimum multiresolving set or amultibasis of G and this cardinality is themultidimension
d
i
m
M
(
G
) of G.For example, consider a connected graphG of Figure 1. As we know W
1
=
w
,
z is a basis of G. However, W
1 is not a multiresolving set of G since m
r
(
u
∣
W
1
)
=
2,3
=
m
r
(
v
∣
W
1
). In fact, the set W
2
=
w
,
x
,
z is a multiresolving set of G with the following multirepresentations of the vertices of G with respect to W
2:(4)
m
r
u
∣
W
2
=
1,2
,
3
,
m
r
v
∣
W
2
=
2,2
,
3
,
m
r
w
∣
W
2
=
0,1
,
3
,
m
r
x
∣
W
2
=
0,1
,
2
,
m
r
y
∣
W
2
=
1,1
,
2
,
m
r
z
∣
W
2
=
0,2
,
3
.It is routine to verify that there are no 1-element and 2-element multiresolving sets of G. Hence, W
2 is a multibasis of G, and so d
i
m
M
(
G
)
=
3.Not all connected graphs have a multiresolving set and alsod
i
m
M
(
G
) is not defined for all connected graphs G. For example, the complete graph K
3 has no multiresolving set. Thus, d
i
m
M
(
K
3
) is not defined. However, if G is a connected graph of order n, for which d
i
m
M
(
G
) is defined, and then every multiresolving set of G is a resolving set of G, and so(5)
1
≤
dim
⁡
G
≤
d
i
m
M
G
≤
n
.For every setW of vertices of a connected graph G, the vertices of G whose multirepresentations with respect to W contain 0 are vertices in W. On the other hand, the multirepresentations of vertices of G which do not belong to W have elements, all of which are positive. In fact, to determine whether a set W is a multiresolving set of G, the vertex set V
(
G
) can be partitioned into W and V
(
G
)
-
W to examine whether the vertices in each subset have distinct multirepresentations with respect to W.The multiresolving set of a connected graph was introduced by Saenpholphat [10] who showed that there is no connected graph G such that d
i
m
M
(
G
)
=
2. Moreover, the multidimensions of complete graphs, paths, cycles, and bipartite graphs were determined. Simanjuntak, Vetrík, and Mulia [11] discovered this concept independently and used a notation m
d
(
G
) for a multidimension of a connected graph G.


## 2. The Multidimension of a Connected Graph

Two verticesu and v of a connected graph G aredistance-similar if d
(
u
,
x
)
=
d
(
v
,
x
) for all x
∈
V
(
G
)
-
u
,
v. Certainly, distance similarity in G is an equivalence relation on V
(
G
). For example, consider a complete bipartite graph K
r
,
s with partite sets U and V. Every pair of vertices in the same partite set are distance-similar. Then the distance-similar equivalence classes in K
r
,
s are its partite sets U and V. The following results were obtained in [10] showing the usefulness of the distance-similar equivalence class to determine the multidimensions of connected graphs.Theorem 1 (see [10]).
LetG be a connected graph such that d
i
m
M
(
G
) is defined. If U is a distance-similar equivalence class in G with U
=
2, then every multiresolving set of G contains exactly one vertex of U.Theorem 2 (see [10]).
IfU is a distance-similar equivalence class in a connected graph G with U
≥
3, then d
i
m
M
(
G
) is not defined.It was shown in [10, 11] that a path is the only one of connected graphs with multidimension 1, and any multiresolving sets of a connected graph cannot contain only two vertices. We state these results in the following theorems.Theorem 3 (see [10, 11]).
LetG be a connected graph. Then d
i
m
M
(
G
)
=
1 if and only if G
=
P
n, the path of order n.Theorem 4 (see [10, 11]).
A connected graph has no multiresolving set of cardinality2
.Last, we are able to determine all pairsk
,
n of positive integers with k
≥
3 and n
≥
3
(
k
-
1
) which are realizable as the multidimension and the order of some connected graph. In order to do this, we present an additional notation. For integers a and b, let [
a
,
b
] be a multiset such that(6)
a
,
b
=
a
,
a
+
1
,
…
,
b
-
1
,
b
if
a
<
b
a
if
a
=
b
∅
if
a
>
b
.Such a multiset is referred to as aconsecutive multiset of integers a and b.Theorem 5.
For every pairk
,
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.Proof.
Letk and n be integers with k
≥
3 and n
≥
3
(
k
-
1
). We consider two cases.
Case
1 (n
=
3
(
k
-
1
)). Let G be a graph obtained from the path P
k
-
1
=
(
u
1
,
u
2
,
…
,
u
k
-
1
) by adding the 2
(
k
-
1
) vertices v
i and w
i for 1
≤
i
≤
k
-
1 and joining v
i and w
i to u
i, as it is shown in Figure 2. Then the order of G is n
=
3
(
k
-
1
). First, we claim that there is no multiresolving set of G with cardinality at most k
-
1. Assume, to the contrary, that there is a multiresolving set S of G such that S
≤
k
-
1. Since a set V
i
=
v
i
,
w
i for 1
≤
i
≤
k
-
1 is a distance-similar equivalence class in G, it follows by Theorem 1 that S contains exactly one vertex of V
i. Without loss of generality, let w
i
∈
S for 1
≤
i
≤
k
-
1. Thus, S
=
k
-
1. Since d
(
w
1
,
w
i
)
=
d
(
w
k
-
1
,
w
k
-
i
) for all 1
≤
i
≤
k
-
1, it follows that m
r
(
w
1
∣
S
)
=
m
r
(
w
k
-
1
∣
S
) and so a set S
=
w
1
,
w
2
,
…
,
w
k
-
1 is not a multiresolving set of G, thereby producing a contradiction. Hence, d
i
m
M
(
G
)
≥
k. Next, we claim that a set W
=
w
1
,
w
2
,
…
,
w
k
-
1
∪
u
1 is a multiresolving set of G. For a vertex x
∈
W, the multirepresentation of x with respect to W is(7)
m
r
x
∣
W
=
0
,
i
∪
3
,
i
+
1
∪
3
,
k
-
i
+
1
if
x
=
w
i
1
≤
i
≤
k
-
1
0
,
k
-
1
if
x
=
u
1
.For 2
≤
i
≤
k
-
1, the multirepresentation of u
i with respect to W is(8)
m
r
u
i
∣
W
=
1
,
i
-
1
∪
2
,
i
∪
2
,
k
-
i
.For 1
≤
i
≤
k
-
1, the multirepresentation of v
i with respect to W is(9)
m
r
v
i
∣
W
=
2
,
i
∪
3
,
i
+
1
∪
3
,
k
-
i
+
1
.Therefore, W is a multiresolving set of G with W
=
k. Hence, d
i
m
M
(
G
)
=
k.
Case
2 (n
>
3
(
k
-
1
)). Let H be a graph obtained from the graph G in Case 1 by adding the path P
=
(
x
1
,
x
2
,
…
,
x
n
-
3
(
k
-
1
)
) and joining x
1 to v
k
-
1 and w
k
-
1, as it is shown in Figure 3. By a similar argument to the one used in Case 1, it is shown that there is no l
-multiresolving set of H with 1
≤
l
≤
k
-
1. We claim that a set W
=
w
1
,
w
2
,
…
,
w
k
-
1
∪
u
1 is a multiresolving set of H. For vertices in V
(
H
)
-
x
1
,
x
2
,
…
,
x
n
-
3
k
-
1, their multirepresentations with respect to W are the same as in Case 1. For 1
≤
i
≤
n
-
3
(
k
-
1
), the multirepresentation of x
i with respect to W is (10)
m
r
x
i
∣
W
=
i
,
i
+
k
-
1
∪
i
+
3
,
i
+
k
.Hence, W is a multiresolving set of H with W
=
k, and so d
i
m
M
(
H
)
=
k.Figure 2
A connected graphG in Case 1.Figure 3
A connected graphH in Case 2.


## 3. Multisimilar Equivalence Relation

In this section, we investigate another equivalence relation on a vertex set of a connected graph. First, we need some additional definitions and notations. LetA
=
{
a
1
,
a
2
,
…
,
a
k
}
∣
a
i
∈
Z
for
1
≤
i
≤
k be a collection of multisets. For an integer c, we define (11)
a
1
,
a
2
,
…
,
a
k
+
c
,
c
,
…
,
c
=
a
1
+
c
,
a
2
+
c
,
…
,
a
k
+
c
,where a
1
,
a
2
,
…
,
a
k
∈
A. Let W be a set of vertices of a connected graph G and let u and v be vertices of G. Amultisimilar relation
R
W with respect to W on a vertex set V
(
G
) is defined by u
R
W
v if there is an integer c
W
(
u
,
v
) such that(12)
m
r
u
∣
W
=
m
r
v
∣
W
+
c
W
u
,
v
,
c
W
u
,
v
,
…
,
c
W
u
,
v
.An integer c
W
(
u
,
v
) satisfying (12) is called amultisimilar constant of
u
R
W
v or simply amultisimilar constant. Clearly, R
W is an equivalence relation on V
(
G
). For each vertex u in V
(
G
), let [
u
]
W denote the multisimilar equivalence class of u with respect to W. Then(13)
x
∈
u
W
if  and  only  if
m
r
x
∣
W
=
m
r
u
∣
W
+
c
W
x
,
u
,
c
W
x
,
u
,
…
,
c
W
x
,
u
,where c
W
(
x
,
u
) is a multisimilar constant. Observe that if x
∈
[
u
]
W, then there is a multisimilar constant c
W
(
x
,
u
) with a property that, for every vertex w
∈
W, there is a corresponding vertex w
′
∈
W such that(14)
d
x
,
w
=
d
u
,
w
′
+
c
W
x
,
u
.With this observation, we may as well say that x
∈
[
u
]
W if and only if there are multisimilar constant c
W
(
x
,
u
) and a bijective function f on W defined as (15)
f
w
=
w
′
whenever
d
x
,
w
=
d
u
,
w
′
+
c
W
x
,
u
.The function f is called amultisimilar function of
x
R
W
u or amultisimilar function if there is no ambiguity. Consequently, it is not surprising that an inverse function f
-
1 is also multisimilar function of v
R
W
u with a multisimilar constant c
W
(
v
,
u
)
=
-
c
W
(
u
,
v
).To illustrate these concepts, consider a vertexu in a connected graph G of Figure 1 and the set W
=
w
,
y
,
z. There is only one vertex x in V
(
G
)
-
u such that x is related to u by a multisimilar relation R
W with a multisimilar constant c
W
(
x
,
u
)
=
-
1; that is, (16)
m
r
x
∣
W
=
m
r
u
∣
W
+
-
1
,
-
1
,
-
1
.Therefore, [
u
]
W
=
u
,
x. Thus, a multisimilar function f of x
R
W
u is defined by (17)
f
w
=
y
,
f
y
=
w
and
f
z
=
z
.Moreover, there is another multisimilar function f
′ of x
R
W
u; that is, (18)
f
′
w
=
w
,
f
′
y
=
y
and
f
′
z
=
z
.The example just described shows an important point that the multisimilar function of any two vertices in the same multisimilar equivalence class with respect to a set W is not necessarily unique.More generally, for a vertexu and a set W of vertices of a connected graph G, let m
r
(
u
∣
W
)
=
r
1
·
a
1
,
r
2
·
a
2
,
…
,
r
l
·
a
l, where a
1
<
a
2
<
⋯
<
a
l and r
i is a repetition number of type a
i for each i with 1
≤
i
≤
l. If u
∈
[
v
]
W, where v
∈
V
(
G
), then it follows by (13) and (14) that, for each type of m
r
(
u
∣
W
), there is a corresponding type of m
r
(
v
∣
W
) such that their repetition numbers are equal. Therefore, we may assume that m
r
(
v
∣
W
)
=
r
1
·
b
1
,
r
2
·
b
2
,
…
,
r
l
·
b
l, where b
1
<
b
2
<
⋯
<
b
l. For each integer i with 1
≤
i
≤
l, let A
i
=
{
w
∈
W
∣
d
(
u
,
w
)
=
a
i
} and B
i
=
{
w
∈
W
∣
d
(
v
,
w
)
=
b
i
}. Then the types of m
r
(
u
∣
W
) partition W into l sets A
1
,
A
2
,
…
,
A
l. On the other hand, W is also partitioned into l sets B
1
,
B
2
,
…
,
B
l depending on the types of m
r
(
v
∣
W
). Hence, the multisimilar function f of u
R
W
v has the property that, for every vertex w
∈
A
i, there is a vertex w
′
∈
B
i such that (19)
f
w
=
w
′
,where 1
≤
i
≤
l. Indeed, there are r
1
!
r
2
!
⋯
r
l
! distinct multisimilar functions of u
R
W
v. These observations yield the following result.Theorem 6.
LetW be a set of vertices of a connected graph G and let u and v be vertices of G such that u
∈
[
v
]
W. Suppose that m
r
(
u
∣
W
)
=
r
1
·
a
1
,
r
2
·
a
2
,
…
,
r
l
·
a
l, where a
1
<
a
2
<
⋯
<
a
l and r
i is a repetition number of type a
i for each i with 1
≤
i
≤
l. Then (i)
m
r
(
v
∣
W
)
=
r
1
·
b
1
,
r
2
·
b
2
,
…
,
r
l
·
b
l for some integers b
1
,
b
2
,
…
,
b
l with b
1
<
b
2
<
⋯
<
b
l,
(ii)
there is a multisimilar functionf of u
R
W
v such that f
(
w
i
)
=
w
i
′, where d
(
u
,
w
i
)
=
a
i and d
(
v
,
w
i
′
)
=
b
i for each i with 1
≤
i
≤
l,
(iii)
there arer
1
!
r
2
!
⋯
r
l
! distinct multisimilar functions of u
R
W
v.By Theorem6, the following result is obtained.Corollary 7.
LetW be a set of vertices of a connected graph G and let u and v be vertices of G such that u
∈
[
v
]
W with a multisimilar constant c
W
(
u
,
v
). Then (i)
ifM
1 and M
2 are the maximum elements of m
r
(
u
∣
W
) and m
r
(
v
∣
W
), respectively, then M
1
=
M
2
+
c
W
(
u
,
v
),
(ii)
ifm
1 and m
2 are the minimum elements of m
r
(
u
∣
W
) and m
r
(
v
∣
W
), respectively, then m
1
=
m
2
+
c
W
(
u
,
v
).Proof.
Suppose thatu
∈
[
v
]
W. Let m
r
(
u
∣
W
)
=
r
1
·
a
1
,
r
2
·
a
2
,
…
,
r
l
·
a
l and m
r
(
v
∣
W
)
=
r
1
·
b
1
,
r
2
·
b
2
,
…
,
r
l
·
b
l, where a
1
<
a
2
<
⋯
<
a
l and b
1
<
b
2
<
⋯
<
b
l. Since M
1 and M
2 are the maximum elements of m
r
(
u
∣
W
) and m
r
(
v
∣
W
), respectively, there are vertices w and w
′ in W such that M
1
=
d
(
u
,
w
)
=
a
l and M
2
=
d
(
v
,
w
′
)
=
b
l. It follows by Theorem 6 that there is a multisimilar function f of u
R
W
v such that f
(
w
)
=
w
′. Then d
(
u
,
w
)
=
d
(
v
,
w
′
)
+
c
W
(
u
,
v
), where c
W
(
u
,
v
) is a multisimilar constant. Thus, (i) holds. For (ii), the statement may be proven in the same way as (i), and therefore such proof is omitted.Next, we are prepared to establish the upper bound for the cardinality of a multisimilar equivalence class of a vertex in a connected graph. To show this, let us present a useful proposition as follows.Proposition 8.
LetW be a set of vertices of a connected graph G and let u and v be vertices of G such that u
∈
[
v
]
W. Then m
r
(
u
∣
W
) and m
r
(
v
∣
W
) have the same minimum (or maximum) element if and only if m
r
(
u
∣
W
)
=
m
r
(
v
∣
W
).Proof.
Ifm
r
(
u
∣
W
)
=
m
r
(
v
∣
W
), then the minimum (and maximum) elements of m
r
(
u
∣
W
) and m
r
(
v
∣
W
) are the same. For the converse, assume that m
1 and m
2 are the minimum elements of m
r
(
u
∣
W
) and m
r
(
v
∣
W
), respectively, such that m
1
=
m
2. Since u
∈
[
v
]
W, there is a multisimilar constant c
W
(
u
,
v
) such that (20)
m
r
u
∣
W
=
m
r
v
∣
W
+
c
W
u
,
v
,
c
W
u
,
v
,
…
,
c
W
u
,
v
.By Corollary 7 (ii), it follows that m
1
=
m
2
+
c
W
(
u
,
v
). Thus, c
W
(
u
,
v
)
=
0. Hence, m
r
(
u
∣
W
)
=
m
r
(
v
∣
W
). Similarly, if m
r
(
u
∣
W
) and m
r
(
v
∣
W
) have the same maximum element, then m
r
(
u
∣
W
)
=
m
r
(
v
∣
W
).Theorem 9.
IfW is a multiresolving set of a connected graph G, then the cardinality of multisimilar equivalence class of each vertex of G with respect to W is at most d
i
a
m
(
G
)
+
1.Proof.
Assume, to the contrary, that there is a vertexv of G such that [
v
]
W has the cardinality at least d
i
a
m
(
G
)
+
2. Since the minimum elements of multirepresentations of vertices in [
v
]
W with respect to W have at most d
i
a
m
(
G
)
+
1 distinct values, there are at least two vertices x and y in [
v
]
W having the same value of the minimum element of m
r
(
x
∣
W
) and m
r
(
y
∣
W
). It follows by Proposition 8 that m
r
(
x
∣
W
)
=
m
r
(
y
∣
W
), contradicting the fact that W is a multiresolving set of G.We can show that the upper bound in Theorem9 is sharp. Consider the path P
n
=
(
v
1
,
v
2
,
…
,
v
n
). We have that d
i
a
m
(
P
n
)
=
n
-
1 and the set W
=
v
1 is a multiresolving set of P
n. Thus, [
v
1
]
W contains all vertices of P
n, and so [
v
1
]
W
=
n.In the last result, we describe the properties of a multisimilar equivalence classes with respect to a set of vertices.Theorem 10.
Letu and v be vertices of a connected graph G and let W be a set of vertices of G. Then (i)
if[
u
]
W
≠
[
v
]
W, then m
r
(
x
∣
W
)
≠
m
r
(
y
∣
W
) for all x
∈
[
u
]
W and y
∈
[
v
]
W,
(ii)
if[
u
]
W
=
u for all u
∈
V
(
G
), then W is a multiresolving set of G.Proof.
(i) Assume, to the contrary, that there exist two distinct verticesx
∈
[
u
]
W and y
∈
[
v
]
W such that m
r
(
x
∣
W
)
=
m
r
(
y
∣
W
). Then there are multisimilar constants c
W
(
x
,
u
) and c
W
(
y
,
v
) such that m
r
(
x
∣
W
)
=
m
r
(
u
∣
W
)
+
c
W
x
,
u
,
c
W
x
,
u
,
…
,
c
W
x
,
u and m
r
(
y
∣
W
)
=
m
r
(
v
∣
W
)
+
c
W
y
,
v
,
c
W
y
,
v
,
…
,
c
W
y
,
v. Therefore, (21)
m
r
u
∣
W
+
c
W
x
,
u
,
c
W
x
,
u
,
…
,
c
W
x
,
u
=
m
r
v
∣
W
+
c
W
y
,
v
,
c
W
y
,
v
,
…
,
c
W
y
,
v
.Thus, m
r
(
u
∣
W
)
=
m
r
(
v
∣
W
)
+
c
W
y
,
v
-
c
W
x
,
u
,
c
W
y
,
v
-
c
W
x
,
u
,
…
,
c
W
y
,
v
-
c
W
x
,
u
. Hence, u belongs to [
v
]
W, which is a contradiction.
(ii) Assume, to the contrary, thatW is not a multiresolving set of G. Then there exist two distinct vertices x and y such that m
r
(
x
∣
W
)
=
m
r
(
y
∣
W
). Hence, y belongs to [
x
]
W, producing a contradiction.


## 4. Final Remarks

The complete graphK
n is only one graph that its dimension is n
-
1 but not so for multidimensions. It follows by [10, 11] that the multidimension of complete graph is not defined. Thus, (5) leads us to the conjecture:IfG is a connected graph such that d
i
m
M
(
G
) is defined, then d
i
m
M
(
G
)
≤
n
-
2.



---

*Source: 8978193-2018-08-01.xml*