Institute of Mathematics

of the Czech Academy of Sciences
 
 
 
 

Applications of Mathematics, Vol. 65, No. 5, pp. 609-618, 2020

Partial sum of eigenvalues of random graphs

Israel Rocha

Received December 10, 2019.   Published online September 4, 2020.
Abstract:  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.
Keywords:  sum of eigenvalues; graph energy; random matrix
Classification MSC:  05C50, 15A18
DOI:  10.21136/AM.2020.0352-19
PDF available at:  Springer   Institute of Mathematics CAS   Digital Mathematics Library
References:
[1] K. C. Das, S. A. Mojallal, S. Sun: 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] Z. Füredi, J. Komlós: The eigenvalues of random symmetric matrices. Combinatorica 1 (1981), 233-241. DOI 10.1007/BF02579329 | MR 0637828 | Zbl 0494.15010
[3] A. Graovac, I. Gotman, N. Trinajstić: 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] W. Hoeffding: 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] X. Li, Y. Shi, I. Gutman: Graph Energy. Springer, New York (2012). DOI 10.1007/978-1-4614-4220-2 | MR 2953171 | Zbl 1262.05100
[6] B. Mohar: 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] V. Nikiforov: 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] V. Nikiforov: 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] V. Nikiforov: 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] I. Rocha: 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] E. P. Wigner: 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
Affiliations:   Israel Rocha, The Czech Academy of Sciences, Institute of Computer Science, Pod Vodárenskou věží 2, 182 07 Praha 8, Czech Republic, e-mail: israelrocha@gmail.com
Springer subscribers can access the papers on Springer website.
[List of online first articles] [Contents of Applications of Mathematics] [Full text of the older issues of Applications of Mathematics at DML-CZ]
© Institute of Mathematics CAS, 2024



 
PDF available at:


Springer
for subscribers
···

Institute of Mathematics CAS
free access
···

Digital Mathematics Library
free access