Graphs with at most Four Seidel Eigenvalues

Download PDF


DOI: 10.46793/KgJMat2302.173G


Let G be a graph of order n with adjacency matrix A(G). The eigenvalues of matrix S(G) = Jn In 2A(G), where Jn is the n by n matrix with all entries 1, are called the Seidel eigenvalues of G. Let ????(n,r) be the set of all graphs of order n with a single Seidel eigenvalue with multiplicity r. In the present work, we will characterize all graphs in the class ????(n,n i) for i = 1, 2 and for the case i = 3 our characterization is done by this condition that the nullity of S(G) is zero. If the nullity of S(G) is not zero the problem is solved in special cases.


Interlacing theorem, Seidel eigenvalue, Seidel switching, nullity.


[1]   N.  Biggs, Algebraic Graph Theory, Cambridge University Press, Cambridge, 1993.

[2]   J.  A. Bondy and U.  S.  R. Murty, Graph Theory with Applications, Elseyier Science Publishing Co., New York, 1976.

[3]   A.  E. Brouwer and W. H. Haemers, Spectra of Graphs, Universitext, Springer, New York, 2012.

[4]   M.  N. Ellingham, Basic subgraphs and graph spectra, Austras. J. Combin. 8 (1993), 247–265.

[5]   E.  Ghorbani, On eigenvalues of Seidel matrices and Haemers’ conjecture, Des. Codes Cryptogr. 84(1-2) (2017), 189–195.

[6]   G.  R.  W. Greaves, Equiangular line systems and switching classes containing regular graphs, Linear Algebra Appl. 536 (2018), 31–51.

[7]   G.  Greaves, J.  H. Koolen, A.  Munemasa and F.  Szöllősi, Equiangular lines in Euclidean spaces, J. Combin. Theory Ser. A 138 (2016), 208–235.

[8]   W.  H. Haemers, Seidel switching and graph energy, MATCH Commun. Math. Comput. Chem. 68 (2012), 653–659.

[9]   M.  Hakimi-Nezhaad and M.  Ghorbani, On the Estrada index of Seidel matrix, Math. Interdisc. Res. 5(1)(2020), 43–54.

[10]   M.  Hakimi-Nezhaad and M.  Ghorbani, Seidel borderenergetic graphs, TWMS J. App. Eng. Math. 10(2) (2020), 389–399.

[11]   X.  Huang and Q.  Huang, On regular graphs with four distinct eigenvalues, Linear Algebra Appl. 512 (2017), 219–233.

[12]   Sage Mathematics Software (Version 8.6), 2019,

[13]    J.  H. van Lint and J.  J. Seidel, Equilateral point sets in elliptic geometry, Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen: Series A: Mathematical Sciences 28 (1966), 335–348.