Geodesic
Turán’s Theorem Implies Stanley’s Bound
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 2, pp. 601-605.

Voir la notice de l'article provenant de la source Library of Science

Let G be a graph with m edges and let ρ be the largest eigenvalue of its adjacency matrix. It is shown that ρ≤√(2(1-⌊1/2+√(2m+1/4)⌋^-1)m,) improving the well-known bound of Stanley. Moreover, writing ω for the clique number of G and W_k for the number of its walks on k vertices, it is shown that the sequence {((1-1/ω)W_2^k)^1/2^k}_k=1^∞ is nonincreasing and converges to ρ.
Keywords: graph spectral radius, Stanley’s bound, Turán’s theorem, clique number, Motzkin-Straus’s inequality, walks 
@article{DMGT_2020_40_2_a14,
     author = {Nikiforov, V.},
     title = {Tur\'an{\textquoteright}s {Theorem} {Implies} {Stanley{\textquoteright}s} {Bound}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {601--605},
     publisher = {mathdoc},
     volume = {40},
     number = {2},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a14/}
}
TY  - JOUR
AU  - Nikiforov, V.
TI  - Turán’s Theorem Implies Stanley’s Bound
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 601
EP  - 605
VL  - 40
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a14/
LA  - en
ID  - DMGT_2020_40_2_a14
ER  - 
%0 Journal Article
%A Nikiforov, V.
%T Turán’s Theorem Implies Stanley’s Bound
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 601-605
%V 40
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a14/
%G en
%F DMGT_2020_40_2_a14
Nikiforov, V. Turán’s Theorem Implies Stanley’s Bound. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 2, pp. 601-605. http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a14/

[1] R. Brualdi and A. Hoffman, On the spectral radius of (0, 1) matrices, Linear Algebra Appl. 65 (1985) 133–146. doi:10.1016/0024-3795(85)90092-8

[2] D. Cvetković, Graphs and their spectra, Ph.D. Thesis, Univ. Beograd. Publ. Elektrotehn. Fak., Ser. Mat. Fiz. 354–356 (1971) 1–50.

[3] C. Edwards and C. Elphick, Lower bounds for the clique and the chromatic number of a graph, Discrete Appl. Math. 5 (1983) 51–64. doi:10.1016/0166-218X(83)90015-X

[4] S. Friedland, The maximal eigenvalue of 0 − 1 matrices with prescribed number of ones, Linear Algebra Appl. 69 (1985) 33–69. doi:10.1016/0024-3795(85)90068-0

[5] S. Friedland, Bounds on the spectral radius of graphs with e edges, Linear Algebra Appl. 101 (1988) 88–86. doi:10.1016/0024-3795(88)90144-9

[6] T. Motzkin and E. Straus, Maxima for graphs and a new proof of a theorem of Turán, Canad. J. Math. 17 (1965) 533–540. doi:10.4153/CJM-1965-053-6

[7] V. Nikiforov, Some inequalities for the largest eigenvalue of a graph, Combin. Probab. Comput. 11 (2002) 179–189. doi:10.1017/S0963548301004928

[8] V. Nikiforov, Walks and the spectral radius of graphs, Linear Algebra Appl. 418 (2006) 257–268. doi:10.1016/j.laa.2006.02.003

[9] E. Nosal, Eigenvalues of Graphs (Master’s Thesis, University of Calgary, 1970).

[10] P. Rowlinson, On the maximal index of graphs with a prescribed number of edges, Linear Algebra Appl. 110 (1988) 43–53. doi:10.1016/0024-3795(83)90131-3

[11] A.F. Sidorenko, The maximal number of edges in a homogeneous hypergraph containing no prohibited subgraphs, Mat. Zametki 41 (1987) 433–455, (English translation in Math. Notes Acad. Sci. USRR 41 (1987) 247–259). doi:10.1007/BF01158259

[12] R. Stanley, A bound on the spectral radius of graphs with e edges, Linear Algebra Appl. 87 (1987) 267–269. doi:10.1016/0024-3795(87)90172-8

[13] P. Turán, On an extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941) 436–452, in Hungarian.

[14] H.S. Wilf, Spectral bounds for the clique and independence numbers of graphs, J. Combin. Theory Ser. B 40 (1986) 113–117. doi:10.1016/0095-8956(86)90069-9