ABSTRACT

Given a graph, a set is a resolving set if for each pair of distinct vertices there is a vertex such that. A resolving set containing a minimum number of vertices is called a minimum resolving set or a basis for. The cardinality of a minimum resolving set is called the resolving number or dimension of and is denoted by. A resolving set is said to be a star resolving set if it induces a star, and a path resolving set if it induces a path. The minimum cardinality of these sets, denoted respectively by and are called the star resolving number and path resolving number. In this paper we investigate these resolving parameters for the hypercube networks.

1. Introduction

A query at a vertex discovers or verifies all edges and non-edges whose endpoints have different distance from In the network verification problem [1], the graph is known in advance and the goal is to compute a minimum number of queries that verify all edges and non-edges. This problem has previously been studied as the problem of placing landmarks in graphs or determining the metric dimension of a graph [2]. Thus, a graph-theoretic interpretation of this problem is to provide representations for the vertices of a graph in such a way that distinct vertices have distinct representations. This is the subject of the papers [3-5].

For an ordered set of vertices and a vertex in a connected graph, the code or representation of with respect to is the -vector

where is the distance between the vertices and. The set is a resolving set for if distinct vertices of have distinct codes with respect to. Equivalently, for each pair of distinct vertices there is a vertex such that The minimum cardinality of a resolving set for is called the resolving number or dimension and is denoted by.

2. An Overview of the Paper

The concept of resolvability in graphs has previously appeared in literature. Slater [4,5] introduced this concept, under the name locating sets, motivated by its application to the placement of a minimum number of sonar detecting devices in a network so that the position of every vertex in the network can be uniquely determined in terms of its distance from the set of devices. He referred to a minimum resolving set as a reference set and called the cardinality of a minimum resolving set as the location number. Independently, Harary and Melter [3] discovered this concept, but used the term metric dimension, rather than location number. Later, Khuller et al. [2] also discovered these concepts independently and used the term metric dimension. These concepts were rediscovered by Chartrand et al. [6] and also by Johnson [7] while attempting to develop a capability of large datasets of chemical graphs.

It was noted in [8] that determining the metric dimension of a graph is NP-complete. It has been proved that the metric dimension problem is NP-hard [2] for general graphs. Manuel et al. [9] have shown that the problem remains NP-complete for bipartite graphs. There are many applications of resolving sets to problems of network discovery and verification [1], pattern recognition, image processing and robot navigation [2], geometrical routing protocols [10], connected joins in graphs [11] and coin weighing problems [12]. This problem has been studied for trees, multi-dimensional grids [2], Petersen graphs [13], torus networks [14], Benes networks [9], honeycomb networks [15], enhanced hypercubes [16] and Illiac networks [17].

Many resolving parameters are formed by combining resolving property with another common graph-theoretic property such as being connected, independent, or acyclic. The generic nature of conditional resolvability in graphs provides various ways of defining new resolving parameters by considering different conditions. In general, a connected graph can have many resolving sets. It is interesting to study those resolving set whose vertices are located close to one another. A resolving set of is connected if the subgraph induced by is a nontrivial connected subgraph of. The minimum cardinality of a connected resolving set is called connected resolving number and it is denoted by [18]. In this paper we introduce a new resolving parameter called star resolving number. A resolving set is said to be a star resolving set if the subgraph induced by is a star and a path resolving set [19] if induces a path. In this paper we show the existence of star and path resolving sets in hypercube networks.

3. Topological Properties of Hypercube Networks

The hypercube is a very popular, versatile and vertextransitive interconnection network. When the dimension of hypercube increases, the cardinality of its vertex set increases exponentially. The effectiveness of parallel computers is often determined by its communication network. The interconnection network is an important component of a parallel processing system. A good interconnection network should have less topological network cost and meanwhile keep the network diameter as shorter as possible [20].

Definition 3.1. Let denote the graph of -dimensional hypercube,. The vertex set

Two vertices

and are adjacent if and only if they differ exactly in one position. See Figure 1.

The hypercube has vertices and edges. It is -regular and its diameter is Further it is bipartite, Hamiltonian if and Eulerian if is even [21]. It has been proved in [22] that dim. The bound is tight for, and it is not tight for. A laborious calculation verifies that is resolved by the 4-vertex set {00000, 00011, 00101, 01001}. Caceres

et al. [22] have determined dim for small values of by computer search; the values are shown in the following table:

4. Star Resolving Number

We begin this section by defining a star and a star resolving set.

Definition 4.1. An -dimensional star, denoted by is a graph with one vertex of degree and vertices of degree 1. The vertex of degree is called the hub of

Definition 4.2. A set is said to be a star resolving set if resolves and if it induces a star. The minimum cardinality of is called the star resolving number and is denoted by.

Remark 1. It is clear that for any graph. In a star resolving set the maximum distance between any two locations (vertices) is 2.

We now proceed to identify a star resolving set in a hypercube network It is clear that there are four copies of in We denote them as, , and. Figure 2 exhibits the four copies of in.

Let. A vertex or

is called the of if.

Note that vertices in, at distance 1 from are not considered as images of. If is the image of in then is called the pre-image of.

The next result which we state as Lemma 1 is crucial to our work. We omit the proof as this result has been proved in [16] for enhanced hypercubes.

Lemma 4.1. Let and let

be the image of. Let be any vertex in. Then.

Lemma 4.2. Let. Let and be the images of. Then and are equidistant from every vertex of

Proof. Since the shortest paths from and to any vertex of pass through, the conclusion follows.

Lemma 4.3. Let Then

Proof. The subcube of is regular and hence it contains. Now there exist vertices and such that are equidistant from every vertex of and in particular from every vertex of This implies

Lemma 4.4. Let. Then.

Proof. We prove the theorem by induction on.

Base Case: Let and where and It follows from the definition of hypercube edges that is adjacent to both and It is easy to check that is a resolving set for Figure 3 shows the distinct codes of vertices in with respect to Since induces it is a star resolving set for.

Now assume that the result is true for the hypercube Let where be a star resolving set for Here is the hub and it is adjacent to all Moreover Divide into four copies

and There exist vertices

and having the same codes with respect to every vertex of and in particular with respect to every vertex of Hence cannot resolve and We exhibit a resolving set for Define where is a vertex

either in or Clearly is adjacent to

We claim that is a resolving set for

Case 1: or or

Since and since and are isomorphic to by induction hypothesis resolves and The same argument applies to the following cases.

1) and

2) and

Case 2: and

We need to prove that for some in Let

be the images of and respectively.

Case 2.1:

In this case

Case 2.2:

Now and are resolved by some in Hence and consequently

Case 3: and

The proof is similar to Case 2.

Case 4:

Let and be the images of and respectively. There are three possibilities

or or and. The conclusion will follow by Case 1 and Case 2.

Case 5: and

Let and be the images of and respectively. Since is resolved by there exist a such that This implies that

Lemmas 3 and 4 imply the following result.

Theorem 4.1. Let Then

5. Path Resolving Number

In this section we determine a path resolving number for hypercube networks.

Definition 5.1. [19] A resolving set of is a path resolving set for if the graph induced by is a path. The minimum cardinality of is called path resolving number and is denoted by

Lemma 5.1. Let Then

Proof. Let be the path in Now cannot resolve as there are vertices and such that they are equidistant from every vertex of in particular from every vertex of P Since there exist a path in

Lemma 5.2. Let Then

Proof. Proceeding as in Lemma 4 we conclude that

is a path resolving set for

Lemma 5 and Lemma 6 imply the following result.

Theorem 5.1. Let Then

6. Conclusion

In this paper we have introduced a new resolving parameter called a star resolving number. We have determined the star resolving number and path resolving number for hypercube networks. The problem is open for architectures like Benes and Butterfly networks.

REFERENCES

NOTES

^*This research is supported by The Major Research Project—No. F. 38- 120/2009(SR) of the University Grants Commission, New Delhi, India.