# Distance-Based Topological Descriptors on Ternary Hypertree Networks

Authors: Yun Yu; D. Antony Xavier; Eddith Sarah Varghese; Deepa Mathew; Muhammad Kamran Siddiqui; Samuel Asefa Fufa
Journal: Complexity
 (2022)

---

## Abstract

Topological indices are numeric parameters which portray the topology of a subatomic structure. In QSAR/QSPR analysis, topological descriptors play a vital role to examine the topology of a network. An interconnection network is a structure whose components are connected physically according to some pattern. In this paper, an interconnection network, ternary hypertree, which is a structural combination of complete ternary tree and hypertree, is introduced. We have evaluated the topological descriptors grounded on the distances for the ternary hypertree. The analytical expressions for Wiener, different types of Szeged, and Mostar indices are determined.


---

## Body

## 1. Introduction

A connected graph having ordern and size n−1 is termed as a tree that contains no cycle. In computer science, trees are designed as data structures. Trees are helpful to store data information in a hierarchical manner and provide insertion and deletion of data. They are also useful in manipulating hierarchical data, making it easy to search information and aid in multistage decision making. One of the basic tree structures which have many applications in the field of computer science is the rooted tree [1, 2]. Rooted tree is a tree that has a root node from where the children arise. The root node is called the parent node [3, 4]. A binary tree is a rooted tree in which every vertex has at the most two children and each child of a vertex is assigned as its left child or right child [5]. A complete binary tree is a rooted tree in which every node has two children-a right child and a left child. Ternary tree which has at the most three children 3x−1,3x,3x+1, where x∈ℤ is a root node, is a rooted tree. Ternary tree is introduced by Barning, a Dutch mathematician in Reference [6]. It is a tool for the ternary search tree which can be used in spell check and as a database when indexing several nonkey fields. In a complete ternary tree, every node has exactly three children.Hypertree of dimensionn is a basic skeleton of complete binary tree, i.e., the vertex x has exactly two children 2x and 2x+1, where x∈2n−1−1, and the vertices on the same level are connected by a horizontal edge with a label difference of 2i−2;2≤i≤n. The hypertree is an interconnection network which has minimum average distance which results in an efficient multicomputer system [7]. It has an excellent combination of characteristics of the hypercube and the binary tree. Recursive hypertrees are modelled as biological networks such as dendrimers [8–10]. The branching of biological networks is not restricted to two branches. With this motivation, we introduce the concept of ternary hypertree. Ternary hypertrees can be modelled as biological networks for protein interactions and to analyze the spread of diseases.The structure of the ternary hypertree is a combination of a complete ternary tree and hypertree. It is a spanning subgraph of the complete ternary tree. We denote ternary hypertree with dimensionn as THTn.The level of root node is 1. The root node gives rise to three children, which is at level 2. We label the root node as 1 and their children as2,3,4. Likewise, if the node is labelled as x; then, the children are labelled as 3x−1,3x,3x+1 where x∈3n−1−1/2. At each level i;1≤i≤n of the ternary hypertree of dimension n has 3i−1 nodes. For a ternary hypertree of dimension n, the network has n levels. There are horizontal edges in the level i,2≤i≤n connecting the nodes with a label difference of 3i−2 along the complete ternary tree structure. See Figure 1.Figure 1
Ternary hypertree of dimension 4.Ternary hypertree consists of3n−1/2 nodes and 3n−3 edges. The vertex connectivity is 4 and edge connectivity is 3. Ternary hypertree of dimension n has a diameter of 2n−3. Also, it is not a regular network. THTn;n≥3 is nonplanar, i.e., it cannot be embedded in a plane and non-Hamiltonian where every vertex can be visited more than once.Real-life problems can be converted to graphical representations using mathematical modelling, especially in the field of biology [11–14]. Networks helps in analysing various health problems by modelling the spread of diseases [15–17]. Topological indices are numeric invariants showing a correlation between the subatomic structure and its physical (as well as chemical) properties [18, 19]. Thus, it characterises the topology of a graph [20, 21]. Topological indices analyse the physical, chemical, and biological characteristics of a synthetic framework [22, 23]. Topological indices are essential in the field of chemistry and pharmacology, notably in nanomedicine. It helps in the study of the properties of networks. These descriptors are used in measuring irregularity, connectivity, centrality, and peripherality in networks [24]. Topological indices for various networks have been studied in recent years [25–28].Computing the topological indices helps in anatomising the properties of the biological network. In the next section, we have discussed some terminologies and two types of topological descriptors (distance-based and degree-based descriptors) of the ternary hypertree are derived and are graphically represented. Section3 concludes the paper with discussion on the possible applications of ternary hypertree.


## 2. Topological Indices

The graphΩ considered in the paper is a simple connected graph. dx,y is used to represent the distance between x and y and is the length of the shortest path connecting the vertices, x and y. For 1≤i≤n, we represent i=n. The cardinality of collection of adjacent vertices of x is termed as the degree of a vertex x, it is denoted by dx [29, 30]. Neighbourhood of a vertex, x is represented by Nx and is defined as follows:(1)Nxxy|Ω=τ∈VΩ:dx,τ<dy,τ,and(2)Mxxy|Ω=e∈EΩ:dx,e<dy,e,We denote the cardinality ofNxxy|Ω and Mxxy|Ω as nxxy|Ω and mxxy|Ω, respectively.Letwv,sv be the vertex weight and vertex strength and let ew,se be the edge weight and edge strength. The notion of strength-weighted graph Ωsw=Ω,Vsw,Esw, where Vsw=wv,sv,Esw=ew,se, was introduced in Reference [31]. For strength-weighted graph Ωsw=Ω,wv,sv,se, the degree of any vertex v∈VΩsw is dΩswx=2svx+∑p∈NΩswxsexp. For xy∈EΩsw, we define(3)nxe|Ωsw=∑p∈nxe|Ωswwvp,mxe|Ωsw=∑p∈nxe|Ωswsvp+∑f∈mxe|Ωswsef.We refer to References [32–34] for the distance-based topological indices. The formulas of these indices for strength-weighted graph Ωsw are given in Table 1 and the degree-based formulas of topological indices of graph Ω are illustrated in Table 2.Table 1
Distance-based topological indices.
Topological indicesMathematical expressionsWiener [31]WΩ=∑x,y⊆VΩwvxwvydx,ySzeged [31]SzΩ=∑xy∈EΩseenxe|Ωswnye|ΩswEdge Szeged [31]SzΩ=∑xy∈EΩseemxe|Ωswmye|ΩswEdge vertex Szeged [31]SzevΩ=12∑xy∈EΩseenxe|Ωswmye|Ωsw+nxe|Ωswmye|ΩswMostar [40]MoΩ=∑xy∈EΩseenxe|Ωsw−nye|ΩswEdge Mostar [40]MoΩ=∑xy∈EΩseemxe|Ωsw−mye|ΩswTotal Mostar [40]MoΩ=∑xy∈EΩseetxe|Ωsw−tye|ΩswPadmakar Ivan [31]PIΩ=∑xy∈EΩseenxe|Ωsw+nye|ΩswTable 2
Degree-based topological indices.
Topological indicesMathematical expressionsFirst Zagreb [35]∑xy∈EΩdx+dySecond Zagreb [35]∑xy∈EΩdxdyRandic [36]∑xy∈EΩ1/dxdyAtom bond connectivity [37]∑xy∈EΩdx+dy−2/dxdySum connectivity [38]∑xy∈EΩ1/dx+dyGeometric arithmetic [39]∑xy∈EΩ2dxdy/dx+dyIn this paper, we considerwv=ew=se=1;sv=0.If the distance of any two vertices inℋ, a subgraph of a graph of Ω, lies in the same subgraph, then the subgraph ℋ is called convex. For Ω, Djoković-Winkler’s relation Θ on EΩ, References [41, 42] can be expressed as follows: if dx,w+dy,z≠dx,z+dy,w, then xy∈EΩ is Θ related with wz∈EΩ. Θ is an equivalence relation in case of partial cubes. Θ partitioned EΩ into convex cuts. Θ∗ (a transitive closure) is an equivalence relation. The edges partition into Θ∗ classes and let Fi;1≤i≤k is the Θ∗ partition set of EΩ. Using Θ∗ relation, we can find the topological indices of any graph [31, 40, 43–45]. For any i∈k, the quotient Ω/Fi graph in which vertex set belongs to the components of Ω−Fi and x,y∈Ω/Fi are adjacent in Ω/Fi if xy∈EΩ, where x∈C1, y∈C2 and where C1,C2 are components. A partition X=X1,X2,…,Xr of EΩ is coarser than Y=Y1,Y2,…,Ys if Xi is the union of one or more sets in Y. To study about the Wiener index, see References [46–48]. We have used Theorem 2.1 and the technique in Reference [48], reduction of original graph Ω into quotient graphs and further into reduced graphs, to compute the Wiener index of ternary hypertree. To compute other distance-based topological indices of ternary hypertree, we use Theorem 1.Theorem 1.
References [49, 50]. “For a connected strength-weighted graphGsw=G,wv,sv,se, letE=E1,E2,…,Ekbe a partition ofEGcoarser thanF. LetX=W,Szv,Sze,Szev,Mo,Moe,Mot,PI. Then,(4)XGsw=∑i=1kXGEi,wvi,svi,sei,wherewvi:VG/Ei⟶ℝ+is defined bywviC=∑x∈Cwvx,∀C∈G/Ei,svi:EG/Ei⟶ℝ+is defined bysviC=∑xy∈Csexy+∑x∈Csvx,∀C∈G/Ei,sei:EG/Ei⟶ℝ+is defined as the number of edges inEisuch that one end inCand the other end inD, for any two connected componentsCandDofG/Ei.Theorem 2.
Ifn≥2, then(1)
WTHTn=32n/4+5×3nn−2/4−32n−3n+2/8+9−3n/4+32+n−32n/8+3n−3/2+3−1+3n−12/4(2)
SzTHTn=33n−2−19×32n+30×3nn−5×3n+6×32nn+39/8(3)
SzeTHTn=33n/18−11×32n+18×3nn+9×3n+32n+1n−33/2(4)
SzevTHTn=33n/36−41×32n/8+33×3nn/4+7×3n/8+32n+1n/2+15/2(5)
PITHTn=5×32n/12−3×3n+21/4(6)
MoTHTn=32n/4−3n+1n+11×3n/2−63/4(7)
MoeTHTn=32n/2−6×3nn+12×3n−81/2(8)
MotTHTn=3×32n/4−9×3nn+35×3n/2−225/4Proof.
For a ternary hypertree of dimensionn, there are 3n−1−1/2+1Θ∗ classes. The Θ classes are as follows:(1)
For2≤i≤n−1,j=3−1+i,k=3, let Sij be the Θ∗− classes containing the edges 3i−1−1/2+⌈j/3⌉+k−13i−2,3i−1/2+j+k−13i−1.(2)
LetS=S1∪S2 be the Θ∗− classes, which consist of the horizontal edges and the edges connecting the first and second level. It comprises of S1=1,2,1,4,3i−1−1/2+j,j+3i−1−1/2+3−2+i,3i−1/2+j,j+3i−1−1/2+2×3−2+i,j+3i−1−1/2+3−2+i,j+3i−1−1/2+2×3−2+i:i=n−1,j=1,3 and S2=3i−1−1/2+j,3i−1−1/2+j+3i−2,3i−1/2+j,j+3i−1−1/2+3i−2×2,3i−1−1/2+j+3i−2,j+3i−1−1/2+3−2+i×2:i=n−1,j=2.
LetFi,i=n−1 be the partition which is coarser than the Θ∗ classes. Define F1=S and Fi,2≤i≤n−1 be the edges joining the levels i and i+1, i.e., Fi=∪jSij.
In general,THTn/Fi is isomorphic to K1,3−i+1+n,i∈1,2,…,n−2. In K1,3−i+1+n,i∈1,2,…,n−2, one vertex is of weight 3n−i−1/2 and edge weight 3n−i−3 and other 3n−i−1 vertices with vertex and edge weight 33i−1/2 and 3i+1−6, respectively. We can see that GHTn/Fn−1 and K4 are isomorphic, with vertex and edge weights 1 and 0 for one vertex and 3n−1−1/2 and 3n−1−1/2 for the remaining adjacent vertices as shown in Figure 2. Figures 3, 4, and 5 give an example for the quotient graph.
Now,WTHTn is calculated as follows:(5)∑i=1−2+nWTHTnFi=32n4+3n×5−2+n4+32n−3n+28+9−3n4+32n32−n−18,WTHTnFn−1=3n−32+3−1+3n−124,WTHTn=32n4+3n×5−2+n4−32n−3n+28+3n32−n−14+32n32−n−18+33n−1−12+33n−1−124,SzTHTn is calculated as follows:(6)SzTHTnFi=3n+1−3n−i+12+3n−3i×34,∑i=1n−2SzTHTnFi=15×3nn4−32n+24−3n+12+32n+1n4+274,SzTHTnFn−1=3n−1−124+13n−32,SzTHTn=33n−2−19×32n+30×3nn−5×3n+6×32nn+398.
The edge-Szeged index of ternary hypertree of dimensionn is as follows:(7)SzeTHTnFi=3n−i3i+1−63n−3i+1,∑i=1n−2SzeTHTnFi=3n18n+3n+1n−21×3n2+92,SzeTHTnFn−1=−15+3n+1+3n−32×3n−1−12,SzeTHTn=33n18−11×32n+18×3nn+9×3n+32n+1n−332.
The edge-vertex Szeged index is as follows:(8)SzevTHTnFi=3n−i33×3i−18×32i4−9×3n4+3×3i×3n2−3,∑i=1n−2SzevTHTnFi=66×3nn−39×32n−9×3n+12×32nn+1088,SzevTHTnFn−1=15×3n−1−21+3×3n/3−33n−1−124,SzevTHTn=33n36−41×32n8+33×3nn4+7×3n8+32n+1n2+152.
The Padmakar Ivan index is as follows:(9)PITHTnFi=3n−i3n−12,∑i=1n−2PITHTnFi=3n−13n−94,PITHTnFn−1=32n−3n+1+186,PITHTn=5×32n12−3×3n+214.
The Mostar index of ternary hypertree is as follows:(10)MoTHTnFi=3n−i−12+3i−12×3n−i−3−3i−12×3×3n−i,∑i=1n−2MoTHTnFi=32n4−3n+1n+5×3n−454,MoTHTnFn−1=3n−92,MoTHTn=32n4−3n+1n+11×3n2−634,MoeTHTnFi=3n−i3n−6×3i+6,∑i=1n−2MoeTHTnFi=32n2−6×3nn+21×3n2−27,MoeTHTnFn−1=3n+1−272,MoeTHTn=32n2−6×3nn+12×3n−812.(11)MotTHTnFi=3n−i3n+12−9×3i+172,∑i=1n−2MotTHTnFi=3×32n4−9×3nn+31×3n2−1534,MotTHTnFn−1=6×3n−1−18,MotTHTn=3×32n4−9×3nn+35×3n2−2254.
The graphical comparison of numerical values of distance-based indices ofTHTn is given in Figure 6.Figure 2
General case of quotient graph and reduced graph. (a)THTn/Fi,1≤i≤n−2,. (b) THTn/Fn−1.
(a)(b)Figure 3
(a)THT4/F1. (b) Quotient graph THT4/F1. (c) Reduced graph.
(a)(b)(c)Figure 4
(a)THT4/F2. (b) Quotient graph THT4/F2. (c) Reduced graph.
(a)(b)(c)Figure 5
(a)THT4/F3. (b) Quotient graph THT4/F3.
(a)(b)Figure 6
Graphical comparison of numerical values of distance-based indices ofTHTn.Theorem 3.
Forn≥2,(1)
M1THTn=3n+2−45(2)
M2THTn=7×3n+1−162(3)
RTHTn=0.23573n−1+3+2×3n−2−2(4)
ABCTHTn=0.62363n−1+3+0.6667×3n−1+0.5270×3n−1−6(5)
SCTHTn=1+3n−2+0.4082×3n−1+0.28873n−1−6(6)
GATHTn=2.828+2×3n−1−6Proof.
Ternary hypertree has3n−3 edges. We divide the edges according to its degrees on either vertex, which is given in Table 1. We denote Fmn as the set of edges xy such that dx=m and dy=n.
M1THTn is calculated as follows:(12)M1THTn=∑xy∈F333+3+∑xy∈F636+3+∑xy∈F666+6=3n−1×6+3n−1+3×9+3n−1−6×12=9×3n−45,
M2THTn is calculated as follows:(13)M2THTn=∑xy∈F333×3+∑xy∈F636×3+∑xy∈F666×6=3n+1+3n−1+3×18+2×3n+1−6×36=21×3n−162.
Randic index ofTHTn is calculated as follows:(14)RTHTn=∑xy∈F3313+∑xy∈F63118+∑xy∈F6616=3n9×13+3n−1+3×118+3n−1−6×16=0.2357×3n−1+3+2×3n−2−2,
ABCTHTn is calculated as follows:(15)ABCTHTn=∑xy∈F3316+∑xy∈F6319+∑xy∈F66112=3n−1+39+3n−16+3n−1−612=0.11113n−1+3+0.1667×3n−1+0.08333n−1−6,
SCTHTn is calculated as follows:(16)SCTHTn=∑xy∈F3316+∑xy∈F6319+∑xy∈F66112=3n−16+3n−1+39+−6+3n−1×112=1+3n−2+0.4082×3n−1+0.28873n−1−6.
The geometric arithmetic index ofTHTn is as follows:(17)GATHTn=∑xy∈F3396+∑xy∈F63189+∑xy∈F663612=3n−1×96+3n−1+3×189+3n−1−6×3612=2.8281+3n−2+2×3n−1−6.
The graphical comparison of numerical comparison of degree-based indices is given in Figure7.Table 3
Partition of edges of ternary hypertree of dimensionn grounded on the degree vertices.
dx,dy;xy∈EΩNo: Of edges3,33n−16,33n−1+36,63n−1−6Figure 7
Graphical representation of numerical values of degree-based indices.


## 3. Conclusion

Hypertree has many chemical applications such as in recursive molecular networks, for example, dendrimers [51]. Also, the topological indices for hypertree are used in the prognosis of physical (as well as chemical) properties of the complex network of molecular and material systems when there are substantial atoms [10, 52–54]. In this article, we have introduced a ternary hypertree, an interconnection network, and evaluated some distance-based and degree-based topological indices of the ternary hypertree. The topological indices of the ternary hypertree may help in determining the chemical properties of complex molecular networks. It can be used to obtain irregularity measures, connectivity measures, centrality measures, and peripherality measures of the ternary hypertree. The degree-based topological indices can help in the study of bioactivity of the ternary hypertree. In future, we can model networks by considering the spread of different viruses and can study their properties. We can also determine the entropy of ternary hypertree in order to analyse data complexity and transmission of information. Also, eccentricity-based topological indices, which help in analysing the toxicological properties, and various topological indices based on different constraints can also be computed. [55].



---

*Source: 4634326-2022-09-28.xml*