Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
sum of eigenvalues; graph energy; random matrix
sum of eigenvalues; graph energy; random matrix
Summary:
Let $G$ be a graph on $n$ vertices and let $\lambda _{1}\geq \lambda _{2}\geq \ldots \geq \lambda _{n}$ be the eigenvalues of its adjacency matrix. For random graphs we investigate the sum of eigenvalues $s_{k}=\sum _{i=1}^{k}\lambda _{i}$, for $1\leq k\leq n$, and show that a typical graph has $s_{k}\leq (e(G)+k^{2})/(0.99n)^{1/2}$, where $e(G)$ is the number of edges of $G$. We also show bounds for the sum of eigenvalues within a given range in terms of the number of edges. The approach for the proofs was first used in Rocha (2020) to bound the partial sum of eigenvalues of the Laplacian matrix.
References:
[1] Das, K. C., Mojallal, S. A., Sun, S.: On the sum of the $k$ largest eigenvalues of graphs and maximal energy of bipartite graphs. Linear Algebra Appl. 569 (2019), 175-194. DOI 10.1016/j.laa.2019.01.016 | MR 3904318 | Zbl 1411.05156
[2] Füredi, Z., Komlós, J.: The eigenvalues of random symmetric matrices. Combinatorica 1 (1981), 233-241. DOI 10.1007/BF02579329 | MR 0637828 | Zbl 0494.15010
[3] Graovac, A., Gotman, I., Trinajstić, N.: Topological Approach to the Chemistry of Conjugated Molecules. Lecture Notes in Chemistry 4. Springer, Berlin (1977). DOI 10.1007/978-3-642-93069-0 | Zbl 0385.05032
[4] Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58 (1963), 13-30. DOI 10.2307/2282952 | MR 0144363 | Zbl 0127.10602
[5] Li, X., Shi, Y., Gutman, I.: Graph Energy. Springer, New York (2012). DOI 10.1007/978-1-4614-4220-2 | MR 2953171 | Zbl 1262.05100
[6] Mohar, B.: On the sum of $k$ largest eigenvalues of graphs and symmetric matrices. J. Comb. Theory, Ser. B 99 (2009), 306-313. DOI 10.1016/j.jctb.2008.07.001 | MR 2482950 | Zbl 1217.05151
[7] Nikiforov, V.: The energy of graphs and matrices. J. Math. Anal. Appl. 326 (2007), 1472-1475. DOI 10.1016/j.jmaa.2006.03.072 | MR 2280998 | Zbl 1113.15016
[8] Nikiforov, V.: On the sum of $k$ largest singular values of graphs and matrices. Linear Algebra Appl. 435 (2011), 2394-2401. DOI 10.1016/j.laa.2010.08.014 | MR 2811124 | Zbl 1222.05172
[9] Nikiforov, V.: Beyond graph energy: norms of graphs and matrices. Linear Algebra Appl. 506 (2016), 82-138. DOI 10.1016/j.laa.2016.05.011 | MR 3530671 | Zbl 1344.05089
[10] Rocha, I.: Brouwer's conjecture holds asymptotically almost surely. Linear Algebra Appl. 597 (2020), 198-205. DOI 10.1016/j.laa.2020.03.019 | MR 4082064 | Zbl 07190773
[11] Wigner, E. P.: On the distribution of the roots of certain symmetric matrices. Ann. Math. (2) 67 (1958), 325-327. DOI 10.2307/1970008 | MR 0095527 | Zbl 0085.13203
Search
Partner of
