# 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.

##### MSC:
 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
##### Keywords:
eigenvalues; eigenvalue sum; graph energy; inertia; rank
SageMath
Full Text:
##### References:
  Bapat, R. B., Graphs and Matrices, Universitext, (2014), Springer/Hindustan Book Agency: Springer/Hindustan Book Agency London/New Delhi · Zbl 1288.05152  Brouwer, A. E.; Haemers, W. H., Spectra of Graphs, (2011), Springer  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)  Collatz, L.; Sinogowitz, U., Spektren endlicher grafen, Abh. Math. Semin. Univ. Hambg., 21, 63-77, (1957) · Zbl 0077.36704  Cvetković, D.; Doob, M.; Sachs, H., Spectra of GraphsTheory and Applications, (1980), Academic Press: Academic Press New York  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  Das, K. C.; Kumar, P., Some new bounds on the spectral radius of graphs, Discrete Math., 281, 149-161, (2004) · Zbl 1042.05060  Das, K. C.; Mojallal, S. A., On energy and Laplacian energy of graphs, Electron. J. Linear Algebra, 31, 167-186, (2016) · Zbl 1339.05225  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  Das, K. C.; Mojallal, S. A.; Gutman, I., On energy of line graphs, Linear Algebra Appl., 499, 79-89, (2016) · Zbl 1334.05079  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  Gernert, D., Private communication, see also  Godsil, C.; Royle, G., Algebraic Graph Theory, (2004), Springer-Verlag: Springer-Verlag New York  Grone, R.; Merris, R., The Laplacian spectrum of a graph II, SIAM J. Discrete Math., 7, 221-229, (1994) · Zbl 0795.05092  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  Jacobs, D. P.; Trevisan, V.; Tura, F., Eigenvalues and energy in threshold graphs, Linear Algebra Appl., 465, 412-425, (2015) · Zbl 1302.05103  Koolen, J. H.; Moulton, V., Maximal energy bipartite graphs, Graphs Combin., 19, 131-135, (2003) · Zbl 1015.05043  Li, X.; Shi, Y.; Gutman, I., Graph Energy, (2012), Springer: Springer New York  Merris, R., Laplacian matrices of graphs: a survey, Linear Algebra Appl., 197, 198, 143-176, (1994) · Zbl 0802.05053  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  Nikiforov, V., Beyond graph energy: norms of graphs and matrices, Linear Algebra Appl., 506, 82-138, (2016) · Zbl 1344.05089  Nikiforov, V., Linear combinations of graph eigenvalues, Electron. J. Linear Algebra, 15, 329-336, (2006) · Zbl 1142.05343  Nikiforov, V., On the sum of k largest singular values of graphs and matrices, Linear Algebra Appl., 435, 2394-2401, (2011) · Zbl 1222.05172  Petrović, M. M., The spectrum of infinite complete multipartite graphs, Publ. Inst. Math. (Beograd) (N.S.), 31, 45, 169-176, (1982) · Zbl 0515.05047  Stein, W. A., Sage Mathematics Software (Version 6.8), The Sage Development Team, (2015)  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.