# On Degree-Based Topological Indices for Strong Double Graphs

Authors: Muhammad Rafiullah; Hafiz Muhammad Afzal Siddiqui; Muhammad Kamran Siddiqui; Mlamuli Dhlamini
Journal: Journal of Chemistry
 (2021)

---

## Abstract

A topological index is a characteristic value which represents some structural properties of a chemical graph. We study strong double graphs and their generalization to compute Zagreb indices and Zagreb coindices. We provide their explicit computing formulas along with an algorithm to generate and verify the results. We also find the relation between these indices. A 3D graphical representation and graphs are also presented to understand the dynamics of the aforementioned topological indices.


---

## Body

## 1. Introduction

Chemical graph theory is an important topological field of mathematical chemistry that deals with mathematical modelling of chemical compound structures. A molecular structure of a compound consists of many atoms. Specially, hydrocarbons are chemical compounds which consist of carbon and hydrogen atoms. A graph consisting of hydrocarbons is known as a molecular graph which represents the carbon structure of a molecule [1].We consider a simple molecular graph, sayG, which consists of nonhydrogen atoms and covalent bonds. In graph theory, the nonhydrogen atoms are represented by a set of vertices V=VG and the covalent bonds with the set of edges E=EG. The number of atoms and bonds in a structure is represented by n=V and m=E, respectively. The valency of an atom is represented by ℜGv, and it is known as the degree of vertex v∈VG, which also represents the number of adjacent (or neighboring) vertices of V. A set consisting of neighboring vertices of v is known as open neighborhood and denoted as Nv=w∈VG:vw∈EG. If the vertex v is included in open neighborhood, then the set of vertices is called closed neighborhood, and it is denoted as Nv=Nv∪v.A double graphDG is generated by taking two copies of a graph G and connecting every vertex vi in one copy with the opened neighborhood Nvi of the corresponding vertex with its second copy. For details, see Figure 1 in which a path graph P4 and its double graph are presented. A strong double graph SDG is generated by taking two copies of a graph G and connecting every vertex vi in one copy with closed neighborhood Nvi=Nvi∪vi of the corresponding vertex with its second copy. For details, see Figure 2 in which a strong double graph of P4 and its k-iterated strong double graph are presented.Figure 1
The graphP4 and its double graph. (a) P4. (b) DP4.
(a)(b)Figure 2
The strong double graph ofP4 and its generalization. (a) SD∗1P4. (b) SD∗2P4.
(a)(b)A complementG¯ of a graph G consists of the same set of vertices, where two vertices v and w are adjacent by an edge vw if and only if they are not adjacent in G. Hence, vw∈EG¯⇔vw∉EG. A complement of a graph consists of a number of edges and the degree of vertex v which are represented as m¯=n2−m and dG¯v=n−1−ℜGv, respectively.A molecular descriptor is known as the topological index provides specific information about the structure of molecules. In graph theory, the molecular structure is considered as a graphG. The topological index is also known as the connectivity index [2, 3]. Topological indices are largely applied in chemistry to develop the quantitative structure-activity relationship (QSAR) in which the characteristics of molecules can be correlated with their chemical structures [4]. The physicochemical properties of a molecule can also be explained through topological indices. The first index of a chemical graph was introduced by Harold Wiener [5] in 1947 as an aid to determining the boiling point of the paraffin compound. This index is known as the Wiener index and defined as WG=∑u,v⊆VGdu,v, where the notation du,v represents the distance between u and v.A topological index is defined as a functionT:ψ⟶ℝ, where ψ is the set of finite simple graphs and ℝ is a set of real numbers which satisfy the relation TG=TH if G is isomorphic to H. Recently published work [6, 7] motivated us to further investigate the Zagreb indices and coindices of strong double graphs.The first Zagreb indexM1G and second Zagreb index M2G were introduced by Gutman and Trinajstić in 1972 [8] and elaborated by Nikolić et al. after 30 years in 2003 [9]. M1G and M2G are defined as(1)M1G=∑uv∈EGℜGu+ℜGv,M2G=∑uv∈EGℜGuℜGv.The first Zagreb index is also written as∑v∈VGℜGv2.Recently, some useful versions of Zagreb indices have been discovered, such as multiplicative Zagreb indices [3, 7, 10], multiplicative sum Zagreb indices [11, 12], Zagreb coindices [6], and multiplicative Zagreb coindices [13].The important variants of the Zagreb index are the first and second Zagreb coindices, which are defined as follows, respectively:(2)M¯1G=∑u≠v;uv∉EGℜGu+ℜGv,M¯2G=∑u≠v;uv∉EGℜGuℜGv.Doslic [14] introduced M¯1G and M¯2G in 2008. In 2009, Ashrafi et al. [15] determined the extremal values of these new invariants for some special graphs. They [6] also explored their fundamental properties and provided some explicit formulas for these versions under different graph operations.


## 2. Main Results

In this section, we study Zagreb indices and Zagreb coindices of strong double graphs. We also study these indices for generalizedk-iterated strong double graphs. We use the concept of edge partition to reduce computation complexity and obtain computing formulas for these indices.For the sake of simplicity, we considerSDG=G1∗=G∗ and Gk∗=Gk−1∗∗ for k≥2. Assume that G0∗=G for the sake of consistency.In the following theorem, we study the first and second Zagreb indices of the strong double graph.Theorem 1.
LetG be a simple connected graph of order n and size m; then,(i)
M1G∗=8M1G+16m+2n(ii)
M2G∗=16M2G+12M1G+12m+nProof.
For the sake of convenience, we label all vertices inG as v1,v2,…,vn. Suppose that xi and yi are the corresponding clone vertices, in strong double graph G∗, of vi for each i=1,…,n.
For any given vertexvi in G and its clone vertices xi and yi, there exists dG∗xi=dG∗yi=2ℜGvi+1 by the definition of the strong double graph.
Forvi,vj∈VG, if vivj∈EG, then xixj∈EG∗, yiyj∈EG∗, xiyj∈EG∗, and yixj∈EG∗.
So, we only need to consider the total contribution of the following three types of adjacent vertex pairs both toM1G∗ and to M2G∗.Type 1: the adjacent vertex pairsxi,xj and yi,yj, where vivj∈EGType 2: the adjacent vertex pairsxi,yi for each i=1,…,nType 3: the adjacent vertex pairsxi,yj and yi,xj, where vivj∈EG
The total contribution of adjacent vertex pairs of type 1 inM1G∗ is given by(3)∑xixj∈EG∗dG∗xi+dG∗xj=∑yiyj∈EG∗dG∗yi+dG∗yj=∑vivj∈EG2ℜGvi+1+2ℜGvj+1=2∑vivj∈EGℜGvi+ℜGvj+2EGvivj∈EG=2M1+2m,and M2G∗ is given by(4)∑xixj∈EG∗dG∗xi⋅dG∗xj=∑yiyj∈EG∗dG∗yi⋅dG∗yj=∑vivj∈EG2ℜGvi+1⋅2ℜGvj+1=4∑vivj∈EGℜGvi⋅ℜGvj+2∑vivj∈EGℜGvi+ℜGvj+EGvivj∈EG=4M2+2M1+m.
The total contribution of adjacent vertex pairs of type 2 inM1G∗ is given by(5)∑xiyi∈EG∗dG∗xi+dG∗yi=∑vi∈VG2ℜGvi+1+2ℜGvi+1=4∑vi∈VGℜGvi+2VGvi∈VG=8m+2n,and M2G∗ is given by(6)∑xiyi∈EG∗dG∗xi+dG∗yi=∑vi∈VG2ℜGvi+1⋅2ℜGvi+1=4∑vi∈VGℜGvi2+4∑vi∈VGℜGvi+VGvi∈VG=4M1G+8m+n.
The total contribution of adjacent vertex pairs of type 3 inM1G∗ is given by(7)∑xiyi∈EG∗dG∗xi+dG∗yi=∑yixj∈EG∗dG∗yi+dG∗xi=∑vivj∈EG2ℜGvi+1+2ℜGvj+1=2∑vivj∈EGℜGvi+ℜGvi+EGvivj∈EG=2M1G+2m,and M2G∗ is given by(8)∑xiyj∈EG∗dG∗xi⋅dG∗yj=∑yixj∈EG∗dG∗yi⋅dG∗xj=∑vivj∈EG2ℜGvi+1⋅2ℜGvj+1=4∑vivj∈EGℜGvi⋅ℜGvj+2∑vivj∈EGℜGvi+ℜGvj+EGvivj∈EG=4M2G+2M1G+m.
Therefore, by using equations (3), (5) and (7), we have(9)M1G∗=∑xixj∈EG∗dG∗xi+dG∗xj+∑yiyj∈EG∗dG∗yi+dG∗yi+∑xiyi∈EG∗dG∗xi+dG∗yi+∑xiyj∈EG∗dG∗xi+dG∗yi+∑yixj∈EG∗dG∗yi+dG∗xj=2M1G+2m+2M1G+2m+8m+2n+2M1G+2m+2M1G+2m=8M1G+16m+2n.
By using (4), (6) and (8), we also have(10)M2G∗=∑xixj∈EG∗dG∗xi⋅dG∗xj+∑yiyj∈EG∗dG∗yi⋅dG∗yi+∑xiyi∈EG∗dG∗xi⋅dG∗yi+∑xiyj∈EG∗dG∗xi⋅dG∗yi+∑yixj∈EG∗dG∗yi⋅dG∗xj=4M2G+2M1G+m+4M2G+2M1G+m+4M1G+8m+n+4M2G+2M1G+m+4M2G+2M1G+m=16M2G+12M1G+12m+n.
In this theorem, we study the first and second Zagreb coindices of the strong double graph.Theorem 2.
LetG be a simple connected graph of order n and size m; then,(i)
M¯1G∗=8M¯1G+4n2−4n−8m(ii)
M¯2G∗=16M¯2G+8M¯1G+2n2−2n−4mProof.
For the sake of convenience, we label all vertices inG as v1,v2,…,vn. Suppose that xi and yi are the corresponding clone vertices, in strong double graph G∗, of vi for each i=1,…,n.
For any given vertexvi in G and its clone vertices xi and yi, there exists dG∗xi=dG∗yi=2ℜGvi+1 by the definition of the strong double graph.
Forvi,vj∈VG, if vivj∉EG, then xixj∉EG, yiyj∉EG, xiyj∉EG, and yixj∉EG.
So, we only need to consider the total contribution of the following two types of nonadjacent vertex pairs both toM¯1G∗ and to M¯2G∗.Type 1: the nonadjacent vertex pairsxi,xj and yi,yj, where vivj∉EGType 2: the nonadjacent vertex pairsxi,yj and yi,xj, where vivj∉EG
The total contribution of nonadjacent vertex pairs of type 1 inM¯1G∗ is given by(11)∑xixj∉EG∗dG∗xi+dG∗xj=∑yiyj∉EG∗dG∗yi+dG∗yj=∑vivj∉EG2ℜGvi+1+2ℜGvj+1=2∑vivj∉EGℜGvi+ℜGvj+2EG¯=2M1G−2m+n2−n,and M¯2G∗ is given by(12)∑xixj∉EG∗dG∗xi⋅dG∗xj=∑yiyj∉EG∗dG∗yi⋅dG∗yj=∑vivj∉EG2ℜGvi+1⋅2ℜGvj+1=4∑vivj∉EGℜGvi⋅ℜGvj+2∑vivj∉EGℜGvi+ℜGvj+EG¯=4M2G+2M1G+12n2−n−2m.
The total contribution of nonadjacent vertex pairs of type 2 inM¯1G∗ is given by(13)∑xiyj∉EG∗dG∗xi+dG∗yj=∑yixj∉EG∗dG∗yi+dG∗xj=∑vivj∉EG2ℜGvi+1+2ℜGvj+1=2∑vivj∉EGℜGvi+ℜGvj+2EG¯=2M1G−2m+n2−n,and M¯2G∗ is given by(14)∑xi,yj∉G∗dG∗xi⋅dG∗yj=∑yi,xj∉EG∗dG∗xi+dG∗yj=∑vi,vj∉EG2ℜGvi+1⋅2ℜGvj+1=4∑vi,vj∉EGℜGvi⋅ℜGvj+2∑vi,vj∉EGℜGvi+ℜGvj+EG¯=4M2G+2M1G+12n2−n−2m.
Therefore, by using equations (11) and (13), we have(15)M¯1G∗=∑xi,xj∉EG∗dG∗xi+dG∗xj=∑yi,yj∉EG∗dG∗yi+dG∗yj+∑xiyj∉EG∗dG∗xi+dG∗yj+∑yixj∉EG∗dG∗yi+dG∗xj=2M1G−2m+n2−n+2M1G−2m+n2−n+2M1G−2m+n2−n+2M1G−2m+n2−n=8M1G−8m+4n2−4n.
By using equations (12) and (14), we also have(16)M¯2G∗=∑xi,xj∉EG∗dG∗xi⋅dG∗xj=∑yi,yj∉EG∗dG∗yi⋅dG∗yj+∑xi,yj∉EG∗dG∗xi⋅dG∗yj+∑yi,xj∉EG∗dG∗yi⋅dG∗xj=4M2G+2M1G+12n2−n−2m+4M2G+2M1G+12n2−n−2m+4M2G+2M1G+12n2−n−2m+4M2G+2M1G+12n2−n−2m=16M2G+8M1G+2n2−n−2m.
Now, we present the first and second indices and coindices ofk-iterated strong double graphs.Theorem 3.
LetG be a nontrivial graph of order n and size m, and let Gk∗ be its k- iterated strong double graph. Then,(i)
M1G∗k=8kM1G+22k+12k−1m+2k2k−12n(ii)
M2G∗k=3⋅23k−1⋅2k−1M1G+42kM2G+3⋅22k⋅2k−12m+2k−12k−13n(iii)
M¯1G∗k=8kM¯1G+2k−14kn2−n−2m(iv)
M¯2G∗k=24kM¯2G+23k⋅2k−1M¯1G+22k−1⋅2k−12n2−n−2mProof.
For any nontrivial graphG with n vertices and m edges, the number of vertices in G∗ is 2n and the number of edges in G∗ is 2m plus those edges between the sets x1,x2,…,xn and y1,y2,…,yn, that is, 4km+n.
Now, we deduce thatGk∗ has 2km vertices and 4km+22k−1−2k−1n edges.(i)
M1Gk∗=8kM1G+22k+12k−1m+2k2k−12n.As we know,(17)M1G∗=8M1G+16m+2n.Using the size of strong double graphm=4km+22k−1−2k−1n, we have(18)M1G∗=8M1G+164km+22k−1−2k−1n+2n,M1Gk∗=8M1Gk−1∗+4⋅22km+22k−1−2k−1+2n.By Theorem1 and the definition of the k-iterated strong double graph, for k≥1, we have(19)M1Gk∗=8M1Gk−1∗+4⋅22km+8⋅22k−2−8⋅2k−1+2knM1Gk∗=88M1Gk−2∗+4⋅22k−2m+8⋅22k−4−8⋅2k−2+2k−1n+4⋅22km+8⋅22k−2−8⋅2k−1+2kn=82M1Gk−2∗+12⋅22km+22k−16⋅22k−15⋅2kn=828M1Gk−3∗+4⋅22k−4m+8⋅22k−6−8⋅2k−3+2k−2n+12⋅22km+22k−16⋅22k−15⋅2kn=83M1Gk−3∗+28⋅22km+14⋅22k−63⋅2knM1G∗k=8kM1G+22k+12k−1m+2k2k−12n.(ii)
M2G∗k=3⋅23k−1⋅2k−1M1G+42kM2G+3⋅22k⋅2k−12m+2k−12k−13n.As we know,(20)M2G∗=16M2G+12M1G+12m+n.UsingM1G∗=8M1G+4⋅22km+22k−1−2k−1+2n and the number of edges of strong double graph m=4km+22k−1−2k−1n, we have(21)M2G∗=16M2G+128M1G+4⋅22km+22k−1−2k−1+2n+124km+22k−1−2k−1n+n,M2G∗=16M2G+96M1G+192+12⋅22km+6⋅22k−6⋅2k+25n.By Theorem1 and the definition of the k-iterated strong double graph, for k≥1, we have(22)M2G∗=16M2Gk−1∗+12⋅23k−1M1G+6⋅23k−1+6⋅25k−1m+6⋅4k−1−6⋅2k−1+52k−1n=1616M2Gk−2∗+12⋅23k−2M1G+6⋅23k−2+6⋅25k−2m+16⋅6⋅4k−2−6⋅2k−2+52k−2n+12⋅23k−1M1G+6⋅23k−1+6⋅25k−1m+6⋅4k−1−6⋅2k−1+52k−1n=162M2Gk−1∗+9⋅23k2M1G+9⋅23k4+9⋅25k32m+15⋅22k2−41⋅52k625+27⋅2k+1n,M2Gk∗=16216M2Gk−3∗+12⋅23k−3M1G+6⋅23k−3+6⋅25k−3m+162⋅6⋅4k−3−6⋅2k−3+52k−3n+9⋅23k2M1G+9⋅23k4+9⋅25k32m+15⋅22k2−41⋅52k625+27⋅2k+1n,M2G∗=163M2Gk−3∗+21⋅23k2M1G+21⋅23k4+21⋅25k64m+63⋅22k2+1281⋅52k15625+219⋅2k+1n,⋮M2G∗k=3⋅23k−1⋅2k−1M1G+42kM2G+3⋅22k⋅2k−12m+2k−12k−13n.(iii)
M¯1G∗k=8kM¯1G+2k−14kn2−n−2m.(23)M1G∗=8M¯1G∗−8m+4n2+4n.By Theorem1 and the definition of the k-iterated strong double graph, for k≥1, we have(24)M1Gk∗=8M¯1Gk−1∗−22k+1m+22kn2+22knM1Gk∗=88M¯1Gk−2∗−22k−1+1m+22k−1n2+22k−1n−22k+1m+22kn2+22kn=82M1Gk−2∗−6⋅22km+3⋅22kn2+3⋅22kn=828M¯1Gk−3∗−22k−2+1m+22k−2n2+22k−2n−6⋅22km+3⋅22kn2+3⋅22kn=83M¯1Gk−3∗−14⋅22km+7⋅22kn2+7⋅22kn⋮M1Gk∗=8kM¯1G+2k−14kn2−n−2m.(iv)
M¯2G∗k=24kM¯2G+23k⋅2k−1M¯1G+22k−1⋅2k−12n2−n−2m.(25)M¯2G∗=16M¯2G+8M¯1G+2n2−n−2m.
By Theorem1 and the definition of the k-iterated strong double graph, for k≥1, we have(26)M¯2Gk∗=16M¯2Gk−1∗+8M¯1Gk−1∗+2n2−n−2m,and using M¯1G∗=8M¯1G−8m+4n2+4n, we have(27)M¯2Gk∗=16M¯2Gk−1∗+88M¯1G−8m+4n2+4n+2n2−n−2m=16M¯2Gk−1∗+64M¯1G+32n2−n−2m+2n2−n−2m.
By rearranging the terms, we have(28)M¯2Gk∗=16M¯2Gk−1∗+8⋅8k−1M¯1G+32k−1n2−n−2m+23k−3n2−n−2m=1616M¯2Gk−2∗+8⋅8k−2M¯1G+32k−2n2−n−2m+16⋅23k−6n2−n−2m+8⋅8k−1M¯1G+32k−1n2−n−2m+23k−3n2−n−2m=162M¯2Gk−2∗+3⋅23kM¯1G+3⋅25k64n2−n−2m+3⋅23k8n2−n−2m=16216M¯2Gk−3∗+8⋅8k−3M¯1G+32k−3n2−n−2m+162⋅23k−9n2−n−2m+3⋅23kM¯1G+3⋅25k64n2−n−2m+3⋅23k8n2−n−2m=163M¯2Gk−3∗+7⋅23kM¯1G+7⋅25k128n2−n−2m+7⋅23k8n2−n−2m⋮M¯2Gk∗=24kM¯2G+23k⋅2k−1M¯1G+22k−1⋅2k−12n2−n−2m.
Here, we present an algorithm to generate and verify the first and second Zagreb indices and coindices of any finite simple connected graphG. This algorithm is based on the adjacency matrix of G (Algorithm 1).Algorithm 1: Computing the first Zagreb index IM1, second Zagreb index IM2, first Zagreb coindex CM1, and second Zagreb coindex CM2.
Input:Ais an adjacency matrix of a finite simple connected graphOutput:IM1,IM2,CM1,CM2Variables used:nr  = number of rows inA,nc  = number of columns inA,(1)
IM1:=0, IM2:=0, CM1:=0, CM2:=0(2)
fori=1tonr(3)
forj=itonc(4)
si:=sum ofith row ofA,(5)
sj:=sum ofjth column ofA.(6)
ifAi,j=1(7)
IM1:=IM1+Si+Sj(8)
IM2:=IM2+Si∗Sj(9)
end if(10)
ifAi,j=0andi≠j(11)
CM1:=CM1+Si+Sj(12)
CM2:=CM2+Si∗Sj(13)
end if(14)
end for j(15)
end for iExample 1.
LetA, B, and C be the matrices of path graph P4 and strong double graphs SD1∗P4 and SD2∗P4, respectively. These matrices are square and symmetric, and choose value 1 (one) at the ith row and jth column if vi and vj are adjacent vertices in a graph; otherwise, it is 0. The suggested algorithm is applied on these matrices to compute the first Zagreb index IM1, second Zagreb index IM2, first Zagreb coindex CM1, and second Zagreb coindex CM2. These adjacency matrices have been obtained by drawing the respective graphs in “GraphTea” software; this software is easily available, and it is free of cost.(29)A=0100101001010010,B=0100110010101110010101110010001111000100111010100111010100110010,C=0100110011001000101011101110000001010111011100000010001100110000110001001000110011101010000011100111010100000111001100100000001111001000010011001110000010101110011100000101011100110000001000111000110011000100000011101110101000000111011101010000001100110010.
The result of the algorithm is given as follows:(30)GraphMatrixAM1AM2CM1CM2P4A10885SD1∗P4B13628888156SD2∗P4C75626528642802.
Now, we provide graphs of Zagreb indices and coindices. Such type of graphical representation will be more helpful to study the dynamics of topological descriptors of the molecular graphs. Here, we present the strong double graph of the path graph,SDPn, where 2≤n≤21 and m=n−1. In Figure 3, the behaviour of the first Zagreb index M1 and second Zagreb index M2 is linear as the straight plane, and the behaviour of the first Zagreb coindex CM1 and second Zagreb coindex CM2 is nonlinear as the curved form. In Figure 4, we have drawn the curves of these indices and coindices for SDPn to understand their dynamics. This figure shows the relation between Zagreb indices and coindices as M1≤M2≤CM1≤CM2.Figure 3
3D surface plot of Zagreb indices and coindices ofSDPn.
(a)(b)(c)(d)Figure 4
3D curve plot of Zagreb indices and coindices ofSDPn.


## 3. Conclusion

We have presented generalized explicit formulas to calculate the first Zagreb indexM1G, second Zagreb index M2G, first Zagreb coindex M¯1G, and second Zagreb coindex M¯2G of the strong double graph SDG and k-iterated strong double graph SDk∗G. The relation between these indices and coindices is also presented as M1≤M2≤CM1≤CM2. We have also presented an algorithm with a given adjacency matrix to verify these indices and coindices by programming and numerically. Computer-generated graphs are also given to understand the dynamics of these indices and coindices.This family of graphs can be considered for other degree-based and distance-related topological indices for further studies.



---

*Source: 4852459-2021-08-02.xml*