Graphs with at most Four Seidel Eigenvalues


Download PDF

Authors: M. GHORBANI, M. HAKIMI-NEZHAAD AND B. ZHOU

DOI: 10.46793/KgJMat2302.173G

Abstract:

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.



Keywords:

Interlacing theorem, Seidel eigenvalue, Seidel switching, nullity.



References:

[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. https://doi.org/10.1007/s10623-016-0248-x

[6]   G.  R.  W. Greaves, Equiangular line systems and switching classes containing regular graphs, Linear Algebra Appl. 536 (2018), 31–51. https://doi.org/10.1016/j.laa.2017.09.008

[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. https://doi.org/10.1016/j.jcta.2015.09.008

[8]   W.  H. Haemers, Seidel switching and graph energy, MATCH Commun. Math. Comput. Chem. 68 (2012), 653–659. https://doi.org/10.2139/ssrn.2026916

[9]   M.  Hakimi-Nezhaad and M.  Ghorbani, On the Estrada index of Seidel matrix, Math. Interdisc. Res. 5(1)(2020), 43–54. https://doi.org/10.22052/MIR.2019.179267.1128

[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. https://doi.org/10.1016/j.laa.2016.09.043

[12]   Sage Mathematics Software (Version 8.6), 2019, www.sagemath.org.

[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. https://doi.org/10.1016/S1385-7258(66)50038-5