Novel inequalities for generalized graph entropies – graph energies and topological indices. (English) Zbl 1390.05132
Summary: The entropy of a graph is an information-theoretic quantity for measuring the complexity of a graph. After Shannon introduced the entropy to information and communication, many generalizations of the entropy measure have been proposed, such as Rényi entropy and Daróczy entropy. In this article, we prove accurate connections (inequalities) between generalized graph entropies, graph energies, and topological indices. Additionally, we obtain some extremal properties of nine generalized graph entropies by employing graph energies and topological indices.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C90 | Applications of graph theory |
| 05C35 | Extremal problems in graph theory |
| 94A17 | Measures of information, entropy |
References:
| [1] | Arndt, C., Information Measures (2004), Springer: Springer Berlin · Zbl 0973.94001 |
| [2] | Adiga, C.; Balakrishnan, R.; So, W., The skew energy of a digraph, Linear Algebra Appl., 432, 1825-1835 (2010) · Zbl 1217.05131 |
| [3] | Barabási, A. L.; Gulbahce, N.; Loscalzo, J., Network medicine: a network-based approach to human disease, Nat. Rev. Genet., 12, 56-68 (2011) |
| [4] | Bonchev, D., Information indices for atoms and molecules, MATCH Commun. Math. Comput. Chem., 7, 65-113 (1979) |
| [5] | Bonchev, D., Information Theoretic Indices for Characterization of Chemical Structures (1983), Research Studies Press: Research Studies Press Chichester |
| [6] | Bozkurt, Ş. B.; Bozkurt, D., On incidence energy, MATCH Commun. Math. Comput. Chem., 72, 215-225 (2014) · Zbl 1464.05228 |
| [7] | Bozkurt, Ş. B.; Güngör, A. D.; Gutman, I.; Çevik, A. S., Randić matrix and Randić energy, Math. Comput. Chem., 64, 239-250 (2010) · Zbl 1265.05113 |
| [8] | Daróczy, Z.; Jarai, A., On the measurable solutions of functional equations arising in information theory, Acta Math. Acad. Sci. Hung., 34, 105-116 (1979) · Zbl 0424.39002 |
| [9] | Das, K. C.; Sorgun, S.; Gutman, I., On Randić energy, MATCH Commun. Math. Comput. Chem., 73, 81-92 (2015) · Zbl 1464.05233 |
| [10] | Dehmer, M., Information processing in complex networks: graph entropy and information functionals, Appl. Math. Comput., 201, 82-94 (2008) · Zbl 1152.05361 |
| [12] | Dehmer, M.; Kraus, V., On extremal properties of graph entropies, MATCH Commun. Math. Comput. Chem., 68, 889-912 (2012) · Zbl 1289.05228 |
| [13] | Dehmer, M.; Mowshowitz, A., A history of graph entropy measures, Inf. Sci., 181, 57-78 (2011) · Zbl 1204.94050 |
| [14] | Dehmer, M.; Mowshowitz, A., Generalized graph entropies, Complexity, 17, 45-50 (2011) |
| [15] | Dehmer, M.; Sivakumar, L.; Varmuza, K., Uniquely discriminating molecular structures using novel eigenvalue-based descriptors, MATCH Commun. Math. Comput. Chem., 67, 147-172 (2012) |
| [16] | Dobrynin, A. A.; Entringer, R.; Gutman, I., Wiener index of trees: theory and applications, Acta Appl. Math., 66, 211-249 (2001) · Zbl 0982.05044 |
| [17] | Emmert-Streib, F., The chronic fatigue syndrome: a comparative pathway analysis, J. Comput. Biol., 14, 961-972 (2007) |
| [18] | Emmert-Streib, F.; Dehmer, M., Identifying critical financial networks of the DJIA: toward a network-based index, Complexity, 16, 24-33 (2010) |
| [19] | Gu, R.; Huang, F.; Li, X., Randić incidence energy of graphs, Trans. Combin., 3, 1-9 (2014) · Zbl 1463.05331 |
| [20] | Gu, R.; Huang, F.; Li, X., General Randić matrix and general Randić energy, Trans. Combin., 3, 21-33 (2014) · Zbl 1463.05330 |
| [22] | Gutman, I., The energy of a graph, Ber. Math.-Stat. Sekt. Forschungsz. Graz, 103, 1-22 (1978) · Zbl 0402.05040 |
| [23] | Gutman, I., Degree-based topological indices, Croat. Chem. Acta, 86, 351-361 (2013) |
| [24] | (Gutman, I.; Furtula, B., Recent Results in the Theory of Randić Index (2008), Univ. Kragujevac: Univ. Kragujevac Kragujevac) · Zbl 1294.05002 |
| [25] | Gutman, I.; Kiani, D.; Mirzakhah, M., On incidence energy of graphs, MATCH Commun. Math. Comput. Chem., 62, 573-580 (2009) · Zbl 1199.05221 |
| [26] | Gutman, I.; Li, X.; Zhang, J., Graph energy, (Dehmer, M.; Emmert-Streib, F., Analysis of Complex Networks: From Biology to Linguistics (2009), Wiley-VCH: Wiley-VCH Weinheim), 145-174 · Zbl 1256.05140 |
| [27] | Gutman, I.; Trinajstić, N., Graph theory and molecular orbitals. Total \(\pi \)-electron energy of alternant hydrocarbons, Chem. Phys. Lett., 17, 535-538 (1972) |
| [28] | Huang, G.; Kuang, M.; Deng, H., Extremal graph with respect to matching energy for a random polyphenyl chain, MATCH Commun. Math. Comput. Chem., 73, 121-131 (2015) · Zbl 1464.05208 |
| [29] | Ilić, A.; Ilić, M.; Liu, B., On the upper bounds for the first Zagreb index, Kragujevac J. Math., 35, 173-182 (2011) · Zbl 1265.05119 |
| [30] | Jooyandeh, M.; Kiani, D.; Mirzakhah, M., Incidence energy of a graph, MATCH Commun. Math. Comput. Chem., 62, 561-572 (2009) · Zbl 1274.05295 |
| [32] | Li, X.; Gutman, I., Mathematical Aspects of Randić-type Molecular Structure Descriptors (2006), Univ. Kragujevac: Univ. Kragujevac Kragujevac · Zbl 1294.92032 |
| [33] | Li, X.; Shi, Y.; Gutman, I., Graph Energy (2012), Springer: Springer New York · Zbl 1262.05100 |
| [34] | Li, X.; Yang, Y., Sharp bounds for the general Randić index, MATCH Commun. Math. Comput. Chem., 51, 155-166 (2004) · Zbl 1053.05067 |
| [35] | Lieberman, E.; Hauert, C.; Nowak, M. A., Evolutionary dynamics on graphs, Nature, 433, 312-316 (2005) |
| [36] | Lozovanu, D.; Pickl, S., Discrete control and algorithms for solving antagonistic dynamic games on networks, Optimization, 58, 665-683 (2009) · Zbl 1167.90396 |
| [37] | Mowshowitz, A., Entropy and the complexity of the graphs I: an index of the relative complexity of a graph, Bull. Math. Biophys., 30, 175-204 (1968) · Zbl 0165.57601 |
| [38] | Mukwembi, S., Effects of density of infected population to the spreading of HIV epidemic in communities, Phys. A, 390, 3915-3921 (2011) |
| [39] | Mukwembi, S.; Rodrigues, B. G.; Nyabadza, F., Graph theoretic application to disease models, (Nyabadza, F.; Kgosimore, M.; Lungu, E. M., A Treatise of Biological Models (2012), Nova: Nova New York), 97-126 |
| [40] | Nikiforov, V., The energy of graphs and matrices, J. Math. Anal. Appl., 326, 1472-1475 (2007) · Zbl 1113.15016 |
| [41] | Ramane, H. S.; Revankar, D. S.; Gutman, I.; Rao, S. B.; Acharya, B. D.; Walikar, H. B., Bounds for the distance energy of a graph, Kragujevac J. Math., 31, 59-68 (2008) · Zbl 1199.05239 |
| [42] | Randić, M., On characterization of molecular branching, J. Am. Chem. Soc., 97, 6609-6615 (1975) |
| [43] | Randić, M., On history of the Randić index and emerging hostility toward chemical graph theory, MATCH Commun. Math. Comput. Chem., 59, 5-124 (2008) · Zbl 1150.01007 |
| [44] | Rashevsky, N., Life, information theory and topology, Bull. Math. Biophys., 17, 229-235 (1955) |
| [46] | Shannon, C. E.; Weaver, W., The Mathematical Theory of Communication (1949), Univ Illinois Press · Zbl 0041.25804 |
| [47] | Shi, L., Bounds on Randić indices, Discrete Math., 309, 5238-5241 (2009) · Zbl 1179.05039 |
| [48] | Todeschini, R.; Consonni, V., Handbook of Molecular Descriptors (2002), Wiley-VCH: Wiley-VCH Weinheim |
| [49] | Wiener, H., Structural determination of paraffin boiling points, J. Am. Chem. Soc., 69, 17-20 (1947) |
| [50] | Xu, K.; Liu, M.; Das, K. C.; Gutman, I.; Furtula, B., A survey on graphs extremal with respect to distance-based topological indices, MATCH Commun. Math. Comput. Chem., 71, 461-508 (2014) · Zbl 1464.05140 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
