# The Edge-Weighted Graph Entropy Using Redefined Zagreb Indices

Authors: Jing Lu; Hafiz Mutee-ur-Rehman; Saima Nazeer; Xuemei An
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

Measurements of graphs and retrieving structural information of complex networks using degree-based network entropy have become an informational theoretical concept. This terminology is extended by the concept of Shannon entropy. In this paper, we introduce entropy with graphs having edge weights which are basically redefined Zagreb indices. Some bounds are calculated to idealize the performance in limiting different kinds of graph entropy. In addition, we discuss the structural complexity of connected graphs representing chemical structures. In this article, we have discussed the edge-weighted graph entropy with fixed number of vertices, with minimum and maximum degree of a vertex, regular graphs, complete graphs, complete bipartite graphs, and graphs associated with chemical structures.


---

## Body

## 1. Introduction

In network theory, entropy measure has become an interesting field during last 5 decades due to Shannon [1]. Rashevsky [2] defined partitions of vertex orbits to study structural information. Later on, Mowshowitz [3] used the same concept to prove certain properties for some operations of graphs (see [4]). Graph entropy measurement was used by Rashevsky to study structural complexity of graphs based on Shannon’s entropy. Mowshowitz [3] introduced applications of graph entropy in information technology. The other applicaitons of graph entropy include characterizing graph patterns in chemistry, biology, and computer scineces [5]. In the literature, the graph entropy was defined in different ways. An important example is Körner’s entropy [6] introduced with an information theory-specific point of view.The basic properties of graph entropy were discussed in [7]. The graph entropy satisfies subadditive property in union of graphs which can be extended in graph covering problem and the problem of perfect hashing.Graph entropy used for minimum number of perfect hash functions over a given range of hash for allk-subsets of a set of given size is discussed in [8]. Another application of graph entropy is due to Kahn and Kim [9], who proposed an algorithm based on graph entropy of an appropriate comparability graph. Csiszar et al. [10] in 1990 characterized minimal pairs of convex corners which generate the probability density p=p1,p2,…,pk∈ in a k−dimensional space. Due to this fact, another definition of graph entropy in terms of vertex packing polytope of a graph was introduced. They also gave characterization of a perfect graph using the subadditivity property of graph entropy (see [6]). Their examinations prompted the thought of a class of graphs called normal graphs, a generalization of perfect graphs given in [11]. Alon and Orlitsky [12] examined the connection between the base entropy shading of a graph and the graph entropy. Distinctive graph invariants are utilized to create graph entropy estimates, for example, eigenvalue and network data [13], weighted graph entropy with distance-based TIs as edge weights [14], and weighted graph entropy with degree-based TIs as edge weights [15]. There are various uses of graph entropy in interchanges and financial matters.Different graph invariants such as connectivity information, distance-based topological indices (Wiener related index), degree-based topological indices, the no. of vertices, the vertex degree sequences, the second neighbor degree sequences, the third neighbor degree sequences, eigenvalues, and so on were used to define graph entropy in the literature (see[16]). The properties of graph entropies based on information functionals by using degree powers of graphs have been explored in [17, 18]. The most important graph invariants are the Zagreb index [19] and the zeroth-order Randic index [20]. Chen et al. [21] proposed the idea of graph entropy for unique weighted graphs by utilizing Randić edge weights and demonstrated extremal properties of graph entropy for some basic groups. Kwun et al. [22] established the weighted entropy with atomic bound connectivity edge weights.In this paper, the idea presented in [23] is used to study the weighted graph entropy by using redefined Zagreb indices as edge weights. Some degree-based indices are portrayed by researching the boundaries of the entropy of certain class of graphs [22]. Our aim is also to address the issue proposed by Chen et al. in [21] and Kwun et al. in [24]. The paper is organized into different sections to discuss the proposed problems.


## 2. Topological Index

In chemical structures, various graph notions used are molecular descriptors (or topological index). Few of them are first and second Zagreb indicesM1G and M2G, respectively, exhibiting applicability for deriving multi-linear regression models. Details on the chemical applications of these indices can be seen in [25, 26]. More results on Zagreb indices can be seen in [27, 28]. Applications of Zagreb indices in QSPR were exposed by modeling the structure-boiling point associated with C3−C8 alkanes using the CROMRsel method [29, 30]. A large number of studies have been conducted on these two indices.Ranjini et al. [31] introduced redefined first, second, and third Zagreb indices as(1)RZ1Γ=∑e=xy∈EΓdx+dydx⋅dy,RZ2Γ=∑e=xy∈EΓdx⋅dydx+dy,RZ3Γ=∑e=xy∈EΓdx⋅dydx+dy.


## 3. Entropy

The entropy of a graph is a functional depending both on the graph itself and on a probability distribution on its vertex set. This graph functional originated from the problem of source coding in information theory and was introduced by Körner in 1973.Consider a graphΓ having order q with degree of a vertex x denoted by dx. For any edge xy, the probability density function is defined as(2)pxy=wxy∑y=1dxwxy,where wxy is the weight xy and wxy>0.The weighted graph entropy is defined as(3)Hvx=−∑pxy⋅logpxy.Extending this method, we introducedentropy of the edge-weighted graph. For an edge-weighted graph, Γ=x,E,w, where x,E, and w denote vertex sets, edge sets, and edge weights of Γ, respectively, where the edge weight is positive.LetΓ=x,E,w be an edge-weighted graph, and the entropy of Γ is(4)IΓ,w=−∑xy∈EΓpxy⋅logpxy,where pxy=wxy/∑xy∈EΓwxy.


## 4. Main Results

In this section, we extend the idea of graph entropy as edge-weighted graphs explained in [23] that tackled the issue of weighted synthetic graph entropy. We also addressed the issue proposed by Chen et al. in [21] and Kwun et al. in [24]. Now we present bounds of the weighted entropy for the connected graphs, regular graphs, complete graphs, complete bipartite graph,s and graphs associated with chemical structures. In these results, the edge weights are redefined first, second, and third Zagreb indices.Theorem 1.
LetΓ be a connected graph with q,q≥3 vertices; then, we have(1)
logRZ1−log3/q−12≤IΓ,ReZ1≤logRZ1−logq−1.(2)
logRZ2−log1/q−2≤IΓ,ReZ2≤logRZ2−logq−12/3.(3)
logRZ3−log4q−8≤IΓ,ReZ3≤logRZ3−log3q−12.Proof.
(1) In simple connected graphΓ, of order q, the maximum and minimum degrees for a vertex are q−1 and 1, respectively. Therefore, for any edge xy, the minimum and maximum possible degrees of x and y are 1,2 and q−1,q−1, respectively. Therefore, we have(5)IΓ,RZ1=−∑xy∈EΓpxylogpxy=−∑xy∈EΓwxy∑y=1dxwxy⋅logwxy∑y=1dxwxy=−∑xy∈EΓdx+dy/dx⋅dy−∑xy∈EΓdx+dy/dx⋅dy×logdx+dy/dx⋅dy−∑xy∈EΓdx+dy/dx⋅dy,IΓ,RZ1=−1RZ1−∑xy∈EΓdx+dydx⋅dy⋅logdx+dy/dx⋅dyRZ1=−1RZ1−∑xy∈EΓdx+dydx⋅dy⋅logdx+dydx⋅dy−logRZ1≤logRZ1−1RZ1∑xy∈EΓdx+dydx⋅dy×log2q−2−log2=logRZ1−logq−1.
Also,(6)IΓ,RZ1=−∑xy∈EΓwxy∑y=1dxwxy⋅logwxy∑y=1dxwxy=−∑xy∈EΓdx+dy/dx⋅dy−∑xy∈EΓdx+dy/dx⋅dy×logdx+dy/dx⋅dy−∑xy∈EΓdx+dy/dx⋅dy=−1RZ1−∑xy∈EΓdx+dydx⋅dy⋅logdx+dy/dx⋅dyRZ1=−1RZ1−∑xy∈EΓdx+dydx⋅dy⋅logdx+dydx⋅dy−logRZ1≥logRZ1−1RZ1∑xy∈EΓdx+dydx⋅dy×log3−logq−12=logRZ1−log3q−12.
Hence,(7)logReZ1−log3q−12≤IΓ,ReZ1≤logReZ1−logq−1.
The proofs of (2) and (3) follow the proof of (1).Theorem 2.
LetΓ be a graph having q vertices with minimum and maximum degrees of γ being δ and Δ, respectively. Then, we have(1)
logRZ1−log2δ/Δ2≤IΓ,RZ1≤logRZ1−log2Δ/δ2.(2)
logRZ2−logδ2/2Δ≤IΓ,RZ2≤logRZ2−logΔ2/2δ.(3)
logRZ3−log2Δδ2≤IΓ,RZ3≤logRZ3−log2δΔ2.Proof.
(1) For a connected graph of orderq, the minimum and maximum degrees for a vertex are 1 and q−1, respectively. For any edge xy, the minimum and maximum possible degrees of vertices x and y are 1,2 and q−1,q−1, respectively. Therefore, we have(8)IΓ,RZ1=−1RZ1−∑xy∈EΓdx+dydx⋅dy×logdx+dydx⋅dy−logRZ1≤logRZ1−1RZ1∑xy∈EΓdx+dydx⋅dy×log2Δ−logδ2=logRZ1−log2Δδ2.
Also,(9)IΓ,RZ1=−1RZ1−∑xy∈EΓdx+dydx⋅dy×logdx+dydx⋅dy−logRZ1≥logRZ1−1RZ1∑xy∈EΓdx+dydx⋅dy×log2δ−logΔ2=logAZI−log2δΔ2.
Hence,(10)logAZI−log2δΔ2≤IΓ,AZI≤logReZ1−log2Δδ2.
The proofs of (2) and (3) follow the proof of (1).Theorem 3.
For a regular graphΓ=V,E,w of order q,q≥3, we have(1)
logRZ1≤IΓ,RZ1≤logRZ1q−1/2.(2)
logRZ2≤IΓ,RZ2≤loglog2RZ2/q−1.(3)
logRZ3/16≤IΓ,RZ3≤logRZ3/2q−13.Moreover,logRZ1=IΓ,RZ1 iff Γ is cyclic graph and logAZI−logRZ1q−1/2 iff Γ is complete graph.Proof.
For at regular graph t≥2, as Γ is connected with q≥3,(11)IΓ,RZ1=−1RZ1−∑xy∈EΓdx+dydx⋅dy×logdx+dydx⋅dy−logRZ1≤logRZ1−1RZ1∑xy∈EΓdx+dydx⋅dy×log2q−2−logq−12=logRZ1q−12.
Also(12)IΓ,RZ1=−1RZ1−∑xy∈EΓdx+dydx⋅dy×logdx+dydx⋅dy−logRZ1≥logRZ1−1RZ1∑xy∈EΓdx+dydx⋅dy×log2q−2−logq−12=logRZ1−log4−log4=logRZ1.
Hence,(13)logRZ1≤IΓ,RZ1≤logRZ1q−12.
The proofs of (2) and (3) follow the proof of (1).Theorem 4.
LetΓ=V,E,w be an arbitrary complete graph of order q; then, we have(1)
IΓ,RZ1≤q2/2−logq/2.(2)
IG,RZ2≤q2/2−logq/2.(3)
IG,RZ3≤2q2−log2q.Proof.
For an arbitrary complete graphΓ of order q, we have RZ1≤q2/2; therefore, the result is obvious.Theorem 5.
For an arbitrary complete bipartite graphΓ=V,E,w with q vertices, we have(1)
logRZ1−logq/q−1≤IΓ,RZ1≤logRZ1−log2/q/2.(2)
logRZ2−logq−1/q≤IΓ,RZ2≤logΓ,RZ2−logq/22/2q/2.(3)
logRZ3−logq2−n≤IΓ,RZ3≤logRZ3−log2q/23.
Moreover,logRZ1−logq/q−1=IΓ,RZ1 iff Γ is a star graph, and IΓ,AZI=logRZ1−log2/q/2 iff Γ is complete bipartite graph (balanced).Proof.
(1) Assume thatΓ is a complete bipartite graph with q vertices with two parts having s and t vertices, respectively. Therefore, we have s+t=q, and we have(14)IΓ,RZ1=−1RZ1−∑xy∈EΓdx+dydx⋅dy×logdx+dydx⋅dy−logRZ1≤logRZ1−1RZ1∑xy∈EΓdx+dydx⋅dy×logs+t−logst=logRZ1−logs+tst.
For minimum value, we takes=1 and a=q−1, while for maximum value, s=a=q/2, and hence(15)logRZ1−logqq−1≤IΓ,AZI≤logRZ1−log2q/2.
The proofs of (2) and (3) follow the proof of (1).Chemical graphs are associated with structure of chemical compounds. Therefore, we consider atoms as vertices and chemical bonds as edges of that graph. The following theorem provides bounds for weighted graph entropy of chemical graph by assigningRZ1 as edge weights.Theorem 6.
LetΓ be a graph with q vertices associated with a chemical structure; then, we have(1)
log16RZ1/3≤IΓ,RZ1≤logRZ1/4.(2)
log4RZ2≤IΓ,RZ2≤log3RZ2/16.(3)
logRZ3/16≤IΓ,RZ3≤logRZ3/48.Proof.
(1) For a chemical graphΓ′, for any edge xy, the maximum degrees of x and y are 4 and 4 and minimum possible degrees are 1 and 2. So, we have(16)IG,RZ1=−1RZ1−∑xy∈EΓdx+dydx⋅dy×logdx+dydx⋅dy−logRZ1≤logRZ1−1RZ1∑xy∈EΓdx+dydx⋅dy×log8−log2=logRZ14.
Similarly,(17)IG,RZ1=−1RZ1−∑xy∈EΓdx+dydx⋅dy×logdx+dydx⋅dy−logRZ1≥logRZ1−1RZ1∑xy∈EΓdx+dydx⋅dy×log3−log16=log16RZ13.
Therefore,(18)log16RZ13≤IΓ,RZ1≤logRZ14.
The proofs of (2) and (3) follow the proof of (1).


## 5. Numerical Examples

Example 1.
The molecular graphs of carbon nanotubesVC5C7p,q are depicted in Figure 1. The structure of VC_5C_7 [p,q] nanotubes consists of C_5 loops and C_7 net following the trivalent decoration. It can cover a cylinder or a ring. Two-dimensional lattice of VC5C7p,q is depicted in Figure 1. Now, we focus on calculating the entropy of a given structure.
It can be observed from Figure1 that the edge set of VC5C7p,q has partition given in Table 1.
Therefore, the entropy ofΓ is computed as(19)IΓ,RZ1=logRZ1−1RZ1∑xy∈EΓdx+dydx⋅dy⋅logdx+dydx⋅dy=log24pq+2p−124pq+2pE144⋅log44+E223⋅log23=log24pq+2p−124pq+2p24pq−6p44⋅log⋅44+12p23⋅log23=log24pq+2p+1.408738p24pq+2p.
Also,(20)IΓ,RZ2=logRZ2−1RZ2∑xy∈EΓdx⋅dydx+dy⋅logdx⋅dydx+dy=log24pq+12p−124pq+12pE144⋅log44+E232⋅log32=log24pq+12p−124pq+12p24pq−6p44⋅log44+12p32⋅log32=log24pq+12p−1.408738p24pq+12p.
Moreover,(21)IΓ,RZ3=logRZ3−−1RZ3−∑xy∈EΓdx+dydx⋅dy⋅logdx+dydx⋅dydx+dy=log384pq−552p−1384pq−552pE116⋅log16+E254⋅log54=log384pq−552p−1384pq−552p24pq−6p16⋅log16+12p54⋅log54=log384pq−552p−462.3820pq−115.5955p384pq−552p.Figure 1
VC5C7p,q.Table 1
Edge partition based on end vertices’ degree ofVC5C7p,q.
da,db(2, 2)(3, 3)Number of edges24pq−6p12pExample 2.
The molecular graphs of carbon nanotubesVC5C7p,q and HC5C7p,q are shown in Figures 2 and 3, respectively. The structure of these nanotubes consistes of C_5 loops and C_7 net following the trivalent decoration. It can cover a cylinder or a ring. Two-dimensional lattice of VC5C7p,q is depicted in Figure 2 and that of HC5C7p,q is depicted in Figure 3. Now, we focus on calculating the entropy of a given structure. From Figure 2, it can be observed that the edge set of VC5C7p,q has the following partitions.
It can be observed from Figure3 that the edge set of HC5C7p,q can be divided into following three classes as given in Table 2.
Furthermore,(22)IΓ,RZ1=logRZ1−1RZ1∑xy∈EΓdx+dydx⋅dy⋅logdx+dydx⋅dy=log20pq+3p−120pq+3pE144⋅log44+E223⋅log32+E356⋅log56=log20pq+3p−120pq+3pp44⋅log44+8p23⋅log32+24pq−4p56⋅log56=log20pq+3p+120pq+3p,IΓ,RZ2=logRZ2−1RZ2∑xy∈EΓdx⋅dydx+dy⋅logdx⋅dydx+dy=log144pq5+41p5−1144pq/5+41p/5E144⋅log44+E232+E365=log144pq5+41p5−1144pq/5+41p/5p44⋅log44+8p32⋅log44+24pq−4p56⋅log56=log24pq+12p−1.408738p24pq+12p.(23)IΓ,RZ3=logRZ3−−1RZ3−∑xy∈EΓdx+dydx⋅dy⋅logdx+dydx⋅dy=log720pq−80p−1720pq−80pE116⋅log16+E26⋅log6+E330⋅log30=log720pq−80p−1720pq−80pp16⋅log16+8p6⋅log6⋅+24pq−4p30⋅log30=log720pq−80p−1720pq−80p.Figure 2
HC5C7p,q.Figure 3
Naphtalenic nanotubes.Table 2
Edge partition based on end vertices’ degree ofHC5C7p,q.
da,db(2, 2)(3, 3)(2, 3)Number of edgesp8p24pq−4pExample 3.
In nanosciences,SC5C7p,q (where p and q represent number of heptagons and number of cycles in each row separately in the entire lattice) nanotubes are a class C5C7, and this is generated by alternating C5 and C7. The standard tiling of C5 and C7 can cover cylinders or rings, and each covers SC5C7p,q. Nanotubes NPHXp,q (where p and q are expressed as the number of hexagon pairs in the first row and the other hexagons in the column) are trivalent modifications in the order of C6,C6,C4,C6,C6,C4,…The first row of the sequence is C6,C8,C6,C8,… in the other rows. In other words, the nanolattice can be viewed as a tile of C4,C6,andC8. Therefore, such tiles can cover cylinders or rings.(24)IΓ,RZ1=logRZ1−1RZ1∑ij∈EΓdx+dydx⋅dy⋅logdx+dydx⋅dy=log8pq−18pqE144⋅log44+E232⋅log32+E356⋅log55=log8pq−18pqp44⋅log44+12pq−9p32⋅log32+6p56⋅log55,IΓ,RZ2=logRZ2−1RZ2∑xy∈EΓdx⋅dydx+dy⋅logdx⋅dydx+dy=log18pq−15p2−118pq−15p/2E144⋅log44+E223⋅log23+E365⋅log65=log18pq−15p2−118pq−15p/2p44⋅log44+12pq−9p23⋅log23+6p65⋅log65,IΓ,RZ3=logRZ3−−1RZ3−∑xy∈EΓdx+dydx⋅dy⋅logdx+dydx⋅dy=log72pq−127p−172pq−127p16E1⋅log16+6E2⋅log6+30E3⋅log30=log720pq−80p−1720pq−80p16p⋅log16+612pq−9p⋅log6+6p30⋅log30=log72pq−127p−172pq−127p.


## 6. Conclusions

In study of information theory, the graph entropy measures the information rate achievable by communicating symbols over a channel in which certain pairs of values may be confused [32–36]. This measure introduced by Körner in the 1970s has proven itself useful in other settings, including combinatorics. In the present paper, we studied weighted graph entropy by using first, second, and third redefined Zagreb indices as edge weights. We also presented numerical examples to justify our results. Interesting work would be to study weighted graph entropy with other degree and distance-based topological indices. The bounds achieved for degree-based network weighted graph entropy can be used for national security, social networks, Internet networks, structural chemistry, computational systems biology, and so on. These studies will play an important role in asymmetry in real networks and analyzing structural symmetry in future.



---

*Source: 5958913-2022-03-28.xml*