×

zbMATH — the first resource for mathematics

Beyond graph energy: norms of graphs and matrices. (English) Zbl 1344.05089
Summary: In 1978, I. Gutman [Ber. Math.-Stat. Sekt. Forschungszent. Graz 103, 22 S. (1978; Zbl 0402.05040)] introduced the energy of a graph as the sum of the absolute values of graph eigenvalues, and ever since then graph energy has been intensively studied.
Since graph energy is the trace norm of the adjacency matrix, matrix norms provide a natural background for its study. Thus, this paper surveys research on matrix norms that aims to expand and advance the study of graph energy. The focus is exclusively on the Ky Fan and the Schatten norms, both generalizing and enriching the trace norm. As it turns out, the study of extremal properties of these norms leads to numerous analytic problems with deep roots in combinatorics.
The survey brings to the fore the exceptional role of Hadamard matrices, conference matrices, and conference graphs in matrix norms. In addition, a vast new matrix class is studied, a relaxation of symmetric Hadamard matrices.
The survey presents solutions to just a fraction of a larger body of similar problems bonding analysis to combinatorics. Thus, open problems and questions are raised to outline topics for further investigation.

MSC:
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adiga, C.; Balakrishnan, R.; So, Wasin, The skew energy of a digraph, Linear Algebra Appl., 432, 1825-1835, (2010) · Zbl 1217.05131
[2] Akbari, S.; Ghorbani, E.; Oboudi, M. R., Edge addition, singular values, and energy of graphs and matrices, Linear Algebra Appl., 430, 2192-2199, (2009) · Zbl 1194.05077
[3] Aouchiche, M.; Hansen, P., A survey of Nordhaus-Gaddum type relations, Discrete Appl. Math., 161, 466-546, (2013) · Zbl 1259.05083
[4] Beth, T.; Jungnickel, D.; Lenz, H., Design theory, vol. 1, (1999), Cambridge University Press Cambridge
[5] Božin, V.; Mateljević, M., Energy of graphs and orthogonal matrices, (Gautschi, W.; Mastroianni, G.; Rassias, Th. M., Approximation and Computation: In Honor of Gradimir V. Milovanovic, (2011), Springer), 87-96 · Zbl 1293.05209
[6] Caporossi, G.; Cvetković, D.; Gutman, I.; Hansen, P., Variable neighborhood search for extremal graphs. 2. finding graphs with extremal energy, J. Chem. Inf. Comput. Sci., 39, 984-996, (1999)
[7] Csikvári, P., On a poset of trees, Combinatorica, 30, 125-137, (2010) · Zbl 1224.05093
[8] Cvetković, D., Chromatic number and the spectrum of a graph, Publ. Inst. Math. (Beograd), 14, 28, 25-38, (1972) · Zbl 0271.05111
[9] Day, J.; So, W., Singular value inequality and graph energy change, Electron. J. Linear Algebra, 16, 291-299, (2007) · Zbl 1146.15008
[10] Day, J.; So, W., Graph energy change due to edge deletion, Linear Algebra Appl., 428, 2070-2078, (2008) · Zbl 1136.05037
[11] Gregory, D.; Hershkowitz, D.; Kirkland, S., The spread of the spectrum of a graph, Linear Algebra Appl., 332, 23-35, (2001) · Zbl 0978.05049
[12] Godsil, C.; Royle, G., Algebraic graph theory, (2001), Springer, x+464 pp · Zbl 0968.05002
[13] Gutman, I., The energy of a graph, Ber. Math.-Stat. Sekt. Forschungszent. Graz., 103, 1-22, (1978)
[14] Gutman, I.; Li, X.; Shi, Y., Graph energy, (2012), Springer New York, 266 pp
[15] Gutman, I.; Kiani, D.; Mirzakhah, M., On incidence energy of graphs, MATCH Commun. Math. Comput. Chem., 62, 573-580, (2009) · Zbl 1199.05221
[16] Gutman, I.; Kiani, D.; Mirzakhah, M.; Zhou, B., On incidence energy of a graph, Linear Algebra Appl., 431, 1223-1233, (2009) · Zbl 1175.05084
[17] Jooyandeh, M.; Kiani, D.; Mirzakhah, M., Incidence energy of a graph, MATCH Commun. Math. Comput. Chem., 62, 561-572, (2009) · Zbl 1274.05295
[18] Haemers, W., Strongly regular graphs with maximal energy, Linear Algebra Appl., 429, 2719-2723, (2008) · Zbl 1152.05060
[19] Hoffman, A. J., On eigenvalues and colorings of graphs, (Graph Theory and Its Applications, (1970), Academic Press New York), 79-91 · Zbl 0227.05105
[20] Horn, R.; Johnson, C., Matrix analysis, (2012), Cambridge University Press Cambridge, xviii+643 pp
[21] Kharaghani, H., New classes of weighing matrices, Ars Combin., 19, 69-72, (1985) · Zbl 0584.05015
[22] Kharaghani, H.; Tayfeh-Rezaie, B., On the energy of \((0, 1)\)-matrices, Linear Algebra Appl., 429, 2046-2051, (2008) · Zbl 1144.05320
[23] Koolen, J. H.; Moulton, V., Maximal energy graphs, Adv. in Appl. Math., 26, 47-52, (2001) · Zbl 0976.05040
[24] Koolen, J. H.; Moulton, V., Maximal energy bipartite graphs, Graphs Combin., 19, 131-135, (2003) · Zbl 1015.05043
[25] de Launey, W., On the asymptotic existence of partial complex Hadamard matrices and related combinatorial objects, Discrete Appl. Math., 102, 37-45, (2000) · Zbl 0961.05010
[26] Mantel, W., Problem 28, Wiskundige Opgaven, 10, 60-61, (1907)
[27] McClelland, B., Properties of the latent roots of a matrix: the estimation of π-electron energies, J. Chem. Phys., 54, 640-643, (1971)
[28] Nikiforov, V., Linear combinations of graph eigenvalues, Electron. J. Linear Algebra, 15, 329-336, (2006) · Zbl 1142.05343
[29] Nikiforov, V., Walks and the spectral radius of graphs, Linear Algebra Appl., 418, 257-268, (2006) · Zbl 1106.05065
[30] Nikiforov, V., Revisiting Schur’s bound on the largest singular value, preprint available at
[31] Nikiforov, V., The energy of graphs and matrices, J. Math. Anal. Appl., 326, 1472-1475, (2007) · Zbl 1113.15016
[32] Nikiforov, V., Graphs and matrices with maximal energy, J. Math. Anal. Appl., 327, 735-738, (2007) · Zbl 1112.05067
[33] Nikiforov, V., On the sum of k largest singular values of graphs and matrices, Linear Algebra Appl., 435, 2394-2401, (2011) · Zbl 1222.05172
[34] Nikiforov, V., Extremal norms of graphs and matrices, J. Math. Sci., 182, 164-174, (2012) · Zbl 1254.05109
[35] Nikiforov, V., The trace norm of r-partite graphs and matrices, C. R. Math. Acad. Sci. Paris, Ser. I, 353, 471-475, (2015), extended version in · Zbl 1314.05118
[36] Nikiforov, V., Extrema of graph eigenvalues, Linear Algebra Appl., 482, 158-190, (2015) · Zbl 1330.05105
[37] Nikiforov, V., Energy of matrices and norms of graphs, (Gutman, I.; Li, X., Energies of Graphs - Theory and Applications, Math. Chem. Monogr., vol. 17, (2016), University of Kragujevac and Faculty of Science Kragujevac), 5-48 · Zbl 1344.05089
[38] Nikiforov, V.; Yuan, X. Y., Maximum norms of graphs and matrices, and their complements, Linear Algebra Appl., 439, 1538-1549, (2013) · Zbl 1282.05146
[39] Nordhaus, E. A.; Gaddum, J., On complementary graphs, Amer. Math. Monthly, 63, 175-177, (1956) · Zbl 0070.18503
[40] de la Peña, J. A.; Mendoza, L.; Rada, J., Comparing moments and π-electron energy of benzenoid molecules, Discrete Math., 302, 77-84, (2005) · Zbl 1076.05078
[41] Rada, J.; Tineo, A., Upper and lower bounds for the energy of bipartite graphs, J. Math. Anal. Appl., 289, 446-455, (2004) · Zbl 1034.05034
[42] So, W.; Robbiano, M.; de Abreu, N.; Gutman, I., Applications of a theorem by Ky Fan in the theory of graph energy, Linear Algebra Appl., 432, 2163-2169, (2010) · Zbl 1218.05100
[43] Stanley, R., A bound on the spectral radius of graphs with e edges, Linear Algebra Appl., 87, 267-269, (1987) · Zbl 0617.05045
[44] Turán, P., On an extremal problem in graph theory, Mat. Fiz. Lapok, 48, 436-452, (1941), (in Hungarian)
[45] Zhang, J.; Li, J., New results on the incidence energy of graphs, MATCH Commun. Math. Comput. Chem., 68, 777-803, (2012) · Zbl 1289.05325
[46] Zhang, J.; Kan, H.; Liu, X. D., Graphs with extremal incidence energy, Filomat, 29, 1251-1258, (2015) · Zbl 1464.05210
[47] Zhou, B.; Gutman, I., Nordhaus-Gaddum-type relations for the energy and Laplacian energy of graphs, Bull. Cl. Sci. Math. Nat. Sci. Math., 32, 1-11, (2007) · Zbl 1250.05074
[48] Zhou, B., More upper bounds for the incidence energy, MATCH Commun. Math. Comput. Chem., 64, 123-128, (2010) · Zbl 1265.05436
[49] Zhou, B., On the energy of a graph, Kragujev. J. Sci., 26, 5-12, (2004)
[50] Zhou, B.; Gutman, I.; de la Peña, J. A.; Rada, J.; Mendoza, L., On the spectral moments and energy of graphs, MATCH Commun. Math. Comput. Chem., 57, 183-191, (2007) · Zbl 1274.05311
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.