For a set of vertices in a connected graph , the multiplicative distance of a vertex with respect to is defined by If for each pair of distinct vertices of , then is called a multiplicative distance-locating set of . The minimum cardinality of a multiplicative distance-locating set of is called its multiplicative distance-location number . If for each pair of distinct vertices of , then is called an external multiplicative distance-locating set of . The minimum cardinality of an external multiplicative distance-locating set of is called its external multiplicative location number . We prove the existence or non-existence of multiplicative distance-locating sets in some well-known classes of connected graphs. Also, we introduce a family of connected graphs such that exists. Moreover, there are infinite classes of connected graphs for which exists as well as infinite classes of connected graphs for which does not exist. A lower bound for the multiplicative distance-location number of a connected graph is established in terms of its order and diameter.
Let be a connected graph and
let be an
ordered set of vertices in . If
, the -vector of with respect to is defined by where is the distance between and . The set is
called a locating set if for every pair of distinct vertices , . It is also called a
resolving set. The -vector is called the locating code of
with respect to . The cardinality of a minimum locating
set in is called the location
number of and it is denoted by
. In 1975 and later in 1988,
Slater [1,2] introduced
the concept of “Locating Set” of a graph G. Independently, in 1976,
Harary and Melter [3]
discovered these concepts as well but used the term Metric Dimension,
rather than location number. Let
be a subset of . The distance
of a vertex with respect to is defined by .
If for each
pair of distinct vertices of
, then is called a distance-locating set of
. In 2003, Chartrand et al. [4] defined the concept
“Distance-Locating Set” of a graph G and the minimum cardinality of a
distance-locating set of G is the distance-location number . They found the relationship
between and . Further, they found the
existence of distance-locating sets in some well-known classes of
connected graphs and proved that no distance-locating set in a connected
graph G has cardinality 2 or 3.
Moreover, there are infinite classes of connected graphs G for which
exists as well as
infinite classes of connected graphs G for which doest not exist. Also, they
found the lower bound for the distance-location number of a connected
graph in terms of its order and diameter.
Motivated by the concept Distance-Locating Set of a graph we introduce the new concept
“Multiplicative Distance-Locating Set” of a graph G and we define the
cardinality of a minimum multiplicative distance-locating set of G as
the multiplicative distance-location number . Then we find the
relationship between and
Also, we find the
existence of multiplicative distance-locating sets in some well-known
classes of connected graphs and we prove that no multiplicative
distance-locating set in a connected graph G has cardinality 2.
Moreover, we find an infinite classes of connected graphs such as
complete graph and star graph for which does not exist. Also, we
find that the path is the
only connected graph G of diameter 2 such that exists. We define the new
class of connected graph , obtained by identifying any two
consecutive vertices of with
the and vertices of , for which exists. Also, we find the
lower bound for the multiplicative distance-location number of a
connected graph in terms of its order and diameter.
Chartrand et al. [4]
defined the concept External Distance-Locating Set of G and the
cardinality of a minimum external distance-locating set of G is the
external location number . Further, they found the
relationship between and
and studied the external location number of some well-known classes of
connected graphs.
Motivated by the concept External Distance-Locating Set of a graph G,
we introduce the new concept “External Multiplicative Distance-Locating
Set” of a graph G and the cardinality of a minimum external
multiplicative distance-locating set of G is the external multiplicative
location number .
Further, we find the external multiplicative location number of some
well-known classes of connected graphs. Also, we introduce the new
concept “Magic Locating Set” of a graph G and we determine the magic
location number of some well-known classes of connected graphs.
2. The Multiplicative
Distance-Location Number
For a set of vertices in a
connected graph the
multiplicative distance of a vertex in with respect to is defined by If , then
we assign to . If for each
pair of distinct vertices of
then is called a multiplicative
distance-locating set of . A
minimum multiplicative distance-locating set of is a multiplicative distance-locating
set of minimum cardinality and this cardinality is the multiplicative
distance-location number . The following results
describe a relationship between and .
Proposition 1. Every multiplicative
distance-locating set of a graph is a locating set.
Proof. On the contrary, assume that the multiplicative
distance-locating set is not a locating set. Then there exists
two distinct vertices
such that . That is,
. Then . Therefore , which is a
contradiction to the fact that is
a multiplicative distance-locating set of .
Corollary 1. If is a connected graph such that exists, then .
The following Theorem 1 shows that the path is the only connected graph of
order with .
Theorem 1. Let be a connected graph of order . Then if and only if .
Proof. Let be a path on vertices. Since for , is a minimum
multiplicative distance-locating set of . Therefore, . Conversely, suppose
. Let be a minimum
multiplicative distance-locating set for G. Then for each vertex of G is a non-negative integer less
than . Since , are distinct, there exists a
vertex in G such that . Consequently the diameter of
G is . Hence .
Proposition 2. No multiplicative
distance-locating set in a connected graph G consists of two vertices of
Proof. Suppose is a multiplicative distance-locating set for Then , which
is a contradiction.
In the case of distance-locating set of a graph there is no distance-locating set with
exactly three vertices of for any
graph However, multiplicative
distance-locating set of a graph may consists of three vertices of For example, for the following graph
,
is a minimum
multiplicative distance locating set and hence . In order to give examples
of other graphs G for which does not exist, we now
make some observations. In a graph , the nieghbourhood of a vertex in is the set consisting of all vertices which are
adjacent to . The closed
neighbourhood is
Proposition 3. If and are distinct vertices of a connected
graph G such that either or , then
every multiplicative distance-locating set of G contains exactly one of
and .
Proof. Let
and . Suppose S is a
multiplicative distance-locating set for Case 1. Suppose .
If , then and are having the same distance apart from
each vertex of G. Therefore, , which is a
contradiction to the fact that S is a multiplicative distance-locating
set. Similar proof holds when . Case 2. Suppose .
The proof is similar to the case 1.
Corollary 2. If is a connected graph containing three
distinct vertices , and such that either or , then does not exist.
In a graph , if , then is called an end-vertex.
Corollary 3. If is a connected graph such that exists, then every vertex
of G is adjacent to at most two end-vertices.
The converse of Corollary 3 does not necessarily hold. For example, in
the following graph every vertex
of is adjacent to at most two end
vertices, but does
not exist.
We have verified this fact by considering all possible cases.
Corollary 4. If , then and do not
exist.
Proof. Immediately follows from Corollaries 2 and 3.
Next we show that the path
is the only connected graph of
diameter 2 such that
exists.
Theorem 2. If is a connected graph of diameter 2 for
which exists, then
.
Proof. Let be a
minimum multiplicative distance-locating set for G and let . Suppose . Since diameter of G is 2 and , by Theorem 1, . By Proposition 2, . Suppose . Let . Then ,
and . Since is a
multiplicative distance-locating set, and hence
. Since diameter
of is 2, without loss of
generality, we may assume that , . Then , and Since has diameter 2, either or . If , then . Therefore, , which is a
contradiction. If , then
. Therefore, , which is a
contradiction. Thus, is not a
multiplicative distance-locating set for Hence assume that . Let be the subgraph of
induced by Since has diameter 2, for each , it follows that is uniquely determined by
vertices of since for the vertices which are adjacent to . Since is nontrivial and diameter of is ,
contains at least two vertices
and such that . Suppose . Since has diameter 2, and . Hence is not a multiplicative
distance-locating set for .
A graph is a -partite graph if can be partitioned into subsets such that is an edge of if and are belong to different partite sets.
If, in addition, every two vertices in different partite sets are joined
by an edge, then is a complete
-partite graph. If for , then we denote this
complete -partite graph by . The complete
-partite graphs are aslo referred
to as complete multiplartite graphs.
The following result provides another well-known class of graphs for
which does not
exist.
Corollary 5. If is a complete multipartite graph of
order at least 4 that is not complete, then does not exist.
Now, we define a family of connected graph such that
exists.
Definition 1. Let be a path on vertices and let be a cycle on vertices. The graph is obtained by
identifying any two consecutive vertices of with the and vertices of as shown in the following Figure 1,
Figure 1
Theorem 3. For , , .
Proof.Case 1. Suppose is even, . Let be the vertices of as shown in the above Figure 1.
Let be a subset of the vertex
set of .
Then Certainly,
for each pair , of distinct integers and
and for each pair of distinct integers . Since and ,
for each pair , of distinct integers . The factors of , and are: where
, where
and where
.
We claim that for every two integers , . First we discuss when
varies from 1 to and varies from 1 to . If or ,then . We consider the following cases:
Suppose . Then
(a) Suppose . Then . This
implies , which is a
contradiction.
(b) Suppose . Then . This
implies .
Therefore, , which is a
contradiction to the fact that is
a positive integer.
(c) Suppose . Then . This
implies that 4=2, which is a contradiction.
(d) Suppose . Then .
Hence , which is a
contradiction.
(e) Suppose . Then .
Thus, , which is a
contradiction.
(f) Suppose . Then .
This implies .
Since , it has
no real solution, which is a contradiction.
(g) Suppose . Then .
This implies .
Since , it has
no real solution, which is a contradiction.
Thus, for every two integers , . Since and ,
for every two integers , . Next
we claim that for every two integers , . First we discuss when
varies from 1 to and varies from 1 to . If or ,
then . Therefore, .
Suppose . Then
.
If , then the
proof is similar to the above case. Thus,
for every two integers , .
Since and ,
for every two integers , . Next
we claim that for every two integers . If or , then .
Suppose . Then
. If
, then the proof
is similar to the first case. Thus,
for every two integers . From the above three cases, for any
two pair of distinct vertices
of .
Therefore, S is a multiplicative distance-locating set for . Hence, when is even.
Case 2. Suppose is odd, .
Let be the vertices of as shown in the Figure 2.
Figure 2
Let be a subset of the vertex
set of .
Then By case 1, for any
two pair of distinct vertices
of .
Therefore, is a multiplicative
distance-locating set for . Thus, for is odd. Hence
.
Corollary 6. The multiplicative distance
location number of is either 3 or 4.
Proof. Since is not a path, the proof follows from
Theorem 1 and Proposition 2
Now we establish a lower bound for the multiplicative
distance-location number of a connected graph in terms of its order and
diameter. Let be a connected
graph of order . For a subset
of , define
Observation 4. Let be a connected graph of order and diameter . If is a multiplicative distance-locating
set for G with ,
then .
Proof. Suppose is a
multiplicative distance-locating set for Then the numbers are distinct. The
set contains
distinct numbers. Therefore, Since is a multiplicative distance-locating
set, and , and . Thus, Combining (1) and
(2),
we get, .
Observation 5. If is a connected graph of order n2 and diameter d2 for which exists, then .
Proof. Let be a
multiplicative distance-locating set for G and let . By Observation 4, . Therefore, . Thus .
3. The
External Multiplicative Location Number of a graph
We shown in Section 2, for many graphs G, does not exist. However,
there is a closely related parameter that is defined for every graph.
For a set of vertices in a
connected graph the
multiplicative distance of a vertex with respect to is defined by If for each pair of distinct vertices of , then is called an external multiplicative
distance-locating set of The
cardinality of a minimum external multiplicative distance-locating set
of is called the external
multiplicative location number of It is denoted by .
Proposition 4. Every external multiplicative
distance-locating set is a locating set.
Proof. Let be an
external multiplicative distance-locating set for Then the numbers are distinct.
Let be any two distinct
vertices of
If , then .
Suppose . If
, then , which is a
contradiction. Therefore, .
Suppose and . Then the locating code of
the vertex with respect to S,
contains the zero vector.
Since , does not contain the zero
vector. Therefore, . Thus, from the above three cases, is a locating set.
Since the vertex set of is an
external multiplicative distance-locating set, exists for every graph
Since every multiplicative
distance-locating set is an external multiplicative distance-locating
set and since every external multiplicative distance-locating set is a
locating set, we have the following.
Theorem 6. For every connected graph . Moreover, if is a connected graph G of order for which exists, then .
In Theorem 1 the path of order is the only connected graph with
. It is straight
forward to show that the path
is also the only connected graph of order with .
Theorem 7. Let be a connected graph G of order . Then if and only if .
It is shown that the complete graph of order is the only connected graph of
order with , while does not exist by
Corollary 6. Certainly for all n2 as well. On the other hand, is not the only connected graph of
order with external
multiplicative location number .
Theorem 8. If is an regular connected graph of order and diameter then .
Proof. Suppose is an
regular connected graph of order
and diameter Because of Theorem 7, it suffices to
show that for each integer with
, there is no
external multiplicative distance-locating set of consisting of vertices. Assume to the contrary, that
there is an external multiplicative distance-locating set of order in Let be an external
multiplicative distance-locating set for where . Let . For each , where , let be the number of vertices of that are adjacent to , and let be the number of vertices of that are not adjacent to . Thus, , , and
, for all with . Since , for all with . Since is an
external multiplicative distance-locating set for , all numbers are distinct. Therefore,
. Since , all numbers are distinct and all numbers are distinct. Let be the subgraph
induced by . Then for all with . Since the
numbers are distinct, are distinct, . Therefore, no two
vertices of have the same degree,
which is impossible. Hence .
As an immediate consequence of Theorem 8 we obtain the
external location number of the Petersen graph.
Corollary 7. The Petersen graph has external
location number 9.
Next we determine the external location number of the complete
bipartite graphs.
Theorem 9. For integers with ,
Proof. Assume that . Let and be the partite sets
of . If then by Theorem 8 . So we may
assume that . Every external
multiplicative distance-locating set of contains at least vertices from and at least vertices from . Thus, . Let
. Then and . Suppose . Then
which is a contradiction.
Therefore, . Thus,
is an external multiplicative distance-locating set for . Since , is the minimum external multiplicative
distance-locating set for .
Therefore, .
4. The Magic Location Number
of a graph
Let be a connected graph with
vertex set Let be a subset of We define the distance of a vertex
with respect to by If for each pair of distinct vertices of , then is called a magic locating set of The cardinality of a minimum magic
locating set of is called the
magic location number of It is
denoted by . Every
distance-locating set is not a magic locating set and every external
distance-locating set is not a magic locating set.
The following Theorem 10 characterizes graph with
Theorem 10. Let be a connected graph of order . Then if and only if contains a vertex of degree .
Proof. Suppose . Let be a minimum magic
locating set for . Then for each pair of distinct vertices of . Assume that for some , where . Then there exists a
path in .
Therefore, and , which is a contradiction.
Thus, for all . Hence, is adjacent to all the vertices of
. Therefore, .
Conversely, assume that
contains a vertex of degree .
Let be a vertex of such that . Let . Then for all . Therefore, is a minimum magic locating set for
. Hence, .
Corollary 8. The magic location number of the
graphs is
1.
In Theorem 11 and Theorem 12 we determine the
magic location number of an even cycle and the complete bipartite
graphs.
Theorem 11. If is an even cycle, then .
Proof. Let be an even cycle. Let be a
subset of . Then for and for . Hence is a magic locating set for . Therefore, . By Theorem 10 .
Theorem 12. For , .
Proof. Let be a
complete bipartite graph with vertex set where and . Let be a subset of Then for and for . Hence is a magic locating set for Therefore, . By Theorem 10 .
Theorem 13 shows that the magic location number of a
path of order is less than or equal to .
Theorem 13. If is a path on vertices, then .
Proof. Let be a path on vertices. Let be a subset of the vertex set of . Then and . Thus, is a magic locating set for . Therefore, .
5. Conclusion
We have defined some new concepts Multiplicative Distance-locating
set, multiplicative distance location number, External Multiplicative
location number and magic location number of graphs. We have discussed
the existence or non-existence of these numbers for some well known
classes of connected graphs. For future study we would like to propose
the following open problems.
If is a connected graph of
diameter 3 for which
exists, then what about
For what values of and
.
For what values of and
, .
Does equality holds in Theorem 13. Based on our
experience we believe that equality holds.
Acknowledgment
The authors would like to thank the two referees for their useful
suggestions and comments.
References:
Slater, P. J., 1975. Leaves of trees. Congressus
Numerantium, 14, pp.549-559.
Slater, P. J., 1988. Dominating and
reference sets in graphs. Journal of Mathematical and Physical
Sciences, 22, pp.445-455.
Harary, F. and Melter, R. A., 1976. On
the metric dimension of a graph. Ars Combinatoria, 2,
pp.191-195.
Chartrand, G., Erwin, D., Slater, P. J. and Zhang, P., 2003.
Distance-location number of graphs. Utilitas Mathematica, 63,
pp.65-79.