# Some New Bounds of Weighted Graph Entropies with GA and Gaurava Indices Edge Weights

Authors: Tiejun Wu; Hafiz Mutee Ur Rehman; Yu-Ming Chu; Deeba Afzal; Jianfeng Yu
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Motivated by the concept of Shannon’s entropy, the degree-dependent weighted graph entropy was defined which is now become a tool for measurement of structural information of complex graph networks. The aim of this paper is to study weighted graph entropy. We usedGA and Gaurava indices as edge weights to define weighted graph entropy and establish some bounds for different families of graphs. Moreover, we compute the defined weighted entropies for molecular graphs of some dendrimer structures.


---

## Body

## 1. Introduction

The branch of mathematics known as graph theory provides tools for solving problems of information theory, computer sciences, physics, and chemistry [1–3]. Among them, special places are reserved for so-called topological descriptors, which play an important role in mathematical chemistry, especially in QSPR/QSAR surveys. Many topological descriptors are introduced and studied in the literature, such as the Zagreb index [4–6], the Randić connectivity index [7], and the modified Zagreb index [8, 9].In the year 2009, Vukičević and Furtula [10] introduced the geometrical arithmetic (GA) index as a molecular descriptor, and mathematical formula for this index is,(1)GA1=∑uv∈EG2dudvdu+dv.There are many interesting attributes on topological indices, and different physicochemical properties of hydrocarbons can be obtained from this index [11–16]. The predictive power of the GA index is compared with others such as the famous Randić index [17]. Due to this reason, different versions of the GA index are now investigated and introduced in the literature [18–20]. The other famous indices are given in [21]. The mathematical formulae for first and second Gaurava indices are(2)GO1=∑uv∈EGdu+dv+du⋅dv,(3)GO2=∑uv∈EGdu+dv⋅du⋅dv,respectively.Many problems of information theory, biology, computer sciences, chemistry, and discrete mathematics are directly solved by utilizing different kinds of graph measures and the graph entropy is one of the powerful tools [22–26] that help to understand the structural complexity of graph networks [27]. Different molecular descriptors are used to introduce weighted graph entropies [28–31].In this paper, we extended the work of [28, 30] and introduced weighted graph entropies by using GA and Gaurava indices as edge weights. We examine the extreme properties of these entropies for some special graph families. We also computed these entropies for different chemical structures.Now, we define some basic notions about entropy of graphs. We always considerG being a connected graph with E as the set of edges, V as the set of vertices, and w to be the edge weight given to the edges of graph G that will be used to define weighted graph entropy. As mentioned above, GA and Gaurava indices are taken as edge weights in this paper. du denoted the degree of a vertex u that is defined as the total number of vertices of G that are at distance one from the vertex u. Consider(4)pij=wvivj∑j=1diwvivj,where wvivj is the weight vivj and wvivj>0.Now, the weighted graph entropy can be defined by(5)Hvi=−∑pijlogpij.Definition 1.
For the graphG, the weighted entropy can be defined as follows [28, 30]:(6)IG,w=−∑uv∈EGpuvlogpuv.
Here,puv is same as that given in (4).


## 2. Main Results

In this section, we are going to present our main results.Lemma 1.
LetG be a simple graph having n vertices and m edges and let Δ and δ be the maximum degree and minimum degree of a vertex, respectively; then,(7)2νΔΔ+1+μ2−μ4δ12∑1di3−2M2G−νδ1−12−μ241−2Δδ1Δ+12≤GA1≤2νδ1δ1+1+μ2−μ4Δ2∑1di3−2M2G−νΔ−12,with equality if and only if G is a regular graph or G is a bipartite graph.Lemma 2.
ConsiderG is a simple connected graph having m edges. Then, we have(8)GA1≤2νΔΔ+1+1ΔM2G−νΔ+m−νδ12,with equality if and only if G is isomorphic to K1,n−1 or G is isomorphic to regular graph or G is isomorphic to Δ,1 semiregular graph.Lemma 3.
ConsiderG is a simple connected graph having m edges. Then, we have(9)GA1≥2νΔΔ+18Δ+δ1Δδ1δ+Δ2m−ν2m−ν4δ12∑1di3−2M2G−νδ1−12.
Moreover, the equality holds if and only ifG is isomorphic to a regular graph or G is isomorphic to Δ,1 semiregular graph.Lemma 4.
ConsiderG is a simple connected graph having m edges. Then, we have(10)GA1≤2m2n−1n+1−2ν2n−1n+1−n−1n,with equality if and only if G is isomorphic to K1,n−1 or G is isomorphic to a complete graph K3.Lemma 5.
ConsiderG is a simple connected graph having m edges. Then, we have(11)GA1≤m−1n−1+m−1n−12+M2Gn−1.Theorem 1.
ConsiderG is a connected graph having n vertices with n≥3. Then, we have(12)logGA1+log2n≤IG,GA1≤logGA1+logn42;logGO1+log4n−1≤IG,GO1≤logGO1−log3n−12.Proof.
We prove the result forGO1, the other results can be proved in the same manner.
SinceG is a connected graph with n number of vertices, for any vertex, the maximum possible degree can be n − 1 and the minimum possible degree can be one. Hence, for any edge uv, the minimum degrees for u and v can be 1 and 2 and maximum possible degrees for u and v can be n − 1 and n − 1, and hence, we have(13)IG,GO1=logGO1−1GO1∑uv∈EGdu+dv+du⋅dv⋅log∑uv∈EGdu+dv+du⋅dv≤logGO1−log3+logn−12=logGO1−log3n−12≥logGO1−1GO1∑uv∈EGdu+dv+du⋅dv⋅log∑uv∈EGdu+dv+du⋅dv≥logGO1−log2n−2+log2=logGO1+log4n−1.
Therefore,(14)logGO1+log4n−1≤IG,GO1≤logGO1−log3n−12.Theorem 2.
LetG be a graph with n vertices. Let δ and Δ be the minimum and maximum degrees of G, respectively. Then, we have(15)logGA1+logδΔ≤IG,GA1≤logGA1+logΔδlogGO1−log2Δδ2≥IG,ReZ1≥logGO1−log2δΔ2.Proof.
SinceG is the connected graph with n number of vertices, for any vertex, the maximum possible degree can be n − 1 and the minimum possible degree can be one. Hence, for any edge uv, the minimum degrees for u and v can be 1 and 2 and maximum possible degrees for u and v can be n − 1 and n − 1, and hence, we have(16)IG,GO1=logGO1−1GO1∑uv∈EGdu+dv+du⋅dv⋅log∑uv∈EGdu+dv+du⋅dv=logGO1−1GO1∑uv∈EGdu+dv+du⋅dv⋅logdu+dv+logdu⋅dv=logGO1−log2Δδ2.
Also,(17)IG,GO1≥logGO1−log2δΔ2.Theorem 3.
ConsiderG is a regular graph having n vertices with n≽3. Then, we have(18)logn≤IG,GA1≤lognn−12.
Note that left inequality turns into equality ifG is a cyclic graph, and the right inequality turns into equality if G is a complete graph.Theorem 4.
ConsiderG is a complete bipartite graph having n vertices. Then, we have(19)logn−1≤IG,GA1≤logn2n2.
Note that the left inequality turns into equality ifG is a star graph, and logn−1=log⌊n/2⌋⌈n/2⌉ if and only if G is a complete bipartite graph (balanced).Theorem 5.
LetT be a tree of order nn>2 with maximum degree vertex Δ; then, we have(20)logGA1≤log2pΔΔ+1.Theorem 6.
LetG be a simple graph having n vertices and m edges and let Δ and δ be the maximum degree and minimum degree of a vertex, respectively; then,(21)log2mδ⋅Δδ+Δ≤IG,GA1,with equality if and only if G is either a regular graph or a bipartite graph.In graph theory, the molecular graph is obtained by taking atoms as vertices and bounds as edges. It can be noted that the maximum possible degree for a vertex in a molecular graph is four. Following theorem is about the bounds of weighted entropy for the molecular graph.Theorem 7.
Consider a molecular graphG having n vertices. Then, we have(22)logGA1−log4≤IG,GA1≤logGA1+log2.


### 2.1. Relation of Entropy with Zagreb Indices

Theorem 8.
ConsiderG is a simple connected graph. Then, we have(23)log2M1Gnn−1≤IG,GA1≤logM1G2.
The equality holds if and only ifG is a union of K2.Theorem 9.
ConsiderG is any graph, then we have(24)IG,GA1≥log2mM2Gn−1.
Equality holds if and only ifG is isomorphic to the regular graph.Theorem 10.
ConsiderG is any graph, then we have(25)log2mM2G+mm−1n−1≤IG,GA1.
Equality holds if and only ifG is isomorphic to the regular graph.Theorem 11.
ConsiderG is any graph, then we have(26)IG,GA1≤log4n−12νΔΔ+1+2n−1ΔM2G−νΔ+m−νδ12.
Equality holds if and only ifG is isomorphic to the regular graph.


### 2.2. Numerical Examples

Here, we compute the weighted entropies introduced in this paper for some chemical structures.Example 1.
Consider the porphyrin dendrimers shown in Figure1. We denote the graph of porphyrin dendrimers by G, and the edge partition of G is given in Table 1. Using Table 1 and definition of entropy, we have the following entropies for porphyrin dendrimers:(27)IG,GA1=logGA1−1GA1∑uv∈EG2dudvdu⋅dv⋅log2dudvdu⋅dv=log98.88020n−10.87877−198.88020n−10.87877E1234⋅log234+E2245⋅log245+E3244⋅log244+E4264⋅log264+E5266⋅log266+E72127⋅log2127=log98.88020n−10.87877−198.88020n−10.878772n234⋅log234+24n245⋅log245+10n−5244⋅log244+48n−6265⋅log265+13n266⋅log266+8n2127⋅log2127,IG,GA1=logGA1−1GA1−23.308n−2.695,Figure 1
Porphyrin dendrimer.Table 1
Edge partition of porphyrin dendrimers.
du,dv(1, 3)(1, 4)(2, 2)(2, 3)(3, 3)(3, 4)Number of edges2n24n10n − 548n − 613n −8n −(28)IG,GO1=logGO1−1GO1∑uv∈EGdu+dv+du⋅dv⋅log∑uv∈EGdu+dv+du⋅dv=log1169n−106−11169n−106E11+3+1.3⋅log1+3+1.3+E21+4+1.4⋅log1+4+1.4+E32+2+2.2⋅log2+2+2.2+E42+3+2.3⋅log2+3+2.3+E53+3+3.3⋅log3+3+3.3+E63+4+3.4⋅log3+4+3.4=log1169n−106−11169n−10614n⋅log7+E21+4+1.4⋅log1+4+1.4+E32+2+2.2⋅log2+2+2.2+E42+3+2.3⋅log2+3+2.3+E53+3+3.3⋅log3+3+3.3+E63+4+3.4⋅log3+4+3.4,IG,GO1=logGA1−1GA1−23.308n−2.695,Example 2.
The graph G of zinc-porphyrin dendrimer is shown in Figure2, and the edge partition for this dendrimer is given in Table 2. We have the following computations for the entropies of zinc-porphyrin dendrimer.Figure 2
Zinc-porphyrin dendrimer.Table 2
Edge partition of zinc-porphyrin dendrimers.
du,dv(2, 2)(2, 3)(3, 3)(3, 4)Number of edges16.2n − 440.2n−168.2n−164(29)IG,GA1=logGA1−1GA1∑uv∈EG2dudvdu⋅dv⋅log2dudvdu⋅dv=log44.9312n−22.226−1244.9312n−22.226E122⋅log22+E222⋅log22+E323⋅log23+E4156⋅log156=log44.9312n−22.226−1244.9312n−22.22616.2n−422⋅log22+40.2n−1622⋅log22+8.2n−1623⋅log234156⋅log156.Example 3.
LetG be the graph of poly(ethylene amidoamine) dendrimers as shown in Figure 3. Then, the edge partition of this dendrimer is given in Table 3 and we have the following results.Figure 3
Poly(ethylene amidoamine) dendrimer.Table 3
Edge partition of the poly(ethylene amidoamine) dendrimer.
du,dv(1, 2)(1, 3)(2, 2)(2, 3)Number of edges4.2n4.2n−216.2n20.2n−9(30)IG,GA1=logGA1−1GA1∑uv∈EG2dudvdu⋅dv⋅log2dudvdu⋅dv=log31.5502n−13.653−1231.5502n−13.653E122⋅log22+E263⋅log63+E322⋅log22+E422⋅log22=log31.5502n−13.653−1231.5502n−13.6534.2n22⋅log22+4.2n−263⋅log63+16.2n22⋅log22+20.2n−922⋅log22.


## 2.1. Relation of Entropy with Zagreb Indices

Theorem 8.
ConsiderG is a simple connected graph. Then, we have(23)log2M1Gnn−1≤IG,GA1≤logM1G2.
The equality holds if and only ifG is a union of K2.Theorem 9.
ConsiderG is any graph, then we have(24)IG,GA1≥log2mM2Gn−1.
Equality holds if and only ifG is isomorphic to the regular graph.Theorem 10.
ConsiderG is any graph, then we have(25)log2mM2G+mm−1n−1≤IG,GA1.
Equality holds if and only ifG is isomorphic to the regular graph.Theorem 11.
ConsiderG is any graph, then we have(26)IG,GA1≤log4n−12νΔΔ+1+2n−1ΔM2G−νΔ+m−νδ12.
Equality holds if and only ifG is isomorphic to the regular graph.


## 2.2. Numerical Examples

Here, we compute the weighted entropies introduced in this paper for some chemical structures.Example 1.
Consider the porphyrin dendrimers shown in Figure1. We denote the graph of porphyrin dendrimers by G, and the edge partition of G is given in Table 1. Using Table 1 and definition of entropy, we have the following entropies for porphyrin dendrimers:(27)IG,GA1=logGA1−1GA1∑uv∈EG2dudvdu⋅dv⋅log2dudvdu⋅dv=log98.88020n−10.87877−198.88020n−10.87877E1234⋅log234+E2245⋅log245+E3244⋅log244+E4264⋅log264+E5266⋅log266+E72127⋅log2127=log98.88020n−10.87877−198.88020n−10.878772n234⋅log234+24n245⋅log245+10n−5244⋅log244+48n−6265⋅log265+13n266⋅log266+8n2127⋅log2127,IG,GA1=logGA1−1GA1−23.308n−2.695,Figure 1
Porphyrin dendrimer.Table 1
Edge partition of porphyrin dendrimers.
du,dv(1, 3)(1, 4)(2, 2)(2, 3)(3, 3)(3, 4)Number of edges2n24n10n − 548n − 613n −8n −(28)IG,GO1=logGO1−1GO1∑uv∈EGdu+dv+du⋅dv⋅log∑uv∈EGdu+dv+du⋅dv=log1169n−106−11169n−106E11+3+1.3⋅log1+3+1.3+E21+4+1.4⋅log1+4+1.4+E32+2+2.2⋅log2+2+2.2+E42+3+2.3⋅log2+3+2.3+E53+3+3.3⋅log3+3+3.3+E63+4+3.4⋅log3+4+3.4=log1169n−106−11169n−10614n⋅log7+E21+4+1.4⋅log1+4+1.4+E32+2+2.2⋅log2+2+2.2+E42+3+2.3⋅log2+3+2.3+E53+3+3.3⋅log3+3+3.3+E63+4+3.4⋅log3+4+3.4,IG,GO1=logGA1−1GA1−23.308n−2.695,Example 2.
The graph G of zinc-porphyrin dendrimer is shown in Figure2, and the edge partition for this dendrimer is given in Table 2. We have the following computations for the entropies of zinc-porphyrin dendrimer.Figure 2
Zinc-porphyrin dendrimer.Table 2
Edge partition of zinc-porphyrin dendrimers.
du,dv(2, 2)(2, 3)(3, 3)(3, 4)Number of edges16.2n − 440.2n−168.2n−164(29)IG,GA1=logGA1−1GA1∑uv∈EG2dudvdu⋅dv⋅log2dudvdu⋅dv=log44.9312n−22.226−1244.9312n−22.226E122⋅log22+E222⋅log22+E323⋅log23+E4156⋅log156=log44.9312n−22.226−1244.9312n−22.22616.2n−422⋅log22+40.2n−1622⋅log22+8.2n−1623⋅log234156⋅log156.Example 3.
LetG be the graph of poly(ethylene amidoamine) dendrimers as shown in Figure 3. Then, the edge partition of this dendrimer is given in Table 3 and we have the following results.Figure 3
Poly(ethylene amidoamine) dendrimer.Table 3
Edge partition of the poly(ethylene amidoamine) dendrimer.
du,dv(1, 2)(1, 3)(2, 2)(2, 3)Number of edges4.2n4.2n−216.2n20.2n−9(30)IG,GA1=logGA1−1GA1∑uv∈EG2dudvdu⋅dv⋅log2dudvdu⋅dv=log31.5502n−13.653−1231.5502n−13.653E122⋅log22+E263⋅log63+E322⋅log22+E422⋅log22=log31.5502n−13.653−1231.5502n−13.6534.2n22⋅log22+4.2n−263⋅log63+16.2n22⋅log22+20.2n−922⋅log22.


## 3. Conclusion

In information theory, the graph entropy is a measure of the information rate achievable by communicating symbols over a channel in which certain pairs of values may be confused. This measure, first introduced by Körner in the 1970s, has since also proven itself useful in other settings, including combinatorics. In this paper, we have studied graph entropy withGA and Gaurava indices and justified it by some numerical examples. It would be interesting to work on entropy of weighted graphs with some other degree- and distance-based topological indices. The bounds of degree-based network entropy can also be used in national security, Internet networks, social networks, structural chemistry, ecological networks, computational systems biology, etc. They will play an important role in analyzing structural symmetry and asymmetry in real networks in the future.



---

*Source: 5474501-2020-09-30.xml*