Partial sum of eigenvalues of random graphs
Applications of Mathematics (2020)
- Volume: 65, Issue: 5, page 609-618
- ISSN: 0862-7940
Access Full Article
top
Abstract
topHow to cite
topRocha, Israel. "Partial sum of eigenvalues of random graphs." Applications of Mathematics 65.5 (2020): 609-618. <http://eudml.org/doc/296959>.
@article{Rocha2020,
abstract = {Let $G$ be a graph on $n$ vertices and let $\lambda _\{1\}\ge \lambda _\{2\}\ge \ldots \ge \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\le k\le n$, and show that a typical graph has $s_\{k\}\le (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.},
author = {Rocha, Israel},
journal = {Applications of Mathematics},
keywords = {sum of eigenvalues; graph energy; random matrix},
language = {eng},
number = {5},
pages = {609-618},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Partial sum of eigenvalues of random graphs},
url = {http://eudml.org/doc/296959},
volume = {65},
year = {2020},
}
TY - JOUR
AU - Rocha, Israel
TI - Partial sum of eigenvalues of random graphs
JO - Applications of Mathematics
PY - 2020
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 65
IS - 5
SP - 609
EP - 618
AB - Let $G$ be a graph on $n$ vertices and let $\lambda _{1}\ge \lambda _{2}\ge \ldots \ge \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\le k\le n$, and show that a typical graph has $s_{k}\le (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.
LA - eng
KW - sum of eigenvalues; graph energy; random matrix
UR - http://eudml.org/doc/296959
ER -
References
top- Das, K. C., Mojallal, S. A., Sun, S., 10.1016/j.laa.2019.01.016, Linear Algebra Appl. 569 (2019), 175-194. (2019) Zbl1411.05156MR3904318DOI10.1016/j.laa.2019.01.016
- Füredi, Z., Komlós, J., 10.1007/BF02579329, Combinatorica 1 (1981), 233-241. (1981) Zbl0494.15010MR0637828DOI10.1007/BF02579329
- Graovac, A., Gotman, I., Trinajstić, N., 10.1007/978-3-642-93069-0, Lecture Notes in Chemistry 4. Springer, Berlin (1977). (1977) Zbl0385.05032DOI10.1007/978-3-642-93069-0
- Hoeffding, W., 10.2307/2282952, J. Am. Stat. Assoc. 58 (1963), 13-30. (1963) Zbl0127.10602MR0144363DOI10.2307/2282952
- Li, X., Shi, Y., Gutman, I., 10.1007/978-1-4614-4220-2, Springer, New York (2012). (2012) Zbl1262.05100MR2953171DOI10.1007/978-1-4614-4220-2
- Mohar, B., 10.1016/j.jctb.2008.07.001, J. Comb. Theory, Ser. B 99 (2009), 306-313. (2009) Zbl1217.05151MR2482950DOI10.1016/j.jctb.2008.07.001
- Nikiforov, V., 10.1016/j.jmaa.2006.03.072, J. Math. Anal. Appl. 326 (2007), 1472-1475. (2007) Zbl1113.15016MR2280998DOI10.1016/j.jmaa.2006.03.072
- Nikiforov, V., 10.1016/j.laa.2010.08.014, Linear Algebra Appl. 435 (2011), 2394-2401. (2011) Zbl1222.05172MR2811124DOI10.1016/j.laa.2010.08.014
- Nikiforov, V., 10.1016/j.laa.2016.05.011, Linear Algebra Appl. 506 (2016), 82-138. (2016) Zbl1344.05089MR3530671DOI10.1016/j.laa.2016.05.011
- Rocha, I., 10.1016/j.laa.2020.03.019, Linear Algebra Appl. 597 (2020), 198-205. (2020) Zbl07190773MR4082064DOI10.1016/j.laa.2020.03.019
- Wigner, E. P., 10.2307/1970008, Ann. Math. (2) 67 (1958), 325-327. (1958) Zbl0085.13203MR0095527DOI10.2307/1970008
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.