Geodesic
Graphs with All But Two Eigenvalues In [−2, 0]
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 2, pp. 379-391.

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

The eigenvalues of a graph are those of its adjacency matrix. Recently, Cioabă, Haemers and Vermette characterized all graphs with all but two eigenvalues equal to −2 and 0. In this article, we extend their result by characterizing explicitly all graphs with all but two eigenvalues in the interval [−2, 0]. Also, we determine among them those that are determined by their spectrum.
Keywords: graph spectrum, complete multipartite graph, graph determined by its spectrum 
@article{DMGT_2020_40_2_a1,
     author = {Abreu, Nair and Alencar, Jorge and Brondani, Andr\'e and de Lima, Leonardo and Oliveira, Carla},
     title = {Graphs with {All} {But} {Two} {Eigenvalues} {In} [\ensuremath{-}2, 0]},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {379--391},
     publisher = {mathdoc},
     volume = {40},
     number = {2},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a1/}
}
TY  - JOUR
AU  - Abreu, Nair
AU  - Alencar, Jorge
AU  - Brondani, André
AU  - de Lima, Leonardo
AU  - Oliveira, Carla
TI  - Graphs with All But Two Eigenvalues In [−2, 0]
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 379
EP  - 391
VL  - 40
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a1/
LA  - en
ID  - DMGT_2020_40_2_a1
ER  - 
%0 Journal Article
%A Abreu, Nair
%A Alencar, Jorge
%A Brondani, André
%A de Lima, Leonardo
%A Oliveira, Carla
%T Graphs with All But Two Eigenvalues In [−2, 0]
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 379-391
%V 40
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a1/
%G en
%F DMGT_2020_40_2_a1
Abreu, Nair; Alencar, Jorge; Brondani, André; de Lima, Leonardo; Oliveira, Carla. Graphs with All But Two Eigenvalues In [−2, 0]. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 2, pp. 379-391. http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a1/

[1] A.E. Brouwer and W.H. Haemers, Spectra of Graphs (Springer, New York, 2012). doi:10.1007/978-1-4614-1939-6

[2] D. Cao and H. Yuan, Graphs characterized by the second eigenvalue, J. Graph Theory 17 (1993) 325–331. doi:10.1002/jgt.3190170307

[3] S.M. Cioabă, W.H. Haemers and J.R. Vermette, The graphs with all but two eigenvalues equal to − 2 or 0, Des. Codes Cryptogr. 84 (2017) 153–163. doi:10.1007/s10623-016-0241-4

[4] S.M. Cioabă, W.H. Haemers, J.R. Vermette and W. Wong, The graphs with all but two eigenvalues equal to ± 1, J. Algebraic Combin. 41 (2015) 887–897. doi:10.1007/s10801-014-0557-y

[5] D. Cvetković, On graphs whose second largest eigenvalue does not exceed 1, Publ. Inst. Math. (Beograd) (N.S.) 31(45) (1982) 15–20.

[6] D. Cvetković, M. Doob and H. Sachs, Spectra of Graphs: Theory and Applications, 3rd Edition (Johann Ambrosius Barth Verlag, Heidelberg-Leipzig, 1995).

[7] D. Cvetković and S. Simić, On graphs whose second largest eigenvalue does not exceed (\(\sqrt{5}−1)/2\), Discrete Math. 138 (1995) 213–227. doi:10.1016/0012-365X(94)00204-V

[8] D. Cvetković, M. Doob and H. Sachs, Spectra of Graphs: Theory and Application (Academic Press, New York, 1980).

[9] L.S. de Lima, A. Mohammadian and C.S. Oliveira, The non-bipartite graphs with all but two eigenvalues in [ − 1, 1], Linear Multilinear Algebra 65 (2017) 526–544. doi:10.1080/03081087.2016.1194802

[10] F. Esser and F. Harary, On the spectrum of a complete multipartite graph, European J. Combin. 1 (1980) 211–218. doi:10.1016/S0195-6698(80)80004-7

[11] H. Ma and H. Ren, On the spectral characterization of the union of complete multipartite graph and some isolated vertices, Discrete Math. 310 (2010) 3648–3652. doi:10.1016/j.disc.2010.09.004

[12] M. Petrović, On graphs whose second largest eigenvalue does not exceed \(\sqrt{2}− 1\), Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. 4 (1993) 70–75.

[13] S. Simić, Complementary pairs of graphs with the second largest eigenvalue not exceeding (\(\sqrt{5}−1)/2\), Publ. Inst. Math. (Beograd) (N.S.) 57(71) (1995) 179–188.

[14] S. Simić, Some notes on graphs whose second largest eigenvalue is less than (\(\sqrt{5}−1)/2\), Linear Multilinear Algebra 39 (1995) 59–71. doi:10.1080/03081089508818380

[15] S.K. Simić, M. Anđelić, C.M. da Fonseca and D.Živković, Notes on the second largest eigenvalue of a graph, Linear Algebra Appl. 465 (2015) 262–274. doi:10.1016/j.laa.2014.09.032

[16] S.K. Simić, D.Živković, M. Anđelić and C.M. da Fonseca, Reflexive line graphs of trees, J. Algebraic Combin. 43 (2016) 447–464. doi:10.1007/s10801-015-0640-z

[17] J.H. Smith, Some properties of the spectrum of a graph, in: Combin. Struct. Appl., (Gordon and Breach, New York, 1970) 403–406.

[18] Z. Stanić, Some graphs whose second largest eigenvalue does not exceed \(\sqrt{2}\), Linear Algebra Appl. 437 (2012) 1812–1820. doi:10.1016/J.laa.2012.04.044