# Distance Measurements Related to Cartesian Product of Cycles

Authors: Xiaoli Qiang; Saima Nazeer; Yu-Ming Chu; Muhammad Awais Umar; Imrana Kousar; Ammara Sehar
Journal: Journal of Mathematics
 (2020)

---

## Abstract

Graph theory and its wide applications in natural sciences and social sciences open a new era of research. Making the graph of computer networks and analyzing it with aid of graph theory are extensively studied and researched in the literature. An important discussion is based on distance between two nodes in a network which may include closeness of objects, centrality of objects, average path length between objects, and vertex eccentricity. For example, (1) disease transmission networks: closeness and centrality of objects are used to measure vulnerability to particular disease and its infectivity; (2) routing networks: eccentricity of objects is used to find vertices which form the periphery objects of the network. In this manuscript, we have discussed distance measurements including center, periphery, and average eccentricity for the Cartesian product of two cycles. The results are obtained using the definitions of eccentricity, radius, and diameter of a graph, and all possible cases (for different parity of length of cycles) have been proved.


---

## Body

## 1. Introduction

Applications of graph theory to computer science, physics, chemistry, biology, social sciences, and statistics open up a new dimension for researchers [1–5]. One of the attributes is distance and its related measurements in the graph. Weighted distance, topological distance, eccentricity, radius, diameter, metric dimension, indices, etc., are such distance-related terms and have received much attention of researchers [6–8]. One of the fundamental questions related to distance measurement is community detection and location of their emergency facilitation within the network [9, 10]. The study of networks such as (1) social networks like Facebook, Twitter, LinkedIn, etc., and (2) biological networks like protein-protein interaction, gene transcription, ecological networks, etc., and statistical inference on these network models have been done extensively in [11, 12]. In distance-based networks, several vertices can have different closeness as well as exactly the same closeness with respect to a particular facility like hospital, electricity, etc. [13–17]. In this paper, we consider the distance measure, vertex eccentricity, and its associated definitions center and periphery. The indices related to vertex eccentricity are discussed in [18, 19]. For an undirected graph, Goddard et al. in [20, 21] have shown the following:(1)radM≤diamM≤2radM.Other proved results are(1)
radKm=diamKm=1 for m≥2(2)
radCm=diamCm=⌊m/2⌋(3)
radKp,m=diamKp,m=2,p,m≥2(4)
radPm=⌈m−1/2⌉, diamPm=m−1Diameter of a tree, random graphs, and bridge graphs are determined in [22, 23], respectively.The eccentricity denoted byecx of a node x in a connected graph M is defined as(2)ecx=Maxdy,x:y∈VM.The radius denoted byradM of a connected graph M is defined as(3)radM=Minecx:x∈VM.The diameter denoted bydiamM of a graph is defined as(4)diamM=Maxecx:x∈VM.In [24], authors introduced average eccentricity denoted by Avgec for a graph M with m number of vertices as(5)AvgecM=1m∑x∈VMecMx.Buckley [25] defined the eccentric set of a nontrivial connected graph and proved the criteria for a nonempty set of positive integers to be an eccentric set of some graphs. Buckley also defined central subgraphs embedding and proved that the central subgraph of a tree is isomorphic to K1 or K2. Dankelmann and Osaye [26] proved results on average eccentricity, k-packing, and k-domination in graphs. They gave the bounds for average eccentricity of a connected graph with independence number. Additionally, they defined the other parameters related to eccentricity: weight function, total weight function, eccentric sequence of tree for given diameter, and k-star. Dankelmann et al. in [27] prove the bounds for eccentricity and average eccentricity of the graph, subgraph, and its complement and when the graph is replaced by a spanning tree or spanning graph. Yu et al. [28, 29] characterize the extremal unicyclic graphs among other m-unicyclic graphs with minimal and second minimal average eccentricity. Ilic [30, 31] discusses the graph transformations which change the eccentricity of a graph. He also solved four conjectures about average eccentricity, clique number, domination, and independent number using the system AutoGraphix.In a graphM, x is an eccentric vertex to y when ecy=dx,y, y is the central vertex if ecy=radM, and y is peripheral if ecy=diamM. A subgraph of M induced by peripheral vertices is called periphery and denoted by PM. CM is the subgraph induced by central vertices, also called the center of M. When all vertices are central vertices and CM=M, then M is called self-centered. Self-centered graphs were introduced by Akiyama et al. in [32], and results were proved about graphs Kp, pK2, ∪i=1nKpi, and V−S1G. Negami and Xu [33] prove the existence of the cycle of length 4 or 5 in a self-centered graph of radius 2, and conversely, if the longest cycle among them for a block vertex has a cycle length 4, then the block is self-centered and radius is 2. Halina Bielak and Maciey syslo [26, 34] investigated that every graph is not periphery of some graph. In graphs with radG=diamG, the center of the graph becomes the same as the graph itself [35].The paper is divided into two sections, the first section describes center and periphery for the Cartesian product of two cyclesCp and Cq for different parity of vertices using definitions of eccentricity, radius, and diameter of a graph with few figures. The second section proves results about average eccentricity of the Cartesian product of two cycles for different parity of number of vertices.


## 2. Center and Periphery for Cartesian ProductCp□Cq

In this section, we will find results related to center and periphery of the Cartesian productCp□Cq for different choices of p and q using the distance-related definitions eccentricity, radius, and diameter. The graph of C4□C3 is shown in Figure 1.Figure 1
The Cartesian productC4□C3.Definition 1 (see [24]).
The Cartesian product of two graphsM and N denoted by M□N is defined as a graph with the vertex set VM×VN, where the two vertices u,u´ and v,v´ are adjacent if and only if either u=v in M and u´ is adjacent to v´ in N or u is adjacent to v in M and u´=v´ in N.
The vertex set and edge set of the Cartesian product of graphs are defined as(6)VCp□Cq=xr,s:1≤r≤p,1≤s≤q,ECp□Cq=xr,sxr+1,s:1≤r≤p−1,1≤s≤q∪xr,sxr,s+1:1≤r≤p,1≤s≤q−1.Theorem 1.
The family of the Cartesian productCp□Cq is self-centered.Proof.
We will prove the result for some choices ofp and q as given in the following cases:Case  1. When p≡0mod2,q≡0mod2, p≥q.Consider the cyclex1,1x1,2x1,3…x1,r…x1,p and choose an arbitrary vertex x1,1 on this cycle:(7)dx1,1,x1,r=r−1,1≤r≤p2+1,dx1,1,x1,r=p2−1,r=p2+2,dx1,1,x1,r=1,r=p,also(8)dx1,1,x1,r=p+1−r,p2+2≤r≤p.In order to locate a vertex at an extreme distance fromx1,1 in Cp□Cq, we have to consider values 1≤r≤p/2+1. Since each x1,r is the neighbor of x2,r and xq,r, therefore, using equations (7) and (8), we have(9)dx1,1,xq,r=dx1,1,x2,r=r,1≤r≤p2+1,(10)dx1,1,xq,r=dx1,1,x2,r=p+2−r,2+p2≤r≤p.Further,x2,r is the neighbor of x3,r and xq,r is the neighbor of xq−1,r, and therefore equations (9) and (10) give(11)dx1,1,xq−1,r=dx1,1,x3,r=r+1,1≤r≤p2+1,dx1,1,xq−1,r=dx1,1,x3,r=p+3−r,p2+2≤r≤p.Moreover,x3,r is the neighbor of x4,r and xq−1,r is the neighbor of xq−2,r; therefore,(12)dx1,1,xq−2,r=dx1,1,x4,r=r+2,1≤r≤p2+1,dx1,1,xq−2,r=dx1,1,x4,r=p+4−r,p2+2≤r≤p.Continuing the same procedure, afterq/2th steps, the vertex xq/2,r would be in the neighborhood of xq/2+1,r which implies(13)dx1,1,x1+q/2,r=r+q2−1,1≤r≤p2+1,dx1,1,xq/2+1,r=p−r+q2+1,p2+2≤r≤p.This meansxq/2+1,p/2+1 is farthest from x1,1. Therefore, ecx1,1=p/2+q/2.Similarly,xq/2+2,p/2+1,xq/2+3,p/2+1,xq/2+4,p/2+1,…,xq/2,p/2+1 are farthest from x2,1,x3,1,x4,1,…,xq,1 in Cp□Cq, respectively.Since the graph is symmetric, each vertex on either cycle has the same eccentricity.(14)radCp□Cq=diamCp□Cq=p2+q2.Consequently, each vertex is a central vertex as well as a peripheral vertex.Case  2. When p≡1,q≡1mod2,p≥q.Consider the cyclex1,1x1,2x1,3…x1,r…x1,p and select a vertex x1,1 from it, and then(15)dx1,1,x1,r=r−1,1≤r≤p−12+1.When values ofr vary between p−1/2+2 and p, the distance dx1,1,x1,r varies between p−1/2 and 1:(16)dx1,1,x1,r=p+1−r,p−12+2≤r≤p.Thus, to locate a farthest vertex fromx1,1 in Cp□Cq, we only consider 1≤r≤p−1/2+1.Eachx1,r is the neighbor of x2,r and xq,r. Therefore, using equations (15) and (16), we have(17)dx1,1,xq,r=dx1,1,x2,r=r,1≤r≤p−12+1,(18)dx1,1,xq,r=dx1,1,x2,r=p+2−r,p−12+2≤r≤p.Further,x2,r is the neighbor of x3,r and xn,r is the neighbor of xq−1,r, and so equations (17) and (18) imply(19)dx1,1,xq−1,r=dx1,1,x3,r=1+r,1≤r≤p−12+1,dx1,1,xq−1,r=dx1,1,x3,r=p+3−r,p−12+2≤r≤p.Moreover,x3,r is the neighbor of x4,r and xq−1,r is the neighbor of xq−2,i. Hence,(20)dx1,1,xq−2,r=dx1,1,x4,r=2+r,1≤r≤p−12+1,dx1,1,xq−2,r=dx1,1,x4,r=p+4−r,p−12+2≤r≤p.Continuing the same procedure, afterq−1/2th steps, the vertex xq−1/2,r would be in the neighbor of xq+1/2,r. Therefore,(21)dx1,1,xq+1/2,r=q−12+r−1,1≤r≤p−12+1,dx1,1,xq+1/2,r=p−r+q−12+1,p−12+2≤r≤p.It means thatxq+1/2,p−1/2+1 is farthest from x1,1. Therefore, ecx1,1=p−1/2+q−1/2. Similarly, xq+3/2,p−1/2+1,xq+5/2,p−1/2+1,xq+7/2,p−1/2+1,…,xq−1/2,p−1/2+1 are farthest vertices from x2,1,x3,1,v4,1,…,xq,1, respectively.Hence,radCp□Cq=diamCp□Cq=p−1/2+q−1/2.Case  3. Consider p≡1mod2,q≡0mod2,p≥q.The verticesx1,1 and x1,r on the cycle x1,1x1,2x1,3…x1,r…x1,p have the following distances:(22)dx1,1,x1,r=r−1,1≤r≤p−12+1,(23)dx1,1,x1,r=p+1−r,p−12+2≤r≤p.This means to locate the farthest vertex fromx1,1 in Cp□Cq, only these values 1≤r≤p−1/2+1 are considered.Since, eachx1,r is the neighbor of x2,r and xq,r, therefore using equations (22) and (23), we have(24)dx1,1,xq,r=dx1,1,x2,r=r,1≤r≤p−12+1,(25)dx1,1,xq,r=dx1,1,x2,r=p+2−r,p−12+2≤r≤p.Further,x2,r is the neighbor of x3,r and xq,r is the neighbor of xq−1,r. Therefore, equations (24) and (25) give(26)dx1,1,xq−1,r=dx1,1,x3,r=r+1,1≤r≤p−12+1,dx1,1,xq−1,r=dx1,1,x3,r=p+3−r,p−12+2≤r≤p.Moreover,x3,r is the neighbor of x4,r and xq−1,r is the neighbor of xq−2,r. Therefore,(27)dx1,1,xq−2,r=dx1,1,x4,r=r+2,1≤r≤p−12+1,dx1,1,xq−2,r=dx1,1,x4,r=p+4−r,p−12+2≤r≤p.Continuing the same procedure, afterq/2th steps, the vertex xq/2,i would be in the neighbor of xq/2+1,i which implies(28)dx1,1,xq/2+1,r=r+q2−1,1≤r≤p−12+1,dx1,1,xq/2+1,r=p−r+n2+1,p−12+2≤r≤p.It meansxq/2+1,p−1/2+1 is farthest from x1,1. Therefore, ecx1,1=p−1/2+q/2. Similarly, farthest vertices from x2,r,x3,r,…,xq,r are xq/2+2,p−1/2+1,xn/2+3,p−1/2+1,…,xq/2,p−1/2+1, respectively. Hence, radCp□Cq=diamCp□Cq=p−1/2+q/2.Case  4. Consider p≡0mod2,q≡1mod2,p≥q.
Since the graph is symmetric, by switching the roles ofp and q, we get the same case as Case 3. Therefore, we have discussed all the possible cases.
Now, it is concluded that the family ofCp□Cq is self-centered for all possible values of p and q.


### 2.1. Illustration

Consider the graphC4□C3 shown in Figure 2 in which eccentricity of every vertex is shown by blue circled numbers. Clearly from Figure 2, all vertices have eccentricity 3. Therefore, the center and periphery for C4□C3 is the graph itself.Figure 2
Center and periphery ofC4□C3.


## 2.1. Illustration

Consider the graphC4□C3 shown in Figure 2 in which eccentricity of every vertex is shown by blue circled numbers. Clearly from Figure 2, all vertices have eccentricity 3. Therefore, the center and periphery for C4□C3 is the graph itself.Figure 2
Center and periphery ofC4□C3.


## 3. Average Eccentricity ofCp□Cq,p≥q

There areq circles in Cp□Cq and each has p vertices. Thus, the total number of vertices in Cp□Cn is equal to the product of p and q. The average eccentricity of Cp□Cq,p≥q, will be discussed in the following cases:Case 1. For p,q≡0mod2,(29)AvgecCp□Cq=1pq∑x∈VMecMx=1pqqpp+q2=p+q2.Case 2. When p,q≡1mod2,(30)AvgecCp□Cq=1pq∑x∈VMecMx=1pqqpp+q−22=p+q−22.Case 3. When p≡1 and q≡0mod2,(31)AvgecCp□Cq=1pq∑x∈VmecMx=1pqqpp+q−12=p+q−12.Therefore,(32)AvgecCp□Cq=q2+p2,p,q≡0mod2,q2+p−12,p≡1andq≡0mod2,q−12+p−12,p,q≡1mod2.Case 4. When p≡1 and q≡0mod2.Since the graph is symmetric, by changing the roles ofp and q, we get Case 3.Thus, all cases have been discussed, and our result is completed.


## 4. Conclusion

In this manuscript, we have discussed distance measurements including center, periphery, and average eccentricity for the Cartesian product of two cycles. The results are obtained using the definitions of eccentricity, radius, and diameter of a graph, and all possible cases (for different parity of length of cycles) have been proved. One of the attributes in applications of graph theory is distance and its related measurements in the graph. Weighted distance, topological distance, eccentricity, radius, diameter, metric dimension, indices, etc., are such distance-related terms and have received much attention of researchers. Along with the distance, the graph operations make the structures somewhat similar to the practical situation. One can be interested in researching the distance-related measurements for different graph operations: corona product, strong product, lexicographic product, etc. The other direction might be of extending these results for one point union of graphs with nonisomorphic copies.



---

*Source: 6371694-2020-11-23.xml*