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