# On the Metric Dimension of Generalized Tensor Product of Interval with Paths and Cycles

Authors: Song Li; Jia-Bao Liu; Mobeen Munir
Journal: Journal of Mathematics
 (2020)

---

## Abstract

The concept of minimum resolving set for a connected graph has played a vital role in Robotic navigation, networking, and in computer sciences. In this article, we investigate the values ofm and n for which P2⊗mPn and P2⊗mCn are connected and find metric dimension in this case. We also conclude that, for each m, we obtain a new regular family of constant metric dimension. We also give a basis for these graphs and presentation of resolving vector in general closed form with respect to the basis.


---

## Body

## 1. Introduction

The concept of metric dimension and resolving sets were initially drafted for the metric spaces in 1953 in [1], p. 95 but did not receive much attention because of the linear continuum nature of standard Euclidean spaces ℝn. Later, Slater in [2, 3] and Harary and Melter in [4] used these ideas of uniquely determining the location of an intruder in a network and graphs. This idea also paved the way for searching uniquely the receiver of a message on a network. Since then the resolving sets have been widely investigated, see, for instance, [5, 6]. The resolving sets also have useful applications in diverse areas including network discovery and verification [7], strategies for the mastermind games [8], and applications to problems of pattern recognition, image processing, and digital geometry [5]. Chartrand et al. discussed resolvability and its connection with metric dimension of graphs in [9, 10]. Similarly, on another node, a real-world problem is the study of networks which is not centrally controlled but rather distributed. So, it becomes relatively difficult and costly to obtain a map of all nodes and the links between them. One possible solution is to view network from various local positions and combine them to obtain a good approximation for the real network, [11]. Metric dimension has some applications in this respect as well. Buczkowski et al. discussed a general idea of k-dimensional graphs [12]. First, we introduce general terminology related to a graph.A graphG is an ordered pair V,E, where V is the vertex set and E is the edge. The distance between vertices v,w∈V, denoted by dv,w, is defined as the length of the shortest path between v and w, and the diameter of G, denoted by diaG, is defined as the maximum distance among all pairs of vertices in G. A vertex x∈V resolves a pair of vertices v,w∈V if dv,x≠dw,x. A set of vertices W⊆V resolves G if each pair of distinct vertices of G is resolved by some vertex in W. The set W is called the resolving set of G if it resolves G. A resolving set W of G with the least cardinality is called metric basis of G, and this cardinality is the called metric dimension of G denoted by βG. It is a common fact now that β is unique although we may have many metric bases. Actually the choice of a particular matric basis leads us towards the unique coordinate representation of all vertices of a graph. For an ordered subset W=w1,w2,…,wn of vertices and a vertex v in a connected graph G, the representation of v with respect to W is the ordered k-tuple.A lot of work has already been carried out on computation of metric dimension and its other variants related ideas of graphs. Buczkowski et al. [12] calculated the dimension of wheel Wn and arrived at the result that dimWn=2n+2/5 for n≥7. Caceres et al. [13] computed the dimension of fan graphs, fn, and proved that, for n≥7,dimfn=2n+2/5. Tomescu and Javaid proved that the dimension of Jahangir graphs J2n to be dimJ2n=2n/3 for n≥4 [14]. Imran et al. computed the dimension of circulant graphs in [15]. Hussain et al. computed bounds for the metric and partition dimension of generalized Mobius ladders in [16].In the abovementioned cases, metric dimension of all graphs depends upon the number of vertices in the graph. In contrast, one is interested in the list of all families of graphs in which metric dimension remains constant which seems to be an important feature of the family. Authors in [17, 18] discussed some families of graphs with constant metric dimension. Another aspect is the metric dimension of a graph that is some kind of product of two other graphs. One is often interested in relating the dimension of the product graphs with dimensions of the component graphs. Cartesian product of two graphs G and H, denoted by G□H is a graph such that the vertex set of G□H is the Cartesian product VG×VH as a set, and any two vertices u,u′ and v,v′ are adjacent in G□H if and only if either u=v and u′ is adjacent with v′ in H or u′=v′ and u is adjacent with v in G. The metric dimension of the Cartesian products of graphs has been studied in [19]. Authors proved that the metric dimension of G□G is tied in a strong sense to the minimum order of a so-called doubly resolving set in G. Authors also computed bounds on G□H for many examples of G and H. Authors in [20] recursively defined generalized corona product and derived some important results about this product in terms of the dimension of components involved, whereas, in [21], authors computed strong metric dimension of this corona product. Another product is the tensor product, G⊗H of graphs G and H which is a graph such that the vertex set of G⊗H is the Cartesian product VG⊗VH; any two vertices u,u′ and v,v′ are adjacent in G⊗H if and only if u′ is adjacent with v′ and u is adjacent with v. For example, the tensor product of P2 with C4 is .Moradi discussed the tensor product of some graphs in [22]. Jannesari and Omoomi computed metric dimension of lexicographic product of some graphs by introducing a new parameter known as adjacency dimension, [23]. Saputro et al. further extended these results for other graphs in [24]. Javaid et al. computed metric dimension of co-normal product of graphs in [25].In this paper, we discussn-copies of tensor product of P2 with Pn and Cn. This type of product is relatively less studied in the literature as compared to the Cartesian product. In the first stage, we decide about the connectedness of this product. At the second step, we compute the metric dimension of the connected graphs among them. We like to remark that metric dimension of the tensor product of two graphs has not been extensively studied over the years.


## 2. Main Results

We focus first onP2⊗mPn. We compute minimal resolving set for it allowing ∞ as distance between two vertices when there does not exist any path connecting them so they are in different components of a graph. The interesting question is the value of m for which the graph P2⊗mPn is connected. The answer, however, is no in this case. Existence of ∞ as any component of resolving vector clearly indicates that the graph is disconnected. Although we cannot talk about the metric dimensions in these cases but cardinality of minimum removability does make sense as it shows the connectedness of a graph. We actually give the closed representation of all vertices with respect to our selected metric basis in each case.Theorem 1.
(i)
∀m and n≥2,P2⊗mPn is disconnected(ii)
Cardinality of the minimal resolving set is2mProof.
LetW=ui,vj,1,vj,2,…,vj,m, where ui are vertices Pn and vj,k is the vertex of P2 of Kth component. We show that W is a resolving set. For this, we give the representation of any vertex of VP2⊗mPn with respect to W:(1)rw2j+1,ui,1,ui,2,…,um−1,v1W=ax,x=j−1,0≤j≤n−2,1≤i≤2,1≤x≤2m−1,ax,y=∞,1≤i≤2,1≤x≤2m−1,1≤y≤2m,rw2j+1,ui,1,ui,2,…,um−1,v2W=ax,x=j−1,0≤j≤n−2,1≤i≤2,1+2m−1≤x≤2m,ax,y=∞,1≤i≤2,1+2m−1≤x≤2m,1≤y≤2m,rw2j,ui,1,ui,2,…,um−1,v1W=ax,x−1+2m=j−1,1≤j≤n−1,1≤i≤2,1+2m−1≤x≤2m,ax,y=∞,1≤i≤2,1≤y≤2m,1+2m−1≤x≤2m,rw2j,ui,1,ui,2,…,um−1,v2W=ax,x−1+2m=j−1,1≤j≤n−1,1≤i≤2,1≤x≤2m,ax,y=∞,1≤i≤2,1≤x≤2m,1≤y≤2m.
Now, we consider the minimality of the resolving set. If we deleteu1,1,u1,2,…,u1,m,v1 from W, then rw1,u1,1,…,u1,m−1,v1W=rw3,u1,1,…,u1,m−1,v1W=∞,∞,…,∞,∞. So, cardinality of minimum recoverability P2⊗mPn is 2m.Example 1.
Ifm=2 and n=3, then βP2⊗P2⊗P3=4 and W=w1,u1,v1,w1,u2,v1,w2,u1,v1,w2,u1,v1 and resolving vectors with respect to W are(2)w1,u1,v1=0,∞,2,∞,w1,u1,v2=∞,0,∞,2,w1,u2,v1=∞,3,∞,1,w1,u2,v2=3,∞,1,∞,w2,u1,v1=2,∞,0,∞,w2,u1,v2=∞,2,∞,0,w2,u2,v1=∞,1,∞,3,w2,u2,v2=1,∞,3,∞,w3,u1,v1=2,∞,2,∞,w3,u1,v2=∞,2,∞,2,w2,u1,v1=∞,1,∞,1,w3,u2,v2=1,∞,1,∞.
Now, we turn our attention to theP2⊗mCn. In contrast to the above result, we have an interesting result here. For m=1 and n≡1mod2, our graph is connected. Moreover, we also give metric dimension in this case as well.Theorem 2.
(1)
βP2⊗Cn=2.(2)
Cardinality of the minimal resolving set:(3)βP2⊗mCn=2m,ifnis odd,2m+1,ifnis even.(3)
P2⊗mCn is connected iff m=1 and n≡1mod2.Proof.
(1) LetW=u1,v1,u2,v1 be set of vertices, where vk are vertices of P2 and u1 and u2 are adjacent vertices of Cn. We show that W is a resolving set. For this, we give the representation of any vertex of VP2⊗CnW with respect to W:(4)ru2i+1,v1W=2i,2i−1,0≤i≤n−2,ru2i,v1W=n−2i+1,n−2i+2,1≤i≤n−2,ru2i+1,v2W=n−2i,n−2i+1,0≤i≤n−2,ru2i,v2W=2i−1,2i−2,1≤i≤n−2.
We see that all the representations are distinct, implying thatdimP2⊗Cn=2. Now, we prove that W is a minimal resolving set. If we take W=u1,v1, we receive two similar resolving vectors: ru2,v1W=ru2k+1,v1W=2k, which indicates dimension is not 1. So, βP2⊗Cn is 2.
(2) Case 1 (whenn is odd): we compute the general form of resolving vector in this case.
LetW=ui,vj,1,vj,2,…,vj,m, where vk are vertices of P2 and ut and u2 are vertices of Cn. We show that W is a resolving set. For this, we give the representation of any vertex of VP2⊗mC2k+1 with respect to W:(5)rw2l+1,ui,1,…,ui,m−1,v1W=ax,x=2l,0≤l≤k,ax,x+2m−1=2k+1−2l−1,0≤l≤k,ax,y=∞,rw2l,ui,1,…,ui,m−1,v1W=ax,x=2k−2l+3,1≤l≤2k−2,ax,x+2m−1=2l+1,1≤l≤2k−2,ax,y=∞,rw2l+1,ui,1,…,ui,m−1,v2W=ax,1+2m−x=2l−1,0≤l≤k,ax,3+2m−x=2k−2l+2,0≤l≤k,ax,y=∞,rw2l,ui,1,…,ui,m−1,v2W=ax,1+2m−x=2l−1,1≤l≤k,ax,3+2m−x=2k−2l+3,1≤l≤k,ax,y=∞,where i=1,2, 1≤x≤2m−1, and 1≤y≤2m.
We see that all the representations are distinct, implying thatβP2⊗mCn≤2m,m≧2. Now, we prove that W is a minimal resolving set. If we delete ui,vj,1,vj,2,…,vj,m from W, we receive two similar resolving vectors: rw1,u1,1,…,u1,m−1,v1W=rw3,u1,1,…,u1,m−1,v1W=∞,…,∞,2k,∞,…,∞, where 2k appears at 2m−1th position, which shows W is the minimal resolving vector.Example 2.
Ifm=2 and n=3, then βP2⊗P2⊗C3=4 and W=w1,u1,v1,w1,u2,v1,w2,u1,v1,w2,u2,v1. P2⊗P2⊗C3 and resolving vectors with respect to W are(6)w1,u1,v1=0,∞,∞,∞,w1,u1,v2=∞,∞,∞,1,w1,u1,v3=2,∞,∞,∞,w1,u2,v1=∞,0,∞,∞,w1,u2,v2=∞,∞,1,∞,w1,u2,v3=∞,2,∞,∞,w2,u1,v1=∞,∞,0,∞,w2,u1,v2=∞,1,∞,∞,w2,u1,v3=∞,∞,2,∞,w2,u2,v1=∞,∞,∞,2,w2,u2,v2=1,∞,∞,∞,w2,u2,v3=∞,∞,∞,0.Remark 1.
The above example and picture show that graph is disconnected. This holds generally for this case.
Case 2 (whenn is even): let W=ui,vj,1,vj,2,…,vj,m. We show that W is a resolving set. For this, we give the representation of any vertex of VP2⊗mC2k with respect to W.When1≤i,j≤2, 1≤x≤2m, and 1≤y≤2m−1,(7)rw2l+1,ui,1,…,ui,m−1,v1W=ax,x=2l,0≤l≤1,l,l=2,k=3,l+2,l=2,k>3,2k−2l,3≤l≤2k−1,k≥4,ax,x+2m+1−1=2l−1,0≤l≤1,2k−2l+1,2≤l≤k−1,k≥3,ax,y=∞.When2m≤x≤2m+1,(8)rw2l+1,ui,1,…,ui,m−1,v2W=ax,x−1=2l,0≤l≤1,l,l=2,k=3,l+2,l=2,k>3,2k−2l,3≤l≤2k−1,k≥4,ax,x+1=2l−1,0≤l≤1,2k−2l+1,2≤l≤k−1,k≥3.When1≤i,j≤2, 1≤x≤2m, and 1≤y≤2m−1,(9)rw2l,ui,1,…,ui,m−1,v1W=ax,x=2l−1,l=1,l=2,k>2,2l−3,l=2,k=2,2k−2l+1,3≤l≤2k,k≥3,ax,x+1=2l−2,1≤l≤2,k≥2,2k+2l+2,3≤l≤k,k≥3,ax,y=∞.When2m≤x≤2m+1,(10)rw2l,ui,1,…,ui,m−1,v1W=ax,x=2l−1,l=1,l=2,k>2,2l−3,l=2,k=2,2k−2l+1,3≤l≤2k,k≥3,ax,x+1=2l−2,1≤l≤2k,k≥2,2k+2l+2,3≤l≤k,k≥3,ax,y=∞.
If we deleteui,vj,1,vj,2,…,vj,m from W, we receive two similar resolving vectors rw1,u1,1,…,u1,m−1,v1W=rw3,u1,1,…,u1,m−1,v1W=∞,…,∞,2k,∞,…,∞, where 2k appears at 2m−1th position, which shows W is the minimal resolving set.
(3) From the above resolving pattern, we can argue this result by presence of∞ at any place.Remark 2.
The same result can be proved by [22] by the agreement that the tensor product of two graphs is disconnected when both factors are bipartite and connected.Example 3.
Ifm=2 and n=4, then βP2⊗P2⊗P4=8 and W=w1,u1,v1,w1,u1,v2,w1,u2,v1,w1,u2,v2,w2,u1,v1,w2,u1,v2,w2,u2,v1,w2,u2,v2 and resolving vectors with respect to W are(11)w1,u1,v1=0,∞,∞,∞,∞,∞,∞,1,w1,u1,v2=∞,0,∞,∞,∞,∞,1,∞,w1,u2,v1=∞,∞,0,∞,∞,1,∞,∞,w1,u2,v2=∞,∞,∞,0,1,∞,∞,∞,w2,u1,v1=∞,∞,∞,1,0,∞,∞,∞,w2,u1,v2=∞,∞,1,∞,∞,0,∞,∞,w2,u2,v1=∞,1,∞,∞,∞,∞,0,∞,w2,u2,v2=1,∞,∞,∞,∞,∞,∞,0,w3,u1,v1=2,∞,∞,∞,∞,∞,∞,1,w3,u1,v2=∞,2,∞,∞,∞,∞,1,∞,w3,u2,v1=∞,∞,2,∞,∞,1,∞,∞,w3,u2,v2=∞,∞,∞,2,1,∞,∞,∞,w4,u1,v1=∞,∞,∞,1,2,∞,∞,∞,w4,u1,v2=∞,∞,1,∞,∞,2,∞,∞,w4,u2,v1=∞,1,∞,∞,∞,∞,2,∞,w4,u2,v2=1,∞,∞,∞,∞,∞,∞,2.


## 3. Conclusions

In the end, we like to summarize our main outcomes. First, noticeable point is the disconnectedness of allP2⊗mPn. The sum and substance of this article is the connectedness of P2⊗mCn for m=1 and n≡1mod2 and metric dimension in this case is 2. So, we obtain a regular family of graph with constant metric dimension 2, which is decomposable into paths and cycles. From network point of view, only this family is significant. However, for the remaining families, we can find minimum resolving set and its cardinality. We conclude this article with(12)βP2⊗mCn=2m,ifnis odd,2m+1,ifnis even.



---

*Source: 2168713-2020-08-30.xml*