Abstract
If G is a connected graph, the distance d (u,v) between two vertices u,v ∈ V(G) is the length of a shortest path between them. Let W = {w1, w2, ..., wk} be an ordered set of vertices of G and let v be a vertex of G . The repre-sentation r(v|W) of v with respect to W is the k-tuple (d(v,w1), d(v,w2), …, d(v,wk)). . If distinct vertices of G have distinct representations with respect to W , then W is called a resolving set or locating set for G. A re-solving set of minimum cardinality is called a basis for G and this cardinality is the metric dimension of G , denoted by dim (G). A family ? of connected graphs is a family with constant metric dimension if dim (G) is finite and does not depend upon the choice of G in ?. In this paper, we show that dragon graph denoted by Tn,m and the graph obtained from prism denoted by 2Ck + {xkyk} have constant metric dimension.
1. Notation and Preliminary Results
If 
is a connected graph, the distance 
between two vertices 
is the length of a shortest path between them. Let 
be an ordered set of vertices of 
and let 
be a vertex of
. The representation of the 
with respect to 
is denoted by 
is the
. If distinct vertices of 
have distinct representations with respect to
, then 
is called a resolving set or locating set for 
[1]. A resolving set of minimum cardinality is called a metric basis for 
and its cardinality is the metric dimension of
, denoted by
. The concepts of resolving set and metric basis have previously appeared in the literature (see [1-14]).
For a given ordered set of vertices 
of a graph
, the ith component of 
is 0 f and only if
. Thus, to show that 
is a resolving set it sufficient to verify that 
for each pair of distinct vertices 
.
Motivated by the problem of uniquely determining the location of an intruder in a network, the concept of metric dimension was introduced by Slater in [2] and studied independently by Harary et al. [3]. Applications of this invariant to the navigation of robots in networks are discussed in [4] and applications to chemistry in [1] while applications to problems of pattern recognition and image processing, some of which involve the use of hierarchical data structures are given in [5].
By denoting 
the join of 
and
, a 
is 
for 
and 
(also known as
) is obtained from the 
by alternately deleting 
spokes. Caceres et al. [6] found the metric dimension of fan 
and Tomescu et al. [7] found the metric dimension of
. Also Tomescu et al. [8] the partition and connected dimension of wheels.
Chartrand et al. proved:
Theorem 1: [1] A graph 
has metric dimension 
if and only if 
is a path.
Hence paths on 
vertices constitute a family of graphs with constant metric dimension. Similarly, cycles with 
vertices also constitute such a family of graphs as their metric dimension is 2. Since 
are the trivalent plane graphs obtained by the cartesian product of the path 
with a cycle
, hence they constitute a family of 
-
with constant metric dimension. Also Javaid et al. proved in [9] that the plane graph 
constitutes a family of regular graphs with constant metric dimension as 
for every
.
Let 
be a family of graphs of order 
obtained from a prism 
as shown in Figure 1 and Figure 2 respectively, by deleting the spokes 
for
. We prove the following.
Theorem 2: Let 
with 
, then 
for
.
Let 
be a cycle with vertex set 
and 
be a path with vertex set
. Dragon graph 
as shown in Figure 3, is a graph of order 
obtained by identifying 
of 
with 
of
. We prove the following.
Theorem 3: For all 
.
2. Proofs
Proof of the Theorem 2: By Theorem 1,
. We only need to show that 
is a resolving set for
, which is obviously of minimal cardinality.
Case (a) When 
for 
Representations of all vertices from 
are as follows,
It is easy to check that all the above representations are distinct. For example, suppose that 
for some fixed 
and
. Then 
and
, a contradiction.
Case (b) When 
for 
Representations of vertices from 
are as follows,
All the above representations are also distinct.
Proof of the Theorem 3: By Theorem 1, 
. We only need to show that there is a resolving set 
of cardinality 2.
Case (a) When 
for 
The set 
is a resolving set for the graph
. Representations of all vertices from 
are as follows,
and
, 
It is easy to check that all the representations are distinct. For example, suppose that 
for some fixed s and j. Then 
because
, a contradiction.
Case (b) When 
for 
The set 
is a resolving set for the graph
. Representations of all vertices from 
are as follows,
and
, 
All the above representations are distinct.
3. Acknowledgements
This research is partially supported by FAST-National University of Computer and Emerging Sciences, Peshawar, Bahauddin Zakariya University, Multan and Higher Education Commission of Pakistan.
NOTES