Eigenvalue -1 and triangle-free graphs

Document Type : Original Paper


Department of Mathematics, K. N. Toosi University of Technology, P. O. Box 16765-3381, Tehran, Iran


Determining the maximum order of graphs whose adjacency matrices have an eigenvalue $mu$ with multiplicity $k$, is a problem which has been studied by several authors. The situation of the problem is quite different for the eigenvalues $-1,0$. In this paper, we investigate this problem for triangle-free graphs and for the eigenvalue $mu=-1$. As the main result of the paper, we prove that the order of graphs with maximum degree $d$ and the eigenvalue $-1$ with multiplicity $k>1$ is at most $k+d+1$. We also characterize the graphs attainting the lower bound.


Main Subjects

[1] S. Akbari, P.J. Cameron, and G.B. Khosrovshahi, Ranks and signatures of adjacency matrices,
manuscript(2004),availbleonlineathttp://www.maths.qmul.ac.uk/~lsoicher/designtheory.org/library/preprints/ranks.pdf[2] F.K. Bell and P. Rowlinson, On the multiplicities of graph eigenvalues, Bull. Lond. Math. Soc. 35(2003), 401–408.[3] D. Cvetković, P. Rowlinson, and S.K. Simić, A Study of eigenspaces of graphs, Linear Algebra Appl.
182 (1993), 45–66.[4] D. Cvetković, P. Rowlinson, and S.K. Simić, An Introduction to the Theory of Graph Spectra, CambridgeUniversity Press, Cambridge, 2010.
[5] H. Esmailian and E. Ghorbani, Maximum order of graphs with a given corank, Linear Algebra Appl.588 (2020), 122–133.[6] E. Ghorbani, A. Mohammadian, and B. Tayfeh-Rezaie, Maximum order of triangle-free graphs witha given rank, J. Graph Theory 79 (2015), 145–158.
[7] E. Ghorbani, A. Mohammadian, and B. Tayfeh-Rezaie, On order and rank of graphs, Combinatorica35 (2015), 655–668.[8] C. Godsil and G. Royle, Algebraic Graph Theory, Springer, New York, 2001.[9] W.H. Haemers and M.J.P. Peeters, The maximum order of adjacency matrices of graphs with a givenrank, Des. Codes, Cryptogr. 65 (2012), 223–232.
[10] R.A. Horn and C.R. Johnson, Matrix Analysis, Second Edition, Cambridge University Press, Cambridge,2013.[11] B.D. McKay, Combinatorial Data, available on line at http://users.cecs.anu.edu.au/~bdm/data/.[12] M. Miloševic, An example of using star complements in classifying strongly regular graphs, Filomat
22 (2008), 53–57.13] P. Rowlinson, On graphs with multiple eigenvalues, Linear Algebra Appl. 283 (1998), 75–85.[14] P. Rowlinson, On multiple eigenvalues of trees, Linear Algebra Appl. 432 (2010), 3007–3011.[15] P. Rowlinson, On eigenvalue multiplicity and the girth of a graph, Linear Algebra Appl. 435 (2011),2375–2381.[16] P. Rowlinson, Eigenvalue multiplicity in cubic graphs, Linear Algebra Appl. 444 (2014), 211–218.[17] P. Rowlinson, Eigenvalue multiplicity in triangle-free graphs, Linear Algebra Appl. 493 (2016), 484–493.[18] P. Rowlinson and B. Tayfeh-Rezaie, Star complements in regular graphs: old and new results, LinearAlgebra Appl. 432 (2010), 2230–2242.