On tetracyclic graphs having minimum energies. (English) Zbl 1509.05115
Summary: The energy of a graph is defined as the sum of the absolute values of all eigenvalues with respect to its adjacency matrix. Denote by \(G_{n,m}\) the set of all connected graphs having \(n\) vertices and \(m\) edges. G. Caporossi et al. [J. Chem. Inf. Comput. Sci. 39, No. 6, 984–996 (1999; doi:10.1021/ci9801419)] conjectured that among all graphs in \(G_{n,m}\), \(n \geq 6\) and \(n - 1 \leq m \leq 2(n - 2)\), the graphs with minimum energy are the star \(S_n\) with \(m - n + 1\) additional edges all connected to the same vertices for \(m \leq n + \lfloor (n-7)/2 \rfloor\), and the bipartite graph with two vertices on one side, one of which is connected to all vertices on the other side, otherwise. In this paper, we provide a new approach to investigate the conjecture above. Especially, we determine the unique tetracyclic graph having minimum energy.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
| 05C35 | Extremal problems in graph theory |
References:
| [1] | Cvetković, D.; Gutman, I., Applications of graph spectra (2009), Belgrade: Mathematical Institution, Belgrade · Zbl 1166.05002 |
| [2] | Graovac, A.; Gutman, I.; Trinajstić, N., Topological approach to the chemistry of conjugated molecules (1977), Berlin: Springer, Berlin · Zbl 0385.05032 |
| [3] | Gutman, I., The energy of a graph, Ber Math-Stat Sekt Forschungszent Graz, 103, 1-22 (1978) · Zbl 0402.05040 |
| [4] | Gutman, I.; Polansky, OE., Mathematical concepts in organic chemistry (1986), Berlin: Springer, Berlin · Zbl 0657.92024 |
| [5] | Gutman, I.; Mateljević, M., Note on the Coulson integral formula, J Math Chem, 39, 259-266 (2006) · Zbl 1101.92062 |
| [6] | Gutman, I. The energy of a graph: old and new results. Algebraic Combinatorics and Applications. Berlin: Springer; 2001. p. 196-211. · Zbl 0974.05054 |
| [7] | Gutman, I, Li, X, Zhang, J. Graph energy. In: Dehmer M, Emmert-Streib F, editors. Analysis of complex networks: from biology to linguistics. Weinheim: Wiley-VCH Verlag; 2009. p. 145-174. · Zbl 1256.05140 |
| [8] | Li, X.; Shi, Y.; Gutman, I., Graph energy (2012), Berlin: Springer, Berlin · Zbl 1262.05100 |
| [9] | Akbari, S.; Ghorbani, E.; Oboudi, M., Edge, addition singular values and energy of graphs and matrices, Lin Algebra Appl, 430, 2192-2199 (2009) · Zbl 1194.05077 |
| [10] | Balakrishnan, R., The energy of a graph, Lin Algebra Appl, 387, 287-295 (2004) · Zbl 1041.05046 |
| [11] | Gutman, I.; Shao, JY., The energy change of weighted graphs, Lin Algebra Appl, 435, 2425-2431 (2011) · Zbl 1222.05158 |
| [12] | Heuberger, C.; Wagner, S., On a class of extremal trees for various indices, MATCH Commun Math Comput Chem, 62, 437-464 (2009) · Zbl 1274.05094 |
| [13] | Li, S.; Li, X.; Zhu, Z., On tricyclic graphs with minimal energy, MATCH Commun Math Comput Chem, 59, 397-419 (2008) · Zbl 1164.05041 |
| [14] | Li, X.; Zhang, J.; Zhou, B., On unicyclic conjugated molecules with minimal energies, J Math Chem, 42, 729-740 (2007) · Zbl 1217.05145 |
| [15] | Li, X.; Zhang, J.; Wang, L., On bipartite graphs with minimal energy, Discrete Appl Math, 157, 869-873 (2009) · Zbl 1226.05161 |
| [16] | Li, X.; Zhang, J., On bicyclic graphs with maximal energy, Lin Algebra Appl, 427, 87-98 (2007) · Zbl 1184.05068 |
| [17] | Li, F.; Zhou, B., Minimal energy of bipartite unicyclic graphs of a given bipartition, MATCH Commun Math Comput Chem, 54, 379-388 (2005) · Zbl 1081.05066 |
| [18] | Caporossi, G.; Cvetković, D.; Gutman, I., Variable neighborhood search for extremal graphs. 2. Finding graphs with external energy, J Chem Inf Comput Sci, 39, 984-996 (1999) |
| [19] | Hou, Y., Unicyclic graphs with minimal energy, J Math Chem, 29, 163-168 (2001) · Zbl 0977.05085 |
| [20] | Hou, Y., Bicyclic graphs with minimum energy, Linear Multilinear Algebra, 49, 347-354 (2001) · Zbl 0996.05092 |
| [21] | Zhang, J.; Zhou, B., On bicyclic graphs with minimal energies, J Math Chem, 37, 4, 423-431 (2005) · Zbl 1066.05092 |
| [22] | Zhang, J.; Kan, H., On the minimal energy of graphs, Lin Algebra Appl, 453, 141-153 (2014) · Zbl 1314.05123 |
| [23] | Li, S.; Li, X., On tetracyclic graphs with minimal energy, MATCH Commun Math Comput Chem, 60, 395-414 (2008) · Zbl 1199.05230 |
| [24] | Cvetković, D.; Doob, M.; Sachs, H., Spectra of graphs (1980), New York: Academic Press, New York · Zbl 0458.05042 |
| [25] | Cvetković, D.; Rowlinson, P.; Simić, S., An introduction to the theory of graph spectra (2009), Cambridge: Cambridge University Press, Cambridge |
| [26] | Day, J.; So, W., Graph energy change due to edge deletion, Lin Algebra Appl, 428, 2070-2078 (2008) · Zbl 1136.05037 |
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.
