Survey of Graph Energies

Document Type : Special Issue: Energy of Graphs

Authors

1 University Kragujevac, Serbia

2 State University of Novi Pazar, Novi Pazar, Serbia

Abstract

Let graph energy is a graph--spectrum--based quantity‎, ‎introduced in the 1970s‎. ‎After a latent period of 20--30 years‎, ‎it became a popular topic of research both‎ ‎in mathematical chemistry and in ``pure'' spectral graph theory‎, ‎resulting in‎ ‎over 600 published papers‎. ‎Eventually‎, ‎scores of different graph energies have‎ ‎been conceived‎. ‎In this article we provide the basic facts on graph energies‎, ‎in particular historical and bibliographic data.‎

Keywords

Main Subjects


1. C. A. Coulson, On the calculation of the energy in unsaturated hydrocarbon molecules, Proc. Cambridge Phil. Soc. 36 (1940) 201–203.
2. I. Gutman, Acyclic systems with extremal Hückel Pi-electron energy, Theoret. Chim. Acta 45 (1977) 79–87.
3. I. Gutman, The energy of a graph, Ber. Math. -Statist. Sekt. Forsch. Graz 103 (1978) 1–22.
4. I. Gutman, Acyclic conjugated molecules, trees and their energies, J. Math. Chem. 1 (1987) 123–144.
5. I. Gutman, The energy of a graph: old and new results, in: A. Betten, A. Kohnert, R. Laue, A. Wassermann (Eds.), Algebraic Combinatorics and Applications, Springer, Berlin, 2001, pp. 196–211.
6. I. Gutman, O. E. Polansky, Mathematical Concepts in Organic Chemistry, Springer, Berlin, 1986.
7. B. J. McClelland, Properties of the latent roots of a matrix: The estimation of π-electron energies, J. Chem. Phys. 54 (1971) 640–643.
8. F. Zhang, Two theorems of comparison of bipartite graphs by their energy, Kexue Tongbao 28 (1983) 726–730.
9. F. Zhang, Z. Lai, Three theorems of comparison of trees by their energy, Sci. Explor. 3 (1983) 12–19.
10. N. Abreu, D. M. Cardoso, I. Gutman, E. A. Martins, M. Robbiano, Bounds for the signless Laplacian energy, Linear Algebra Appl. 435 (2011) 2365–2374.
11. B. D. Acharya, S. B. Rao, T. Singh, The minimum robust domination energy of a connected graph, AKCE Int. J. Graphs Comb. 4 (2007) 139–143.
12. B. D. Acharya, S. B. Rao, P. Sumathi, V. Swaminathan, Energy of a set of vertices in a graph, AKCE Int. J. Graphs Comb. 4 (2007) 145–152.
13. C. Adiga, R. Balakrishnan, W. So, The skew energy of a digraph,
Linear Algebra Appl. 432 (2010) 1825–1835.
14. C. Adiga, A. Bayad, I. Gutman, A. S. Shrikanth, The minimum covering energy of a graph, Kragujevac J. Sci. 34 (2012) 39–56.
15. C. Adiga, E. Sampathkumar, M. A. Sriraj, A. S. Shrikanth, Color energy of a graph, Proc. Jangjeon Math. Soc. 16 (2013) 335–351.
16. C. Adiga, M. Smitha, On maximum degree energy of a graph, Int. J. Contemp. Math. Sci. 4 (2009) 385–396.
17. C. Adiga, M. Smitha, On the skew Laplacian energy of a digraph, Int. Math. Forum 4 (2009) 1907–1914.
18. N. Agudelo, J. Rada, Lower bounds of Nikiforov’s energy over digraphs, Linear Algebra Appl. 494 (2016) 156–164.

19. S. Alikhani, M. A. Iranmanesh, Energy of graphs, matroids and Fibonacci numbers,
Iran. J. Math. Sci. Inform 5 (2) (2010) 55–60.
20. A. Alwardi, N. D. Soner, I. Gutman, On the common–neighbourhood energy of a graph, Bull. Acad. Serbe Sci. Arts (Cl. Math. Natur.) 143 (2011) 49–59.
21. S. K. Ayyaswamy, S. Balachandran, I. Gutman, On second–stage spectrum and energy of a graph, Kragujevac J. Math. 34 (2010) 139–146.
22. V. Božin, M. Mateljević , Energy of graphs and orthogonal matrices, in: W. Gautschi, G. Mastroianni, T. M. Rassias (Eds.), Approximation and Computation – In Honor of Gradimir V. Milovanović, Springer, New York, 2011, pp. 87–96.
23. Ş. B. Bozkurt, A. D. Güngör, I. Gutman, A. S Çevik, Randić matrix and Randić energy, MATCH Commun. Math. Comput. Chem. 64 (2010) 239–250.
24. M. Cavers, S. Fallat, S. Kirkland, On the normalized Laplacian energy and general Randić index R-1 of graphs, Linear Algebra Appl. 433 (2010) 172–190.
25. B. Cheng, B. Liu, The normalized incidence energy of a graph, Linear Algebra Appl. 438 (2013) 4510–4519.
26. V. Consonni, R. Todeschini, New spectral indices for molecule description, MATCH Commun. Math. Comput. Chem. 60 (2008) 3–14.
27. K. Ch. Das, F. M. Bhatti, S. G. Lee, I. Gutman, Spectral properties of the He matrix of hexagonal systems, MATCH Commun. Math. Comput. Chem. 65 (2011) 753–774.
28. K. C. Das, A. D. Güngör, A. S. Çevik, On Kirchhoff index and resistance– distance energy of a graph, MATCH Commun. Math. Comput. Chem. 67 (2012) 541–556.
29. A. C. Dinesh, Puttaswamy, The minimum maximal domination energy of a graph, Int. J. Math. Appl. 3 (3-A) (2015) 31–40.
30. G. H. Fath–Tabar, The Szeged energy of fullerene graph, 7th Slovenian International Conference on Graph Theory, 19-25 June 2011 Bled, Slovenia.
31. R. Gu, F. Huang, X. Li, Randić incidence energy of graphs, Trans. Comb. 3 (4) (2014) 1–9.
32. R. Gu, F. Huang, X. Li, General Randić matrix and general Randić energy, Trans. Comb. 3 (3) (2014) 21–33.
33. R. Gu, F. Huang, X. Li, Skew Randić matrix and skew Randić energy, Trans. Comb. 5 (1) (2016) 1–14.
34. A. D. Güngör, A. S. Çevik, On the Harary energy and Harary Estrada index of a graph, MATCH Commun. Math. Comput. Chem. 64 (2010) 281–296.
35. I. Gutman, The energy of a graph, Ber. Math.–Statist. Sekt. Forsch. Graz 103 (1978) 22 pp.
36. I. Gutman, Bounds for all graph energies, Chem. Phys. Lett. 528 (2012) 72–74.
37. I. Gutman, B. Furtula, E. Zogić, E. Glogić, Resolvent energy of graphs, MATCH Commun. Math. Comput. Chem. 75 (2016) 279–290.
38. I. Gutman, S. Wagner, The matching energy of a graph, Discrete Appl. Math. 160 (2012) 2177–2187.
39. I. Gutman, B. Zhou, Laplacian energy of a graph, Linear Algebra Appl. 414 (2006) 29–37.
40. W. H. Haemers, Seidel switching and graph energy, MATCH Commun. Math. Comput. Chem. 68 (2012) 653–659.
41. G. Indulal, I. Gutman, A. Vijayakumar, On distance energy of graphs, MATCH Commun. Math. Comput. Chem. 60 (2008) 461–472.
42. S. P. Jeyakokila, P. Sumathi, soEnergy of some standard graphs, Procedia Comput. Sci. 47 (2015) 360–367.
43. S. P. Jeyakokila, P. Sumathi, A note on soEnergy of stars, bistar and double star graphs, Bull. Int. Math. Virtual Inst. 6 (2016) 105–113.
44. M. R. Jooyandeh, D. Kiani, M. Mirzakhah, Incidence energy of a graph, MATCH Commun. Math. Comput. Chem. 62 (2009) 561–572.
45. H. Kharaghani, B. Tayfeh–Rezaie, On the energy of (0; 1)-matrices, Linear Algebra Appl. 429 (2008) 2046–2051.
46. M. K. Kumar, Characteristic polynomial & domination energy of some special class of graphs, in: L. Mao (Ed.), Mathematical Combinatorics (International Book Series) Vol. 1 (2014), Univ. Beijing, Beijing, 2014, pp. 37–48.

47. R. Li, On
α-incidence energy and α-distance energy of a graph, Ars Comb. 121 (2015) 373–384.
48. J. Liu, X. Li, Hermitian–adjacency matrices and Hermitian energies of mixed graphs, Linear Algebra Appl. 466 (2015) 182–207.
49. J. Liu, B. Liu, A Laplacian–energy like invariant of a graph, MATCH Commun. Math. Comput. Chem. 59 (2008) 355–372.
50 A. D. Maden, A. S. Cevik, I. N. Cangul, K. C. Das, On the Kirchhoff matrix, a new Kirchhoff index and the Kirchhoff energy, J. Inequal. Appl. 2013(2013) 337.
51. V. Mathad, S. S. Mahde, The minimum hub distance energy of a graph, Int. J. Comput. Appl. 125 (2015) 1–6.
52. M. Mateljević, V. Božin, I. Gutman, Energy of a polynomial and the Coulson integral formula, J. Math. Chem. 48 (2010) 1602–1068.
53. K. B. Murthy, Puttaswamy, A. M. Naji, The complementary dominating energy of a graph, Indian Streems Res. J. 5 (6) (2015) 1–7.
54. N. Murugesan, D. Narmatha, e and n-energies of linear semigraph, Int. J. Res. Engin. Technol. 3 (2014) 174–178.
55. M. J. Nadjafi-Arani, Sharp bounds on the PI and vertex PI energy of graphs, MATCH Commun. Math. Comput. Chem. 65 (2011) 123–130.
56. A. M. Naji, N. D. Soner, The minimum monopoly energy of a graph, Int. J. Math. Appl. 3 (4B) (2015) 47–58.
57. A. M. Naji, N. D. Soner, The minimum monopoly distance energy of a graph, Int. J. Comput. Appl. 128 (3) (2015) #0975-8887.
58. V. Nikiforov, The energy of graphs and matrices, J. Math. Anal. Appl. 326 (2007) 1472–1475.
59. M. R. Rajesh Kanna, B. N. Dharmendra, R. Pradeep Kumar, Minimum covering distance energy of a graph, Appl. Math. Sci. 7 (2013) 5525–5536.
60. M. R. Rajesh Kanna, B. N. Dharmendra, G. Sridhara, Laplacian minimum dominating energy of a graph, Int. J. Pure Appl. Math. 89 (2013) 565–581.
61. M. R. Rajesh Kanna, B. N. Dharmendra, G. Sridhara, The minimum dominating energy of a graph, Int. J. Pure Appl. Math. 85 (2013) 707–718.

62. M. R. Rajesh Kanna, B. N. Dharmendra, G. Sridhara, Laplacian minimum covering energy of a graph,
Adv. Appl. Discrete Math. 13 (2014) 85–108.
63. M. R. Rajesh Kanna, R. Pradeep Kumar, R. Jagadeesh, Minimum covering color energy of a graph, Int. J. Math. Anal. 9 (2015) 351–364.
64. J. M. Rodríguez, J. M. Sigarreta, Spectral properties of geometric–arithmetic index, Appl. Math. Comput. 277 (2016) 142–153.
65. L. Shi, H. Wang, The Laplacian incidence energy of graphs, Linear Algebra Appl. 439 (2013) 4056–4062.

66. D. Stevanović, N. M. M. de Abreu, M. A. A. de Freitas, C. Vinagre, R. Del-Vecchio, On the oriented incidence energy and decomposable graphs,
Filomat 23 (2009) 243–249.
67. V. Trevisan, private communication (2016).
68. J. Yang, L. You, I. Gutman, Bounds on the distance Laplacian energy of graphs, Kragujevac J. Math. 37 (2013) 245–255.
69. B. Zhou, N. Trinajstić, On sum-connectivity matrix and sum-connectivity energy of (molecular) graphs, Acta Chim. Slov. 57 (2010) 518–523.
70. M. E. Bolaños, S. Aviyente, Quantifying the functional importance of neuronal assemblies in the brain using Laplacian Hückel graph energy, Proceedings of Int. Conf. on Acoustics, Speech and Signal Processing, Prague, 2011, pp. 753–756.

71. M. Daianu, A. Mezher, N. Jahanshad, D. P. Hibar, T. M. Nir, C. R. Jack, M. W. Weiner, M. A. Bernstein, P. M. Thompson, Spectral graph theory and graph energy metrics show evidence for the Alzheimer’s disease disconnection
syndrome in APOE-4 risk gene carriers,
Proc. IEEE Int. Symp. Biomed Imaging 2015 (2015) 458–461.
72. M. Dehmer, X. Li, Y. Shi, Connections between generalized graph entropies and graph energy, Complexity 21 (2015) 35–41.
73. L. Di Paola, G. Mei, A. Di Venere, A. Giuliani, Exploring the stability of dimers through protein structure topology, Curr. Protein Pept. Sci. 17 (2016) 30–36.
74. I. Gutman, D. Vidović, N. Cmiljanović, S. Milosavljević, S. Radenković, Graph energy – A useful molecular structure–descriptor, Indian J. Chem. 42A (2003) 1309–1311.
75. X. Li, Z. Qin, M. Wei, I. Gutman, M. Dehmer, Novel inequalities for generalized graph entropies – Graph energies and topological indices, Appl. Math. Comput. 259 (2015) 470–479.

76. S. C. Rakshit, B. Hazra, Correlations among molecular properties, quantum mechanical and topological quantities,
J. Indian Chem. Soc. 67 (1990) 887–891.

77. Y. Z. Song, P. Arbelaez, P. Hall, C. Li, A. Balikai, Finding semantic structures in image hierarchies using Laplacian graph energy, in: K. Daniilidis, P. Maragos, N. Paragios (Eds.), 11th European Conference on Computer Vision, ECCV 2010, September 5, 2010 - September 11, 2010, Part IV, Springer–Verlag, Berlin, 2010, pp. 694–707.

78. D. Sun, C. Xu, Y. Zhang, A novel method of 2D graphical representation for proteins and its application,
MATCH Commun. Math. Comput. Chem. 75 (2016) 431–446.
79. P. Van Mieghem, R. van de Bovenkamp, Accuracy criterion for the mean–field approximation in susceptible–infected–susceptible epidemics on networks, Phys. Rev. E, Stat. Nonlin. Soft Matter Phys. 91 (2015) 032812.
80. H. Wu, Y. Zhang, W. Chen, Z. Mu, Comparative analysis of protein primary sequences with graph energy, Physica A: Statistical Mechanics and its Applications 437 (2015) 249–262.
81. H. Zhang, X. Bai, H. Zheng, H. Zhao, J, Zhou, J. Cheng, H. Lu. Hierarchical remote sensing image analysis via graph Laplacian energy, IEEE Geosci. Remote Sensing Lett. 10 (2013) 396–400.
82. E. O. D. Andriantiana, Laplacian energy, in: I. Gutman, X. Li (Eds.), Graph Energies – Theory and Applications, Univ. Kragujevac, Kragujevac, 2016, pp. 49–80.
83. Ş. B. Bozkurt Altındağ, D. Bozkurt, Lower bounds via new approaches for incidence energy, in: I. Gutman, X. Li (Eds.), Graph Energies – Theory and Applications, Univ. Kragujevac, Kragujevac, 2016, pp. 145–166.

84. K. C. Das, S. Sorgun, K. Xu, On Randić energy of graphs, in: I. Gutman, X. Li (Eds.), Graph Energies – Theory and Applications, Univ. Kragujevac, Kragujevac, 2016, pp. 111–122.
85. I. Gutman, The energy of a graph: Old and new results, in: A. Betten, A. Kohnert, R. Laue, A. Wassermann (Eds.), Algebraic Combinatorics and Applications, Springer–Verlag, Berlin, 2001, pp. 196–211.
86. I. Gutman, Hyperenergetic and hypoenergetic graphs, in: D. Cvetković, I. Gutman (Eds.), Selected Topics on Applications of Graph Spectra, Math. Inst., Belgrade, 2011, pp. 113–135.

87. I. Gutman, Comparative studies of graph energies,
Bull. Acad. Serbe Sci. Arts (Cl. Sci. Math. Natur.) 144 (2012) 1–17.

88. I. Gutman, Matching energy, in: I. Gutman, X. Li (Eds.),
Graph Energies – Theory and Applications, Univ. Kragujevac, Kragujevac, 2016, pp. 167–190.

89. I. Gutman, B. Furtula, E. Zogić, E. Glogić, Resolvent energy, in: I. Gutman, X. Li (Eds.),
Graph Energies – Theory and Applications, Univ. Kragujevac, Kragujevac, 2016, pp. 277–290.
90. I. Gutman, X. Li, J. Zhang, Graph energy, in: M. Dehmer, F. Emmert–Streib (Eds.), Analysis of Complex Networks. From Biology to Linguistics, Wiley–VCH, Weinheim, 2009, pp. 145–174.

91. X. Li, H. Lian, Skew energy of oriented graphs, in: I. Gutman, X. Li (Eds.),
Graph Energies – Theory and Applications, Univ. Kragujevac, Kragujevac, 2016, pp. 191–236.

92. B. Liu, Y. Huang, Z. You, A survey on the Laplacian–energy–like invariant,
MATCH Commun. Math. Comput. Chem. 66 (2011) 713–730.
93. S. Majstorović, A. Klobučar, I. Gutman, Selected topics from the theory of graph energy: hypoenergetic graphs, in: D. Cvetković, I. Gutman (Eds.), Applications of Graph Spectra, Math. Inst., Belgrade, 2009, pp. 65–105.
94. S. Meenakshi, S. Lavanya, A survey on energy of graphs, Ann. Pure Appl. Math. 8 (2014) 183–191.
95. V. Nikiforov, Energy of matrices and norms of graphs, in: I. Gutman, X. Li (Eds.), Graph Energies – Theory and Applications, Univ. Kragujevac, Kragujevac, 2016, pp. 5–48.

96. J. Rada, Energy of digraphs, in: I. Gutman, X. Li (Eds.),
Graph Energies – Theory and Applications, Univ. Kragujevac, Kragujevac, 2016, pp. 237–276.

97. H. S. Ramane, Distance energy of graphs, in: I. Gutman, X. Li (Eds.),
Graph Energies – Theory and Applications, Univ. Kragujevac, Kragujevac, 2016, pp. 123–144.
98. D. Stevanović, S. Wagner, Laplacian–energy–like invariant: Laplacian coefficients, extremal graphs and bounds, in: I. Gutman, X. Li (Eds.), Graph Energies – Theory and Applications, Univ. Kragujevac, Kragujevac, 2016, pp. 81–110.
99. I. Triantafillou, On the energy of graphs, in: T. M. Rassias, L. Tóth (Eds.), Topics in Mathematical Analysis and Applications, Springer, Cham, 2014, pp. 699–714.
100. R. Balakrishnan, K. Ranganathan, A Textbook of Graph Theory, Springer, New York, 2012.
101. R. B. Bapat, Graphs and Matrices, Springer – Hindustan Book Agency, London, 2011.
102. A. Betten, A. Kohnert, R. Laue, A. Wassermann (Eds.), Algebraic Combinatorics and Applications, Springer–Verlag, Berlin, 2001.
103. A. E. Brouwer, W. H. Haemers, Spectra of Graphs, Universitext. Springer, New York, 2012.
104. D. M. Cvetković, M. Doob, I. Gutman, A. Torgašev, Recent Results in the Theory of Graph Spectra, Annals of Discrete Mathematics, 36, NorthHolland Publishing Co., Amsterdam, 1988.
105. D. M. Cvetković, M. Doob, H. Sachs, Spectra of Graphs – Theory and Application, Academic Press, New York, 1980.
106. D. Cvetkovich, M. Dub, H. Zahs, Spektry grafov – Teoriya i primenenie [Spectra of Graphs – Theory and Application], Naukova Dumka, Kiev, 1984.
107. D. M. Cvetković, M. Doob, H. Sachs, Spectra of Graphs – Theory and Applications, Barth, Heidelberg, 1995.
108. D. Cvetković, I. Gutman (Eds.), Applications of Graph Spectra, Math. Inst., Belgrade, 2009.
109. D. Cvetković, I. Gutman (Eds.), Selected Topics on Applications of Graph Spectra, Zb. Rad. (Beogr.) 14 (22) 2011.

110. D. Cvetković, P. Rowlinson, S. Simić,
An Introduction to the Theory of Graph Spectra, London Mathematical Society Student Texts, 75, Cambridge University Press, Cambridge, 2010.
111. M. Dehmer, F. Emmert–Streib (Eds.), Analysis of Complex Networks. From Biology to Linguistics, Wiley–VCH, Weinheim, 2009.
112. A. Graovac, I. Gutman, N. Trinajstić, Topological Approach to the Chemistry of Conjugated Molecules, Springer-Verlag Berlin Heidelberg, 1977.
113. I. Gutman, Introduction to Chemical Graph Theory, Faculty of Science, Kragujevac, 2003 (in Serbian).

114. I. Gutman, X. Li (Eds.),
Graph Energies – Theory and Applications, Univ. Kragujevac, Kragujevac, 2016.

115. I. Gutman, O. E. Polansky,
Mathematical Concepts in Organic Chemistry, Springer-Verlag, Berlin, 1986.
116. X. Li. Y. Shi, I. Gutman, Graph Energy, Springer, New York, 2012.
117. T. M. Rassias, L. Tóth (Eds.), Topics in Mathematical Analysis and Applications, Springer Optimization and Its Applications, 94, Springer, Cham, 2014.
118. Z. Stanić, Inequalities for Graph Eigenvalues, London Mathematical Society Lecture Note Series, 423, Cambridge University Press, Cambridge, 2015.
119. P. Van Mieghem, Graph Spectra for Complex Networks, Cambridge University Press, Cambridge, 2011.