zbMATH — the first resource for mathematics

On the sum of the \(k\) largest eigenvalues of graphs and maximal energy of bipartite graphs. (English) Zbl 1411.05156
Summary: Let \(G\) be a graph of order \(n\). Also let \(\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n\) be the eigenvalues of graph \(G\). In this paper, we present the following upper bound on the sum of the \(k\) \((\leq n)\) largest eigenvalues of \(G\) in terms of the order \(n\) and negative inertia \(\theta\) (the number of negative eigenvalues): \(\sum_{i = 1}^k \lambda_i \leq \frac{n}{2(\theta + 1)}(\theta + \sqrt{\theta(k \theta + k - 1)})\) with equality holding if and only if \(G \cong n K_1\) or \(G \cong \overline{p K}_t\)\((n = p t, p \geq 2)\) with \(k = 1\) (where \(\overline{p K}_t\) is the complete \(p\)-partite graph of \(p\) \(t\) vertices with all partition sets having size \(t\)). Moreover, we obtain a sharp upper bound on the energy of bipartite graphs with given order \(n\) and rank \(r\). We also propose an open problem as follows: Characterize all connected \(d\)-regular bipartite graphs of order \(n\) with 5 distinct eigenvalues and rank \(r = \frac{2 n^2}{(4 d - n)^2}\), where \(d > \frac{n}{4}\). Finally we give a partial solution to this problem.

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: DOI
[1] Bapat, R. B., Graphs and Matrices, Universitext, (2014), Springer/Hindustan Book Agency: Springer/Hindustan Book Agency London/New Delhi · Zbl 1288.05152
[2] Brouwer, A. E.; Haemers, W. H., Spectra of Graphs, (2011), Springer
[3] 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)
[4] Collatz, L.; Sinogowitz, U., Spektren endlicher grafen, Abh. Math. Semin. Univ. Hambg., 21, 63-77, (1957) · Zbl 0077.36704
[5] Cvetković, D.; Doob, M.; Sachs, H., Spectra of GraphsTheory and Applications, (1980), Academic Press: Academic Press New York
[6] Cvetković, D.; Rowlinson, P.; Simić, S., An Introduction to the Theory of Graph Spectra, (2010), Cambridge University Press: Cambridge University Press New York · Zbl 1211.05002
[7] Das, K. C.; Kumar, P., Some new bounds on the spectral radius of graphs, Discrete Math., 281, 149-161, (2004) · Zbl 1042.05060
[8] Das, K. C.; Mojallal, S. A., On energy and Laplacian energy of graphs, Electron. J. Linear Algebra, 31, 167-186, (2016) · Zbl 1339.05225
[9] Das, K. C.; Mojallal, S. A.; Gutman, I., On energy and Laplacian energy of bipartite graphs, Appl. Math. Comput., 273, 759-766, (2016) · Zbl 1410.05124
[10] Das, K. C.; Mojallal, S. A.; Gutman, I., On energy of line graphs, Linear Algebra Appl., 499, 79-89, (2016) · Zbl 1334.05079
[11] Ebrahimi, J. B.; Mohar, B.; Nikiforov, V.; Ahmady, A. S., On the sum of two largest eigenvalues of a symmetric matrix, Linear Algebra Appl., 429, 2781-2787, (2008) · Zbl 1148.05047
[12] Gernert, D., Private communication, see also
[13] Godsil, C.; Royle, G., Algebraic Graph Theory, (2004), Springer-Verlag: Springer-Verlag New York
[14] Grone, R.; Merris, R., The Laplacian spectrum of a graph II, SIAM J. Discrete Math., 7, 221-229, (1994) · Zbl 0795.05092
[15] Huo, B.; Li, X.; Shi, Y., Complete solution to a conjecture on the maximal energy of unicyclic graphs, European J. Combin., 32, 662-673, (2011) · Zbl 1235.05088
[16] Jacobs, D. P.; Trevisan, V.; Tura, F., Eigenvalues and energy in threshold graphs, Linear Algebra Appl., 465, 412-425, (2015) · Zbl 1302.05103
[17] Koolen, J. H.; Moulton, V., Maximal energy bipartite graphs, Graphs Combin., 19, 131-135, (2003) · Zbl 1015.05043
[18] Li, X.; Shi, Y.; Gutman, I., Graph Energy, (2012), Springer: Springer New York
[19] Merris, R., Laplacian matrices of graphs: a survey, Linear Algebra Appl., 197, 198, 143-176, (1994) · Zbl 0802.05053
[20] Mohar, B., On the sum of k largest eigenvalues of graphs and symmetric matrices, J. Combin. Theory Ser. B, 99, 306-313, (2009) · Zbl 1217.05151
[21] Nikiforov, V., Beyond graph energy: norms of graphs and matrices, Linear Algebra Appl., 506, 82-138, (2016) · Zbl 1344.05089
[22] Nikiforov, V., Linear combinations of graph eigenvalues, Electron. J. Linear Algebra, 15, 329-336, (2006) · Zbl 1142.05343
[23] Nikiforov, V., On the sum of k largest singular values of graphs and matrices, Linear Algebra Appl., 435, 2394-2401, (2011) · Zbl 1222.05172
[24] Petrović, M. M., The spectrum of infinite complete multipartite graphs, Publ. Inst. Math. (Beograd) (N.S.), 31, 45, 169-176, (1982) · Zbl 0515.05047
[25] Stein, W. A., Sage Mathematics Software (Version 6.8), The Sage Development Team, (2015)
[26] Stevanović, D.; Gutman, I.; Rehman, M. U., On spectral radius and energy of complete multipartite graphs, Ars Math. Contemp., 9, 109-113, (2015) · Zbl 1329.05201
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.