# A New Method to Find the Wiener Index of Hypergraphs

Authors: Yalan Li; Bo Deng
Journal: Discrete Dynamics in Nature and Society
 (2020)

---

## Abstract

The Wiener index is defined as the summation of distances between all pairs of vertices in a graph or in a hypergraph. Both models—graph-theoretical and hypergraph-theoretical—are used in mathematical chemistry for quantitatively studying physical and chemical properties of classical and nonclassical organic compounds. In this paper, we consider relationships between hypertrees and trees and hypercycles and cycles with respect to their Wiener indices.


---

## Body

## 1. Introduction

LetG be a simple connected graph with vertex set VG and edge set EG. For u,v∈VG, let dGu,v be the distance between the vertices u and v in G, and let WGu=∑v∈VGdGu,v be the sum of distances between u and all other vertices of G. The Wiener index of G is defined as follows [1]:(1)WG=∑u,v∈VGdGu,v=12∑u∈VGWGu.LetH be a connected hypergraph with vertex set VH and edge set EH, where VH is nonempty and each edge e∈EH is a nonempty subset of VH. If each edge contains exactly k vertices, where k≥2, then a hypergraph H is called k-uniform. It is obvious that a 2-uniform hypergraph H corresponds to an ordinary graph. The degree dHv of a vertex v∈VH is the number of edges of H which contains the vertex v. The order of H is the cardinality of its vertex set VH.Foru,v∈VH, a path from u to v in H is defined to be a sequence of distinct vertices and edges v0,e1,v1,…,vp−1,ep,vp such that vi−1,vi∈ei for any i=1,…,p, where v0=u and vp=v. For any u,v∈VH, if there exits a path from u to v, then H is connected. A k-uniform hypergraph H with VH=v1,…,vn and EH=e1,…,em, where ei=vi−1k−1+1,…,vi−1k−1+k,i=1,…,m, is called a k-uniform loose path and denoted by Pn,k. A hypercycle Cp of length p in H is a sequence v0,e1,v1,…,vp−1,ep,vp, p≥2, of distinct vertices (with the sole exception that v0≡vp) and distinct edges such that vi−1,vi∈ei, i=1,…,p. A hypertree is a connected hypergraph with no hypercycles. A k-uniform hypertree with m edges has exactly 1+k−1m vertices. For a k-uniform hypertree H of order n, if there is a disjoint partition VH=u∪V1∪⋯∪Vm of the vertex set VH such that V1=⋯=Vm=k−1, and EH=u∪Vi:1≤i≤m, then H is called a k-uniform hyperstar centered at u and denoted by Sn,k. In particular, S1,k is a hypergraph with a single vertex, and Sk,k is a hypergraph with a single edge.LetH be a k-uniform hypergraph with vertex set VH=v1,…,vn. For u,v∈VH, the distance between u and v in H is denoted by dHu,v. The Wiener index WH is defined as the summation of distances among all unordered pairs of distinct vertices u,v in H:(2)WH=∑u,v⊆VHdHu,v.Especially, the summation of distances from the vertexu to any other vertex is denoted by WHu=∑v∈VHdHu,v. Obviously, we have WH=1/2∑u∈VHWHu.Hypergraph theory has found applications in chemistry [2–7], showing a higher accuracy of molecular structure, that is, the higher accuracy of the model and the greater diversity of the behavior of its invariants. As an important descriptor of molecular structures, the Wiener index of a graph has many applications as well [8–13].In this paper, we show relationships between Wiener indices for hypertrees and trees and for hypercycles and cycles with respect to some transformations. LetT be a k-uniform hypertree with at most two vertices whose degrees are not less than 2 in each edge of T. The following formulas are proved for a k-uniform hypertree T and a tree T of order n obtained from T by transformations:(3)WT=k−12WT−n−1k−12,and for a k-uniform hypercycle Cn and a cycle Cn obtained from C by transformations:(4)WCn=k−12WCn+n2k−12,ifnis odd,k−12WCn+n2k−12−n2k−2,ifnis even.


## 2. Hypertrees and Trees

To prove (3), we need additional definitions and notations.LetT be a k-uniform hypertree with at most two vertices whose degrees are not less than 2 in each edge of T. Any two edges of T have at most one common vertex which is called a joint vertex; otherwise, it is called a nonjoint vertex.We get a treeT from the hypertree T as follows: (1) in T, we pick a nonjoint vertex in each pendent edge and pick all joint vertices to form vertex set VT; (2) if two vertices of VT are in the same edge of the hypertree T, then we connect them with an edge in T. A 4-uniform hypertree T and its corresponding tree T are shown in Figure 1.Figure 1
The 4-uniform hypertreeT and the induced tree T.The following notation is used in the rest of the paper. Ink-uniform hypertree, the joint vertex is denoted by bj,j≥1. The nonjoint vertex of each pendent edge ei in a hypertree is denoted by ai. The nonjoint vertex in the nonpendent edge is denoted by ci. Figure 2 illustrates the notation above. If e is a pendent edge, we use VT\ve\bto denote delete all vertices in edge e except joint vertex b from VT.Figure 2
Thek-uniform hypertree T and the induced tree T.Since there arek−1 nonjoint vertices in each pendent edge and k−2 nonjoint vertices in a nonpendent edge, the number of vertices in the induced tree T is n. The following equations hold for a hypertree T and induced tree T:(5)ET=ET=n−1,WTai=k−1WTai,WTbi=k−1WTbi,(6)2WT=k−12∑ai∈TWTai+k−1∑bi∈TWTbi+k−2∑ci∈TWTci.Lemma 1.
LetT be a hypertree with joint vertices bi and nonjoint vertices ci in each nonpendent edge ei, i=1,…,s. Then, the following equation holds:(7)∑bi∈VTWTbi−∑ci∈VTWTci=ETk−1=n−1k−1.Proof.
By induction on the number of edges, letET=3; then, either T is a k-uniform hyperstar SVT,k centered at vertex b or T is a k-uniform loose path of length 3.
IfT is a k-uniform hyperstar SVT,k centered at vertex b, then there are no nonjoint vertices ci∈VT, and hence we have(8)∑bi∈VTWTbi−∑ci∈VTWTci=WTb=3k−1.
IfT is a k-uniform loose path of length 3, then T has two joint vertices b1 and b2. Choosing one nonjoint vertex c2∈e2, by (5), we have(9)WTb1+WTb2−WTc2=4k−1+4k−1−5k−1=3k−1.
LetET>3, then we choose any pendent edge e∈ET connecting to joint vertex b, and consider T′=VT\ve\b,ET\e. We also choose one nonjoint vertex ci (i=1,2,…,r) from nonpendent edge on the left of b. It can be seen that there is a joint vertex bi for each ci in the same edge. Then, it has the similar case for the right side of b (see Figure 3).
Since the verticesci and bi belong to the same edge in T and T′, they have the same increasing quality Δi for their Wiener indices such that WTbi=WT′bi+Δi and WTci=WT′ci+Δi. By the inductive hypothesis, we have(10)∑bi∈VT′WT′bi−∑ci∈VT′WT′ci=ET′k−1=ET−1k−1.
Thus, we obtain(11)∑bi∈VTWTbi−∑ci∈VTWTci=∑bi∈VT,bi≠bWTbi+WTb−∑ci∈VTWTci=∑bi∈VT′,bi≠bWT′bi+∑bi∈VT′,bi≠bΔi+WT′b+k−1−∑ci∈VT′WT′ci−∑ci∈VT′Δi=∑bi∈VT′WT′bi−∑ci∈VT′WT′ci+k−1=ET−1k−1+k−1=ETk−1=ETk−1=n−1k−1.Figure 3
Ak-uniform hypertrees T.Theorem 1.
LetT be an n-vertex tree obtained from the hypertree T. Then,(12)WT=k−12WT−n−1k−12.Proof.
By the definition of the Wiener index of a hypergraph, we have(13)2WT=k−12∑ai∈VTWTai+k−1∑bi∈VTWTbi+k−2∑ci∈VTWTci=k−12∑ai∈VTWTai+∑bi∈VTWTbi−k−1k−2∑bi∈VTWTbi+k−2∑ci∈VTWTci=2k−12WT−k−1k−2∑bi∈VTWTbi+k−2∑ci∈VTWTci=2k−12WT−k−2∑bi∈VTWTbi−∑ci∈VTWTci.
Then,(14)WT=k−12WT−k−22∑bi∈VTWTbi−∑ci∈VTWTci.
By Lemma1, we get(15)WT=k−12WT−n−1k−12.Corollary 1.
LetSt,k be a k-uniform hyperstar of order t. Then,(16)WSt,k=t−12−t−1k−22.Proof.
ByWSt−1/k−1+1=t−1/k−12 and from Theorem 1, we have(17)WSt,k=k−12WSt−1/k−1+1−t−1k−1+1−1k−12=k−12t−1k−12−t−1k−1k−12=t−12−t−1k−22.Corollary 2.
LetPt,k be a k-uniform loose path of order t. Then,(18)WPt,k=k−12t−1/k−1+23−t−1k−22.Proof.
It follows from Theorem1 and by WPn=n+13.


## 3. Hypercycles and Cycles

Let us consider the hypercycleCn with n joint vertices bi, i=1,…,n. If bi and bj, i≠j, are in the same edge in Cn, then we connect them with an edge and get an n-vertex cycle Cn from the hypercycle Cn. We denote by ai a nonjoint vertex in each edge ei, i=1,…,n. The following statement gives us the relationship between Wiener indices of Cn and Cn.Theorem 2.
(19)WCn=k−12WCn+n2k−12,ifnis odd,k−12WCn+n2k−12−n2k−2,ifnis even.Proof.
Ifn is odd, the following equations are obtained by the definition of Wiener index:(20)2WCn=n1+1+2+2+⋯+n−12+n−12=n3−n4,WCnbi=n2+2n+1k−14−n+12,WCnai=n2+4n−1k−14−n+12,WCn=12nWbi+12nk−2Wai=k−12n3−n4+nn2+4n−14k−1k−22=k−12n3−n4+n3−n8+n22k−1k−2=k−1WCn+WCn+n22k−1k−2=k−12WCn+n2k−12.
Ifn is even, then by (5) and (6) we have the following equations:(21)2WCn=n1+1+2+2+⋯+n−22+n−22+n2=n34,WCnbi=n2+2nk−14−n2,WCnai=n2+4nk−14−n+22,WCn=12nWbi+12nk−2Wai=k−12n3−4n4+n3+4n24k−1k−22+n2=k−122WCn−n+2WCn+n2k−1k−22+n2=k−12WCn+n2k−12−n2k−2.
Table1 presents the Wiener index for the k-uniform hypercycles Ci and their corresponding cycles Ci, 2≤i≤7.Table 1
The Wiener index ofk-uniform hypercycles and corresponding cycles.
WC2=k−12+4k−12−k−2WC2=1WC3=3k−12+9k−12WC3=3WC4=8k−12+16k−12−2k−2WC4=8WC5=15k−12+25k−12WC5=15WC6=27k−12+36k−12−3k−2WC6=27WC7=42k−12+49k−12WC7=42



---

*Source: 8138942-2020-06-11.xml*