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![](https://www.scirp.org/html/5-1200041\d6f960e8-49bf-4e5e-9626-cdf4892dfc04.jpg)
. 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![](https://www.scirp.org/html/5-1200041\7ae4d021-da64-4339-ad79-0508fc0e8fe9.jpg)
. 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,
![](https://www.scirp.org/html/5-1200041\daf9b659-a49e-4f77-9e58-fae18f8e5fd1.jpg)
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,
![](https://www.scirp.org/html/5-1200041\2096210c-0a93-4e7f-8bf5-b034df7bc41f.jpg)
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,
![](https://www.scirp.org/html/5-1200041\d55ae5ba-da13-4920-bd36-780f464bf281.jpg)
and
, ![](https://www.scirp.org/html/5-1200041\e81adae6-2060-484e-9cee-90665797934e.jpg)
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,
![](https://www.scirp.org/html/5-1200041\353155cf-145a-42d3-8a90-0974e2d5d093.jpg)
![](https://www.scirp.org/html/5-1200041\4cd80aa2-04a2-484e-954c-624bd48798c2.jpg)
and
, ![](https://www.scirp.org/html/5-1200041\3330f8aa-3063-44cc-a05d-288a25d40117.jpg)
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