Eigenvalue -1 and triangle-free graphs

Document Type : Original Paper

Authors

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

Abstract

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.

Keywords

Main Subjects


[1] S. Akbari, P.J. Cameron, and G.B. Khosrovshahi, Ranks and signatures of adjacency matrices,
manuscript (2004), available online at http://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, Cambridge
University 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 with
a given rank, J. Graph Theory 79 (2015), 145–158.
[7] E. Ghorbani, A. Mohammadian, and B. Tayfeh-Rezaie, On order and rank of graphs, Combinatorica
35 (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 given
rank, 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, Linear
Algebra Appl. 432 (2010), 2230–2242.