# Exact Wiener Index of the Direct Product of a Path and a Wheel Graph

Authors: Shi-Jie Duan; Feng Li
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

The direct product is one of the most important methods to construct large-scale graphs using existing small-scale graphs, and the topological structure parameters of the constructed large-scale graphs can be derived from small-scale graphs. For a simple undirected graphG, its Wiener index WG is defined as the sum of the distances between all different unordered pairs of vertices in the graph. Path is one of the most common and useful graphs, and it is found in almost all virtual and real networks; wheel graph is a kind of graph with good properties and convenient construction. In this paper, the exact value of the Wiener index of the direct product of a path and a wheel graph is given, and the obtained Wiener index is only derived from the orders of the two factor graphs.


---

## Body

## 1. Introduction

In this paper, a simple graphG refers to the set of vertices VG and the set of different unordered vertex pairs a,b in VG, i.e., the edge set EG of G. For an edge e=a,b, we say that e connects a,b, the vertices a and b are the endpoints of e, and a and b are adjacent to each other. The number of the elements in VG is the order of the graph G, and size of the graph G is the number of edges in the graph. A graph G is called connected, if given any two vertices vi,vj∈VG, there is a path from vi to vj.The direct product of two given graphsG and H is denoted as G×H, with vertex set(1)VG×H=VG×VH=ai,bj:ai∈VG,bj∈VH.Two different verticesai,bj and ak,bl of the direct product graph G×H are adjacent to each other, if and only if ai,ak∈EG and bj,bl∈EH. We call G and H the factor graphs of the direct product graph G×H, and for convenience, vertex ai,bj is usually represented by aibj.A path is the topological structure of bus network, linear array network, and other important networks. Wheel graph has good connectivity, transitivity, stability, and other characteristics. By combining the two graphs in the way of direct product, the resulting graph will not only inherit their excellent properties but also perform better than the factor graphs in terms of various properties. In this paper, we mainly research the Wiener index of the direct product of a path and a wheel graph, so we review the definitions of paths and wheel graphs next.Let a finite sequencea0e1a1e2a2…an−1enan be composed of vertices and edges, and in this sequence, ei connects ai−1 and ai1≤i≤n. When all the vertices and edges in the sequence are different from each other, the graph composed of vertices and edges in the sequence is called a a0an-path, and the length of the path is n, denoted by Pn+1. The graph obtained by connecting two vertices a0 and an of a a0an-path with an edge is a cycle Cn+1 with order n+1. Connect all vertices of Cn to a new isolated vertex (wheel center), and the resulting graph is a wheel graph of order n+1, denoted by Wn+1; it is obvious that n+1>3. The direct product graph P2×W6 of a path P2 and a wheel graph W6 is shown in Figure 1.Figure 1
G=P2×W6.Wiener index is widely used in many fields and disciplines, such as physical chemistry, biology, and computer science [1–5], giving credit to the pioneering work of the chemist Wiener [6]. In graph theory, Wiener index of a connected graph G is defined as WG=1/2∑a,b∈VG×VGdGa,b, denoted by WG, where dGa,b is the distance between vertices a and b in G. Since the Wiener index was successfully introduced into graph theory, many scholars have done a lot of research on it. This paper is mainly interested in the Wiener index of direct product graphs (to know further about Wiener index of product graphs and other graphs, refer to [7–10]).In 1959, Sabidussi proposed the definition of Cartesian product, strong product, and direct product [11]. Product operations of graphs are effective tools to construct large-scale graphs by using small-scale factor graphs and provide important models for computer connection. By using the graph product methods, large networks can be constructed by factor networks, and all factor networks are subnetworks of the large networks, so the large networks retain the good characteristics of factor networks, and these properties can be well derived from the properties of factor networks. Because of its simple way of connection, direct product has attracted extensive attention of many scholars. Soon after the direct product graph was put forward, Weichsel observed that the direct product graph of two factor graphs is connected while the two factor graphs are connected, and at least one of them is not bipartite [12]. For more than half a century, direct product has been studied by many scholars with different names (such as weak product, Kronecker product, tensor product, cardinal product, and category product), including its matching problem, Hamiltonicity, and connectivity [13–15].The general result of Wiener index of direct product of graphs has not been obtained yet, but many scholars try to make breakthroughs from different types of factor graphs. For example, Hoji et al. [16] researched the Wiener index of the direct product of a connected graph G and a complete graph Kn of order nn≥3. Pattabiraman et al. gave the Wiener index of the direct product of a path and a cycle [17]. In this paper, by designing the minimum routing, we use the transitivity and symmetry of Pm×Wn to calculate the exact Wiener index of it. For more literatures on the product graphs, refer to [18] and [19].


## 2. Main Results

Reviewing Figure1, we find that arranging the vertices of Pm×Wn according to Figure 1 is not conducive to observing the topology of Pm×Wn. So, we rearrange the vertices of Pm×Wn and mark the vertices similar to Figure 1, mark the vertices of Pm as 0,1,2,3,…,m−2,m−1, and mark the vertices of Wn as 0,1,2,3,…,n−2,n−1. Here 0 is the wheel center of Wn; on this premise, the set of vertices of Pm×Wn is labeled ∪i=0m−1∪j=0n−1ij, and if there is ambiguity, we use i,j instead of ij. After rearranging the vertices, we find that Pm×Wn is actually a m-partite graph.In order to observePm×Wn better, we first give an example of P3×W5 (see Figure 2). In addition, we calculate the Wiener index of the direct product graph in Figure 1 and the Wiener index of P3×W6 manually and list the results in Table 1.Figure 2
G′=P3×W5 and G=Pm×Wn.Table 1
Wiener indices ofP2×W6 and P3×W6.
GraphIndexVPmVWnWIP2×W626128P3×W636298Next, we will give the main theorems by combining Figure2 and the properties of the direct product graph (for undefined symbols, refer to Hammack et al. [18]).Theorem 1.
LetP2m be a path of order 2mm>1, with vertices v0,v1,v2,…,v2m−1, and Wn is a wheel graph of order nn>3, with vertices 0,1,2,…,n−2,n−1. The Wiener index of their direct product G=P2m×Wn is(2)WG=4m3+17m−6n2−54mn+48m−243.Proof.
LetSij be the sum of the distances from ij to every vertex kl∈VG, i.e.,(3)Sij=∑kl∈VGdGij,kl,where dGij,kl refers to the distance from ij to kl, and note that the distance from ij to itself is 0. By using the symmetry of G, we can get the following formula:(4)∑i=0m−1∑j=0n−1Sij=∑i=0m−1∑j=0n−1S2m−i+1,j⇒∑i=02m−1∑j=0n−1Sij=2∑i=0m−1∑j=0n−1Sij=2∑i=0m−1∑j=0n−1S2m−1−i,j=2WG⇒WG=∑i=0m−1∑j=0n−1Sij.
According to formula (4), we just need to calculate ∑i=0m−1∑j=0n−1Sij; next, we use the characteristics of wheel graph to simplify the calculation process again.
According to the definition ofWn, if we do not consider the wheel center and the edges associated with wheel center of Wn, then the graph composed of other vertices and edges is a cycle Cn−1. From the transitivity of vertices on a cycle, there is an automorphism of G that maps vertex ij to vertex il, where Sij=Sil, j≠l, and j,l≠0. Therefore, when j≠0, we just need to calculate each Si1 and multiply it by n−1 instead of finding all Sij,j=1,2,3…,n−1. For the case of j=0, we will deal with it separately.
We divide the proof into two cases: in Case 1, we calculate the sum of the distances from vertex∑i=0m−1i1 to all vertices in VG, and in Case 2, we calculate the sum of the distances from vertex ∑i=0m−1i0 to all vertices in VG.Case 1.
Then−1 times of the sum of the distances from vertex 01,11,…,m−1,1 to all vertices in VG, i.e., n−1∑i=0m−1Si1. Because when i=0,1, the distance rule of the distances from vertex 0i to all vertices in VG is a bit special, for the vertices 01 and 11, we cannot share the same distance rule with other vertices, so we give S01 and S11 separately.(5)S01=2n−1+3+3n−3+n2+⋯+2m−1,S11=3+3n−3+2n−1+3+3n−3+n2+3+⋯+2m−2,∑i=2m−1Si1=∑i=2m−1n2+3+⋯+i+3n−2+2n−1+3n−2+n2+3+⋯+2m−1−i=∑i=2m−1ii+1n−2n2+8n−14+2m−1−i2m−in−2n2.
Explanations for the terms appearing in (5) are as follows.
As shown in Figure3, the distances from 01 to vertices 00,02,03,04⋯,0,n−1 are all 2, the distances to vertices 10,12,1,n−1 are all 1, the distances to vertices 13,14,…,1,n−2 are all 3, the distances to vertices 20,21,22,…,2,n−1 are all 2, the distances to vertices 30,31,32,…,3,n−1 are all 3, and so on; the distances from 01 to its farthest vertices 2m−1,1,2m−1,2,2m−1,3,…,2m−1,n−1 are all 2m−1.
Now let us discuss vertex 11, namely, the second equation of formula (5). For vertex 11, there is a column of vertices that lie on its left side, which are vertices 00,01,02,…,0,n−1. The sum of the distances from vertex 11 to these vertices is equal to the sum of the distance from vertex 01 to vertices 10,11,12,…,1,n−2. The same rule applies to ∑i=2m−1Si1; therefore, we give only the shortest path from 01 to VG (Figure 3). By using the structural properties of G and the properties of direct product and formula (5), we give the final result of Case 1 as follows:(6)n−1∑i=0m−1Si1=n−1S01+S11+∑i=2m−1Si1=4m3+17m−6n2+−4m−59mn+42m−183.
Formula (6) is the final result of Case 1, and we will deal with Case 2 in a similar way.Figure 3
The shortest paths from vertex 01 to all vertices inVG.Case 2.
Calculate∑i=0m−1Si0, the sum of the distances from vertices 00,10,20,…,m−1,0 to all vertices in VG. The method of computation is similar to Case 1; we first give the calculation process and then explain the formula by making use of Figure 4, namely, the shortest path graph from vertex 00 to all vertices in VG.(7)S00=2n−1+3+n−1+n2+⋯+2m−1,S10=3+n−1+2n−1+3+n−1+n2+3+⋯+2m−2,∑i=2m−1Si0=∑i=2m−1n2+3+⋯i+3+n−1+2n−1=+3+n−1+n2+3+⋯+2m−1−i=∑i=2m−1ii+1n−2n2+4n+2+2m−i−12m−in−2n2.
Explanations for the terms appearing in formula (7) are as follows.
As shown in Figure4, for vertex 00, the distances from it to vertices 10,20,30,…n−1,0 are all 2, those to the vertex 10 is 3, and those to vertices 11,12,13,…,1,n−1 are all 1, and the distance rule to the other vertices is same as Case 1. The explanations of vertex 10 and vertices ∑i=2m−1Si0 are similar to Case 1; due to space limitation, they will not be repeated here. Now we summarize each term of formula (7), and by using the properties of the direct product, we get the final result of Case 2 as follows:(8)∑i=0m−1Si0=S00+S10+∑i=2m−1Si0=4m3+5mn+6m−63,
Formula (8) is the final result of Case 2.
By combining the above two cases, the Wiener index of the direct product graphG=P2m×Wn is(9)WG=n−1∑i=0m−1Si1+∑i=0m−1Si0=4m3+17m−6n2−54mn+48m−243.
The following theorem gives the Wiener index of the direct product of an odd order pathP2m+1 and a wheel graph Wn. The calculation method of Theorem 2 is roughly the same as Theorem 1, and difference is the order of the path in the two theorems.Figure 4
The shortest paths from vertex 00 to all vertices inVG.Theorem 2.
LetP2m+1 be a path of order 2m+1m>1, with vertices v0,v1,v2,…,v2m, and Wn is a wheel graph of order nn>3, with vertices 0,1,2,…,n−2,n−1. The Wiener index of their direct product G=P2m+1×Wn is(10)WG=4m3+6m2+20m+6n2+−54m−6n+48m3.Proof.
Since the order of the path is2m+1, we use the symmetry of G to get the following formula:(11)∑j=0n−1∑i=0m−1Sij=∑j=0n−1∑i=0m−1S2m−i,j⇒∑j=0n−1∑i=02mSij=2∑j=0n−1∑i=0m−1Sij+∑j=0n−1Smj=2∑j=0n−1∑i=0m−1S2m−i,j+∑j=0n−1Smj=2WG⇒WG=∑j=0n−1∑i=0m−1Sij+12∑j=0n−1Smj.
According to formula (11) , we need to solve only ∑j=0n−1∑i=0m−1Sijand 1/2∑j=0n−1Smj, and the calculation method and process of ∑j=0n−1∑i=0m−1Sijare the same as formula (4) of Theorem 1; therefore, by using formulas (3)–(6), we can give the following result directly:(12)∑j=0n−1∑i=0m−1Sij=8m3+9m2+37m−12n+48−108mn+96m−486.
Now let us calculate1/2∑j=0n−1Smj. Since the graph G is left-right symmetric with respect to the vertices ∑j=0n−1mj, the sum of the distances from ∑j=0n−1mj to all the vertices on their left side is equal to that on their right side, so we can ignore all the vertices on the left side of ∑j=0n−1mj. Figure 5 shows the graph after we delete all the vertices and their associated edges on the left side of ∑j=0n−1mj. We use Tijm≤i≤2m,0≤j≤n−1 to represent the sum of the distances from vertex ij to all vertices in Figure 5. By calculating the sum of the distances from ∑j=0n−1mj to all the vertices in Figure 5, namely, ∑j=0n−1Tmj, we find that the distance from mi to mj0≤i,j≤n−1,i≠j is calculated twice, i.e., 2nn−1. So, we need to subtract nn−1 from ∑j=0n−1Tmj to get 1/2∑j=0n−1Smj.
By using the definition ofWn, if the wheel center and its associated edges are not considered, the remaining vertices and edges are Cn−1. Because of the transitivity of the vertices on circle, we can get Tm1; then, multiply the result by n−1 instead of calculating all ∑j=0n−1Tmj. For Tm0, we will calculate it separately. So, we have(13)Tm0=2n−1+3+n−1+n2+3+⋯+2m−m,Tm1=2n−1+3+3n−3+n2+3+⋯+2m−m,12∑j=0n−1Smj=∑j=0n−1Tmj−nn−1=Tm0+n−1Tm1−nn−1=m2+m+6n2−18n+162.
According to the previous explanation, by combining formulas (12) and (13), we obtain the Wiener index of the direct product graph G=P2m+1×Wn as follows:(14)WG=∑j=0n−1∑i=0m−1Sij+12∑j=0n−1Smj=4m3+6m2+20m+3n2+−54m−3n+48m3.
Recalling the two theorems in the previous paper, it is not difficult to find that the two theorems do not include the Wiener indices of the direct product of pathsP2,P3 and wheel graph Wn, but we can directly derive the results from the proof processes. Therefore, we give them directly in the following corollary.Figure 5
The graph after deleting all vertices and their associated edges on the left of verticesmj0≤j≤n−1.Corollary 1.
The Wiener indices of the direct product of pathsP2,P3 and a wheel graph Wn are(1)
WP2×Wn=5n2−10n+8.(2)
WP3×Wn=11n2−19n+16.
Substituten=6 into the two formulas of Corollary 1, i.e.,(15)WP2×W6=5×62−10×6+8=128,WP3×W6=11×62−10×6+16=298.The results of the two equations in formula (15) are consistent with the results we calculated manually in Table 1, which proves the correctness of Corollary 1.


## 3. Conclusion

Direct product is the simplest standard product for the adjacency between vertices, and it is one of the important methods of network design. The direct product of a path and a wheel graph also has good topological properties. Exact Wiener index of the direct product of a path and a wheel graph describes the overall condition of the distances between each pair of vertices in its vertex set, and further we can get the average distance by using the Wiener index. Therefore, it has theoretical and practical significance to research the Wiener index of the direct product of a path and a wheel graph.



---

*Source: 1077549-2022-02-10.xml*