![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
Let be a connected graph. Let
be a subset of V with an order imposed on W. The k-vector
is called the resolving vector of v with respect to W. The set W is called a resolving set if
for any two distinct vertices
In this paper we investigate the existence of independent resolving sets in Cartesian product and corona of graphs.
2010 Mathematical Subject Classification Number:
1. Introduction
By a graph we mean a finite, undirected connected graph with neither loops nor multiple edges. The order
and the size
of G are denoted by n and m respectively. For graph theoretic terminology we refer to Chartrand and Lesniak [Citation3].
The distance d(u, v) between two vertices in G is the length of a shortest u-v path in G. Let be an ordered subset of V and let
Then the k-vector
is called the resolving vector of v with respect to W and is denoted by
The set W is called a resolving set of G if
for any two distinct vertices u and v. The minimum cardinality of a resolving set of G is called the metric dimension of G and is denoted by
The concept of resolving set was independently discovered by Harary and Melter [Citation5] and Slater [Citation8]. Slater used the terms locating set and location number. Harary and Malter used the term resolving set and metric dimension.
Many resolving parameters have been formulated and investigated by combining resolving property with another graph theoretic property such as connected, independent or acyclic. For a survey of conditional resolving sets we refer to [Citation7].
The concept of independent resolving set was introduced and studied in [Citation4]. A subset W of V which is both an independent set and a resolving set is called an independent resolving set. The minimum cardinality of an independent resolving set of G is called the independent metric dimension of G and is denoted by This parameter is denoted by ir(G) in [Citation4]. Since ir(G) is used for irredundance number in the study of domination, we prefer to use idim(G) instead of
Not all graphs have an independent resolving set and hence idim(G) is not defined for all graphs. The existence of independent resolving sets in some classes of graphs has been proved in [Citation4]. A characterization of all graphs of order n for which
is given in [Citation4].
Definition 1.1.
[Citation6] Let and
be two graphs. The Cartesian product
is the graph with vertex set
and (v1, v2) is adjacent to (w1, w2) if either v1 = w1 and
or v2 = w2 and
Theorem 1.2.
[Citation2] Let G be a connected graph of order n. Then dim(G) = 1 if and only if G is the path
Theorem 1.3.
[Citation6] Let G1 and G2 be two connected graphs. Then the distance between two vertices (v1, v2) and (w1, w2) in is given by
Definition 1.4.
Let G be a connected graph of order n with Let
be connected graphs. The generalized corona
is the graph obtained from G by joining vi to all the vertices of
Theorem 1.5.
[Citation1] Let G1 and G2 be two connected graphs and let Then every pair of vertices in a fixed row of
is resolved by S if and only if the projection of S onto G1 resolves
Similarly every pair of vertices in a fixed column of
is resolved by S if and only if the projection of S onto G2 resolves
In this article, we investigate the existence of independent resolving sets in generalized corona and Cartesian product of graphs.
2. Independent resolving sets in generalized corona
Metric dimension of corona product of graphs has been studied in Yeno et al. [Citation9]. In this section we investigate the existence of independent resolving sets in generalized corona of graphs.
Let be the generalized corona of G with
The induced subgraph
is denoted by
Definition 2.1.
Let and let
Then
is called the resolving vector of v with respect to Wi in
Theorem 2.2.
The generalized corona has an independent resolving set if and only if for each i with
one of the following holds.
and if
then
and there exists an independent set Wi in Hi such that
for any two distinct vertices u, v in
Proof.
Suppose H has an independent resolving set W. If and
then
for any two distinct vertices in Hi which is a contradiction. Hence
Now, suppose
Since W is independent,
and
for the remaining two vertices of
Hence
and (i) holds. Now, let
and let
Suppose there exist two distinct vertices u, v in Hi such that
Since
for all
it follows that
which is a contradiction. Hence (ii) holds. Conversely suppose (i) or (ii) holds for each i. If
let
where
and
If
let Wi be as in (ii).
We claim that is an independent resolving set of H. Let u and v be two distinct vertices in
If
and
then
for all
If
and
then
for all
for any
If
and
where
then
for all
If
and
then
for all
If
and
then
If
and
then
and
for all
Thus in all cases
Hence W is an independent resolving set of H. □
Corollary 2.3.
Let G be a graph of order n and let If each Hi is a path of order 2 or 3, then
Proof.
If each Hi is a path of order 2 or 3, then and W is an independent resolving set of H and
Hence
Also if W is any independent resolving set of H, then
for all i. Hence
so that
Thus
□
Corollary 2.4.
Let G be a graph of order n and let If
for some i and
then H does not have an independent resolving.
Proof.
Any resolving set W of H contains at least two vertices of Hi and hence W is not independent. □
Example 2.5.
Let G = C4 and let The graph H is given in .
Clearly is a minimum independent resolving of H and hence
This shows that the converse of Corollary 2.3 is not true.
Example 2.6.
Let If
then
If
and
then
If
then
Thus if G is a graph of order n and
then we can have idim(H) < n or idim(H) = n or
Hence the following problem arises naturally.
Problem 2.7.
Let G be a graph of order n and let Characterize graphs H for which
3. Independent resolving sets in Cartesian product
Cáceres et al. [Citation1] have presented several results on the metric dimension of Cartesian product of graphs.
In this section, we investigate the existence of independent resolving sets in Cartesian product of two graphs. Let G1 and G2 be connected graphs of order r and s respectively. Let and
We denote the vertex (vi, wj) in
by
It follows from Theorem 1.3 that
Consider the grid If
then
which does not have an independent resolving set. The following theorem shows that all the other grids have an independent resolving set.
Theorem 3.1.
Let where
and
Then
Proof.
Let Since
it follows that W is an independent set in G.
Hence
if and only if
and
Thus
if and only if xij = xst and hence W is a resolving set of G. It follows from Theorem 1.2 that
□
The following theorem shows that if the independent metric dimension of Cartesian product of two graphs is 2, then one of the two graphs is a path.
Theorem 3.2.
Let G1 and G2 be connected graphs and let If
then G1 or G2 is a path.
Proof.
Let be an independent resolving set of G. We claim that i = s or
Suppose
and
Let vr be the neighbor of vs in a shortest vi-vs path in G1 and let wk be the neighbor of wt in a shortest wj-wt path in
Now,
Also
Hence
Hence
which is a contradiction.
Thus i = s or Hence
or
where W1 and W2 are the projections of W on G1 and G2 respectively. Hence it follows from Theorem 1.2 and Theorem 1.5 that G1 or G2 is a path. □
Theorem 3.3.
Let where
and
Then
Proof.
Let and
Let
and let
We consider two cases.
Case 1. n is odd.
Let and let
Since
it follows that W is an independent set in G. We claim that W is a resolving set of G. Let
Then
(1)
(1)
Now suppose
If
and
then
and
From these two equations we get
which is a contradiction. A similar contradiction arises if
and
Hence it follows that either
and
or j > k and
In both these cases, Equation(1)
(1)
(1) gives
and
Hence i = s and
so that
Thus W is a resolving set of G. Hence
Case 2. n is even.
Let and let
Clearly W is an independent set in G. Now let
and
(2)
(2)
(3)
(3)
Suppose
If
and
or j > k and
then it follows from Equation(2)
(2)
(2) and Equation(3)
(3)
(3) that
and
Hence i = s and
so that
which is a contradiction.
If and
then
Also from Equation(2)
(2)
(2) and Equation(3)
(3)
(3) we have
and
Since
adding these two equations, we get
which is a contradiction. A similar contradiction arises if j > k and
Thus
and hence W is a resolving set of G. Thus
Now let be an independent set in G. We claim that S is not a resolving set of G. We consider three cases.
Case i. and
Let vs be the vertex adjacent to b in a shortest a-b path in Pm and let wt be the vertex adjacent to d in a shortest c-d path in
Hence Ws is not a resolving set of G.
Case ii. a = b and
If then
If a = 1 and
then
If a = 1 and
then
If a = 1 and
then
Thus S is not a resolving set of G. This proof is similar if
Case iii. and
In this case,
Hence S is not a resolving set of G. Thus and hence
□
Theorem 3.4.
Let where
and n is odd. Then
Proof.
Let and
be two copies of the cycle
We denote the vertex (vi, wj) in G by
Let and let
Then
Now, suppose
If or
then
and
Hence
If
and
then
Using the expressions for
and
we get
and
which is a contradiction. A similar contradiction arises in other cases. Thus
implies
Hence W is a resolving set of G and
Also it follows from Theorem 3.2 that
Hence
□
4. Conclusion and scope
Since a characterization of graphs which admit an independent resolving set is an unsolved problem, determining such graphs in various classes of graphs is a significant problem. In this paper we have initiated a study of this problem in corona and Cartesian product of graphs. Similar investigation for other graph classes is an interesting direction for further research.
References
- Cáceres, J., Hernando, C., Mora, M., Pelayo, I. M., Puertas, M. L., Seara, C, Wood, D. R. (2007). On the metric dimension of Cartesian product of graphs. SIAM J. Discrete Math. 21(2): 423–441.
- Chartrand, G., Eroh, L., Johnson, M. A, Oellermann, O. R. (2000). Resolvability in graphs and the metric dimension of a graph. Discrete Appl. Math 105(1-3): 99–113.
- Chartrand, G, Lesniak, L. (2005). Graphs and Digraphs, 4th ed. Boca Raton: CRC.
- Chartrand, G., Saenpholphat, V, Zhang, P. (2003). The independent resolving number of a graph. Math. Bohem. 128(4): 379–393.
- Harary, F, Melter, R. A. (1976). On the metric dimension of a graph. ARS Combin. 2: 191–195.
- Imrich, W, Klavzar, S. (2000). Graph Products, Structure and Recognition, New York: John Wiley & Sons.
- Saenpholphat, V, Zhang, P. (2004). Conditional resolvability in graphs-A survey. Int. J. Math. Math. Sci. 2004(38): 1997–2017.
- Slater, P. J. (1975). Leaves of trees, Proceedings of the sixth Southeastern Conference on Combinatorics, Graph Theory and Computing. Cong. Numer. 14: 549–559.
- Yero, I. G., Kuziak, D, Rodríguez-Velázquez, J. A. (2011). On the metric dimension of corona product of graphs. Comput. Math. Appl. 61(9): 2793–2798.