ABSTRACT

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 with respect to is the -tuple. If distinct vertices of have distinct representations with respect to, then is called a resolving set or locating set for. A resolving set of minimum cardinality is called a basis for and this cardinality is the metric dimension of, denoted by. A family of connected graphs is a family with constant metric dimension if is finite and does not depend upon the choice of in. In this paper, we show that dragon graph denoted by and the graph obtained from prism denoted by 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.

REFERENCES

NOTES

^*Corresponding author.