Printer Friendly

The Entropy of Weighted Graphs with Atomic Bond Connectivity Edge Weights.

1. Introduction

Mathematical chemistry is the branch of theoretical chemistry in which we discuss and predict the behavior of mathematical structure by using mathematical tools [1, 2]. In the past few decades, there have been many studies in this area. This theory has played an important role in the field of chemistry.

The topological index is a real number associated with the molecular graph. It is a graph invariant. Many topological indices are defined up till now [3-5]. Some of them are based on distance, while others are based on degree and have found many applications in pharmacy, theoretical chemistry, and especially QSPR/QSAR research.

In 1975, the first degree-based topological index [6] was proposed. Later, this index was generalized to any real number a by Estrada et al. in [7] and was named the generalized Randic index. Another well-known topological index based on the vertex degree of the graph is the atomic bond connectivity index [8], which is defined as

ABC(G)= [summation over (uv [member of] E(G))] [square root of ([[d.sub.u] + [d.sub.u] -2]/[[d.sub.u] x [d.sub.u]])] (1)

At the beginning, a close link between the heat of alkane formation and the ABC index was experienced. After that, the ABC index became a powerful tool for simulating the thermodynamic properties of organic compounds. The fourth member of the ABC index category was proposed by M. Ghorbani et al. in [9]. In recent years, many papers are written on topological indices and its application; here we mention few [10-15].

Based on the groundbreaking work of Shannon [16], in the late 1950s began to study the entropy measurement of network systems. Rashevsky uses the concept of graph entropy to measure the structural complexity of the graph. Here, the complexity of his graph is based on Shannon's entropy. Mowshowitz [17] introduced the entropy of the graph as information theory, which he interpreted as the structural information content of the graph. Mowshowitz [18] later studied the mathematical properties of graph entropy and conducted indepth measurements of his particular application. Graph entropy measures have been used in various disciplines, for example, to characterize patterns in biology, chemistry, and computer science. Therefore, it is not surprising to realize that "graph entropy" has been defined in various ways. Another classic example is the introduction of Korners entropy [19].

Different graph invariances have been used to develop image entropy measures such as eigenvalue and connectivity information [20], distance-based graph entropy [21], and degree-based graph entropy [22].

We have different applications of graph entropy in communications and economics. We use the concept of graph entropy as a weighted graph, just as Dehmer [20] who solved the problem of weighted chemical graph entropy by using a special information functional. Some degree-based indices are characterized by investigating the extremes of the entropy of certain class of graphs [23, 24].

In [25], Chen et al. introduced the concept of graph entropy for special weighted graphs by using Randic edge weights and proved extremal properties of graph entropy for some elementary families of graphs. Our aim is to solve problem suggested by Chen et al. in [25]. In this paper, we study graph entropy by taking Atomic bond connectivity edge weights and prove some extermal properties of graph entropy for special families of graphs such as connected graphs, regular graphs, complete bipartite graphs, chemical graphs, tree, unicyclic graphs, and star graphs. Moreover we compute graph entropy of different dendrimer structures.

2. Main Results

Let us have a graph, where G and [v.sub.i] are its vertices and the degree of [v.sub.i] is denoted by [d.sub.i]. For an edge [v.sub.i][v.sub.j] we have

[mathematical expression not reproducible] (2)

where w([v.sub.i] [v.sub.j]) is the weight [v.sub.i][v.sub.j] and w([v.sub.i] [v.sub.j]) > 0. The weighted entropy is defined as

H([v.sub.i]) = [[d.sub.i].summation over (j=1)] [p.sub.ij] log ([p.sub.ij). (3)

Inspired by this method, we have introduced the definition of the entropy of the edge-weighted graph, which can also be interpreted as multiple graphs. For edge weight graphs, G = (V, E, w), where V, E, and w denote the vertex sets of G, edge sets, and edge weights (sometimes also called costs). In this article, we always assume that the edge weights are positive.

Definition 1. Let G = (V, E, w) be an edge weighted, then the entropy of G is

I(G,w) = [summation over uv [member of] E] [p.sub.uv] log ([p.sub.uv]). (4)

where [p.sub.uv] = w(uv)/[[summation].sub.uv [member of] E] w(uv)

Theorem 2. For a connected graph G with n vertices for n [greater than or equal to] 3, we have

log (ABC) + log [square root of (1/[n - 2])] [less than or equal to] I(G, ABC) [less than or equal to] log (ABC)- log [1/[n - 1]] (5)

Proof. For a simple connected graph of order n, the maximum degree for a vertex is n-1 and minimum degree is 1. With any edge uv, the minimum possible degrees of u and v are 1 and 2, respectively, and maximum possible degrees of u and v are n-1 and n-1, so we have

[mathematical expression not reproducible]. (6)

Corollary 3. Let Gbea graph with n vertices. Let [delta] and [DELTA] be the minimum degree and maximum degree of G, respectively. Then we have

log (ABC) + log ([square root of [delta]/[2[DELTA] - 2])]) [less than or equal to] I(G, ABC) [less than or equal to] log (ABC) - 1/2 log ([DELTA]/[square root of (2[delta] -2)] (7)

Proof.

[mathematical expression not reproducible] (8)

Also

I (G, ABC) [greater than or equal to] log (ABC) - 1/2 [log (2[DELTA] - 2) - log ([[delta].sup.2])] = log (ABC) + log ([square root of ([delta]/[2[DELTA] - 2])]. (9)

Theorem 4. For a regular graph G = (V, E, w) with n vertices such that n [greater than or equal to] 3, we have

log (n) [less than or equal to] I(G,ABC) [less than or equal to] log (n(n - 1)/2), (10)

and log(n) = I(G,ABC) if and only if G is cycle graph, and I(G, ABC) = log(n(n- 1)/2) if and only if G is complete graph.

Proof. Let a k regular graph G with k [greater than or equal to] 2. As G is connected with n [greater than or equal to]3, so

[mathematical expression not reproducible]. (11)

Since 2 [less than or equal to] k [less than or equal to] n - 1, we have

log(n) [less than or equal to] I(G,ABC) [less than or equal to] log (n(n - 1)/2) (12)

Theorem 5. For a complete bipartite graph G = (V, E, w) with n vertices, we have

[mathematical expression not reproducible], (13)

and log(n - 1) = I(G,ABC) if and only if G is star graph, and [mathematical expression not reproducible] if and only if G is complete bipartite graph (balanced).

Proof. For a complete bipartite graph G = (V, E, w) with n vertices and two parts have p and q vertices, respectively. Therefore p + q = n. We have

[mathematical expression not reproducible] (14)

Thus

[mathematical expression not reproducible] (15)

Moreover log(n - 1) = I(G,ABC) if and only if p =1 and q = n- 1. i.e., G is a star. Also [mathematical expression not reproducible] if and only if [mathematical expression not reproducible]; i.e., G is a complete bipartite graph (balanced).

Chemical graph is a graph associated with the chemical compound in which atoms are taken as vertices and chemical bonds are taken as edges. In the following theorem, we give bounds for the weighted entropy of chemical graphs by taking ABC edge weights.

Theorem 6. Let G be a chemical graph with n vertices; then we have

log (ABC)- log [square root of 1/16] [less than or equal to] I(G,ABC) [less than or equal to] log (ABC) - log [square root of 3] (16)

Proof. In a chemical graph G the maximum degree of a vertex is 4 and the minimum degree of a vertex is 1, so we have

[mathematical expression not reproducible] (17)

Similarly,

I(G,ABC) [greater than or equal to] log (ABC)- log [square root of (1/16)] (18)

Therefore,

log (ABC)- log [square root of (1/16)] [less than or equal to] I(G, ABC) [less than or equal to] log (ABC) - log [square root of 3] (19)

Corollary 7. Let G = (V, E, w) be any complete graph of order n. Then we have

I(G, ABC) [less than or equal to] n [square root of ([n - 2]/2)] -log ([square root of (n/[n - 1])]. (20)

Proof. For any complete graph G of order n we have [14], ABC(G) [less than or equal to] n[square root of (n - 2)/2)]; therefore the result

I(G,ABC) [less than or equal to] n[square root of ([n - 2]/2)] - log ([square root of (n/[n - 1])]) (21)

Corollary 8. Let G = (V, E, w) be any tree of order n. Then we have

I(G,ABC) [less than or equal to] [square root of ((n-1)(n-2))] - log ([square root of (n/[n - 1])]). (22)

Corollary 9. For a unicyclic graph

I(G, ABC) [less than or equal to] [square root of (n(2[n.sup.2] - 7n - 19)/2(n - 1))] - log ([square root of (n/[n - 1])]. (23)

Corollary 10. For a Star graph,

I(G, ABC) [less than or equal to] [square root of (n(2[n.sup.2] - 7n - 19)/2(n - 1))] - log ([square root of (n/[n - 1])]. (24)

3. Numerical Examples

Dendrimers are man-made, nanoscale compounds with unique properties that make them useful to the health and pharmaceutical industry as both enhancements to existing products and as entirely new products. Dendrimers are constructed by the successive addition of layers of branching groups. The final generation incorporates the surface molecules that give the dendrimers the desired function for pharmaceutical, life science, chemical, electronic, and materials applications. Dendrimers fall under the broad heading of nanotechnology, which covers the manipulation of matter in the size range of 1-100 nanometers (one million nanometers equal one millimeter) to create compounds, structures, and devices with a novel, predetermined properties.

In this section, we discuss entropies of four familiar classes of dendrimers, namely, Porphyrin (Figure 1), Propyl ether imine (Figure 2), Zinc-Porphyrin (Figure 3), and Poly(EThyleneAmidoAmine) (Figure 4) Dendrimers. It is important to remark that all dendrimers differ in cores. These dendrimers have been studied extensively in [25-28].

Example 1. Let G be the Porphyrin dendrimers; then using the edge partition given of Porphyrin dendrimers given in Table 1, we get

ABC(G) = 77.26044062n - 7.778174591 (25)

Therefore

[mathematical expression not reproducible] (26)

Example 2. Let G be the propyl ether imine dendrimer. Then using the edge partition of G given in Table 2, we get

[mathematical expression not reproducible] (27)

Example 3. For the Zinc-Porphyrin dendrimers G, using edge partition given in Table 3, we get

[mathematical expression not reproducible] (28)

Example 4. Let G be the graph of Poly(EThyleneAmidoAmine; then using edge partition given in Table 4 we get

[mathematical expression not reproducible] (29)

Concluding Remarks. QSARs represent predictive models got from utilization of statistical instruments correlating biological activity (including desirable therapeutic effect and undesirable side effects) of chemicals (toxicants/drugs/environmental pollutants) with descriptors illustrative of molecular structure as well as properties. QSARs are being connected in many disciplines, for instance, toxicity prediction, risk assessment and regulatory decisions, lead optimization, and drug discovery. The atom-bond connectivity index denoted by ABC is a molecular structure descriptor that has remarkable application in rationalizing the stability of linear and branched alkanes and in the strain energy of cycloalkanes [25]. Weighted entropy is a generalization of Shannon's entropy and is the measure of information supplied by a probablistic experiment whose elementary events are characterized both by their objective probabilities and by some qualitative (objective or subjective) weights [29]. It is useful to rank chemicals in quantitative high-throughput screening experiments [30] and may be used to balance the amount of information and the degree of homogeneity associated to a partition of data in classes [31]. Weighted entropy also found applications in the coding theory [32]. For more insights about applications of entropy, please see [33]. In this paper we have studied weighted entropy with atomic bond connectivity edge weights, which was an open problem of [34]. Our next aim is to work on entropy of weighted graphs with geometric arithmetic and sum connectivity edge weights.

https://doi.org/10.1155/2018/8407032

Data Availability

The data used to support the findings of this study are included within the article.

Conflicts of Interest

Authors do not have any competing interests.

Authors' Contributions

All authors contributed equally to this paper.

Acknowledgments

This work was supported by the Dong-A University research fund.

References

[1] W. Gao, W. Wang, and M. R. Farahani, "Topological indices study of molecular structure in anticancer drugs," Journal of Chemistry, vol. 2016, 2016.

[2] W. Gao, M. R. Farahani, and L. Shi, "The forgotten topological index of some drug structures," Acta Medica Mediterranea, vol. 32, no. 1, pp. 579-585, 2016.

[3] S. Kang, Z. Iqbal, M. Ishaq, R. Sarfraz, A. Aslam, and W. Nazeer, "On eccentricity-based topological indices and polynomials of phosphorus-containing dendrimers," Symmetry, vol. 10, no. 7, p. 237, 2018.

[4] S. M. Kang, M. A. Zahid, W. Nazeer, and W. Gao, "Calculating the degree-based topological indices of dendrimers," Chemistry, vol. 16, no. 1, pp. 681-688, 2018.

[5] S. M. Kang, W. Nazeer, M. A. Zahid, A. R. Nizami, A. Aslam, and M. Munir, "M-polynomials and topological indices of hex-derived networks," Physics, vol. 16, no. 1, pp. 394-403, 2018.

[6] H. Wiener, "Structural determination of paraffin boilingpoints," Journal of the American Chemical Society, vol. 69, no. 1, pp. 1720, 1947.

[7] M. Randic, "On characterization of molecular branching," Journal of the American Chemical Society, vol. 97, no. 23, pp. 6609-6615, 1975.

[8] E. Estrada, L. Torres, L. Rodriguez, and I. Gutman, "An atombond connectivity index, modeling the enthalpy of formation of alkanes," Indian Journal of Chemistry, vol. 37, pp. 849-855, 1998.

[9] M. Ghorbani and M. A. Hosseinzadeh, "Hosseinzadeh, Computing index of nanostar dendrimers, Opto-electron," Optoelectronics and Advanced Materials, Rapid Communications, vol. 4, no. 9, pp. 1419-1422, 2010.

[10] W. Nazeer, A. Farooq, M. Younas, M. Munir, and S. Kang, "On Molecular Descriptors of Carbon Nanocones," Biomolecules, vol. 8, no. 3, p. 92, 2018.

[11] W. Gao, M. Younas, A. Farooq, A. Mahboob, and W. Nazeer, "M-Polynomials and Degree-Based Topological Indices of the Crystallographic Structure of Molecules," Biomolecules, vol. 8, no. 4, p. 107, 2018.

[12] Y. C. Kwun, M. Munir, W. Nazeer, S. Rafique, and S. M. Kang, "Computational Analysis of topological indices of two Boron Nanotubes," Scientific reports, vol. 8, no. 1, p. 14843, 2018.

[13] W. Gao, M. Younas, A. Farooq, A. Virk, and W. Nazeer, "Some Reverse Degree-Based Topological Indices and Polynomials of Dendrimers," Mathematics, vol. 6, no. 10, p. 214, 2018.

[14] M. Munir, W. Nazeer, S. Rafique, A. R. Nizami, and S. M. Kang, "Some computational aspects of boron triangular nanotubes," Symmetry, vol. 9, no. 1, 2017.

[15] Y. C. Kwun, M. Munir, W. Nazeer, S. Rafique, and S. M. Kang, "M-Polynomials and topological indices of V-Phenylenic Nanotubes and Nanotori," Scientific Reports, vol. 7, no. 1, 2017.

[16] C. E. Shannon, The Mathematical Theory of Communication, The University of Illinois Press, Urbana, Ill, USA, 1949.

[17] A. Mowshowitz, "Entropy and the complexity of graphs. II. The information content of digraphs and infinite graphs," Bulletin of Mathematical Biology, vol. 30, pp. 225-240, 1968.

[18] A. Mowshowitz, "Entropy and the complexity of graphs. I. An index of the relative complexity of a graph," Bulletin of Mathematical Biology, vol. 30, pp. 175-204, 1968.

[19] J. Korner, "Coding of an information source having ambiguous alphabet and the entropy of graphs," the 6th Pargue Conference on Information Theory, Statistical Decision, Functions, Random Processes, Pargue, Czech Republic, pp. 411-425, 1973.

[20] M. M. Dehmer, N. N. Barbarini, K. K. Varmuza, and A. A. Graber, "Novel topological descriptors for analyzing biological networks," BMC Structural Biology, vol. 10, article no. 18, 2010.

[21] M. Dehmer and A. Mowshowitz, "A history of graph entropy measures," Information Sciences, vol. 181, no. 1, pp. 57-78, 2011.

[22] Z. Chen, M. Dehmer, F. Emmert-Streib, and Y. Shi, "Entropy bounds for dendrimers," Applied Mathematics and Computation, vol. 242, pp. 462-472, 2014.

[23] S. Ji, X. Li, and B. Huo, "On reformulated Zagreb indices with respect to acyclic, unicyclic and bicyclic graphs," The Match!, vol. 72, no. 3, pp. 723-732, 2014.

[24] K. Xu, K. C. Das, and S. Balachandran, "Maximizing the Zagreb Indices of (n,m)-Graphs," MATCH Communications in Mathematical and in Computer Chemistry, vol. 72, pp. 641-654, 2014.

[25] K. C. Das, I. Gutman, and B. Furtula, "On atom-bond connectivity index," Filomat, vol. 26, no. 4, pp. 733-738, 2012.

[26] Y. Bashir, A. Aslam, M. Kamran et al., "On forgotten topological indices of some dendrimers structure," Molecules, vol. 22, no. 6, 2017.

[27] S. M. Kang, M. A. Zahid, W. Nazeer, and W. Gao, "Calculating the Degree-based Topological Indices of Dendrimers," Open Chemistry, 2018.

[28] A. Aslam, Y. Bashir, M. Rafiq, F. Haider, N. Muhammad, and N. Bibi, "Three New/Old Vertex-Degree-Based Topological Indices of Some Dendrimers Structure," Journal of Biology, vol. 13, no. 1, 2017.

[29] S. Guiasu, "Weighted entropy," Reports on Mathematical Physics, vol. 2, no. 3, pp. 165-179, 1971.

[30] K. R. Shockley, "Using weighted entropy to rank chemicals in quantitative high-throughput screening experiments," Journal of Biomolecular Screening, vol. 19, no. 3, pp. 344-353, 2014.

[31] S. Guia?u, "Grouping data by using the weighted entropy," Journal of Statistical Planning and Inference, vol. 15, no. 1, pp. 63-69, 1986.

[32] A. Clim, "Weighted entropy with application," Analele Universitatii Bucuresti: Matematica, pp. 223-231, 2008.

[33] M. Ghorbani, M. Dehmer, and S. Zangi, "Graph operations based on using distance-based graph entropies," Applied Mathematics and Computation, vol. 333, pp. 547-555, 2018.

[34] Z. Chen, M. Dehmer, F. Emmert-Streib, and Y. Shi, "Entropy of weighted graphs with Randic weights," Entropy, vol. 17, no. 6, pp. 3710-3723, 2015.

Young Chel Kwun (iD), (1) Hafiz Mutee ur Rehman, (2,3) Muhammad Yousaf, (4) Waqas Nazeer (iD), (2) and Shin Min Kang (iD) (5,6)

(1) Department of Mathematics, Dong-A University, Busan 49315, Republic of Korea

(2) Division of Science and Technology, University of Education Lahore 54000, Pakistan

(3) Department of Mathematics and Statistics, The University of Lahore, Lahore 54000, Pakistan

(4) Department of Mathematics, COMSATS University Islamabad, Lahore, Campus, Lahore 54000, Pakistan

(5) Department of Mathematics and RINS, Gyeongsang National University, Jinju 52828, Republic of Korea

(6) Center for General Education, China Medical University, Taichung 40402, Taiwan

Correspondence should be addressed to Waqas Nazeer; nazeer.waqas@ue.edu.pk and Shin Min Kang; smkang@gnu.ac.kr

Received 24 July 2018; Revised 30 October 2018; Accepted 27 November 2018; Published 16 December 2018

Academic Editor: Manuel De la Sen

Caption: Figure 1: Porphyrin dendrimer.

Caption: Figure 2: Propyl ether imine dendrimer.

Caption: Figure 3: Zinc-Porphyrin dendrimer.

Caption: Figure 4: Poly(EThyleneAmidoAmine dendrimer.
Table 1: Edge partition of Porphyrin dendrimers based on degree of end
vertices of each edge.

([d.sub.uv],         (1,3)   (1,4)   (2,2)    (2,3)    (3,3)   (3,4)
   [d.sub.v])
Number of edges       2n      24n    10n-5    48n-6     13n     8n

Table 2: Edge partition of propyl ether imine dendrimers based on
degree of end vertices of each edge.

([d.sub.u], [d.sub.v])      (1,2)          (2,2)            (2,3)
Number of edges          [2.sup.n+1]    [2.sup.n+4]    [6.2.sup.n] - 6

Table 3: Edge partition of Zinc-Porphyrin dendrimers based on degree
of end vertices of each edge.

([d.sub.u], [d.sub.v])         (2,2)                (2,3)
Number of edges           [16.2.sup.n] - 4    [40.2.sup.n] - 16

([d.sub.u], [d.sub.v])         (3,3)           (3, 4)
Number of edges           [8.2.sup.n] - 16       4

Table 4: Edge partition of Poly(EThyleneAmidoAmine dendrimers based on
degree of end vertices of each edge.

([d.sub.u], [d.sub.v])      (1,2)             (1,3)
Number of edges          [4.2.sup.n]     [4.2.sup.n] - 2

([d.sub.u], [d.sub.v])      (2,2)             (2, 3)
Number of edges          [16.2.sup.n]    [20.2.sup.n] - 9
COPYRIGHT 2018 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2018 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Kwun, Young Chel; Rehman, Hafiz Mutee ur; Yousaf, Muhammad; Nazeer, Waqas; Kang, Shin Min
Publication:Discrete Dynamics in Nature and Society
Geographic Code:9PAKI
Date:Jan 1, 2018
Words:3439
Previous Article:Global Dynamics of Some 3 x 6 Systems of Exponential Difference Equations.
Next Article:Modeling of Lateral Stability of Tractor-Semitrailer on Combined Alignments of Freeway.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters