Article in volume
Authors:
Title:
More on signed graphs with at most three eigenvalues
PDFSource:
Discussiones Mathematicae Graph Theory 42(4) (2022) 1313-1331
Received: 2020-08-28 , Revised: 2021-01-24 , Accepted: 2021-01-25 , Available online: 2021-02-11 , https://doi.org/10.7151/dmgt.2393
Abstract:
We consider signed graphs with just 2 or 3 distinct eigenvalues, in particular
(i) those with at least one simple eigenvalue, and (ii) those with
vertex-deleted subgraphs which themselves have at most 3 distinct eigenvalues.
We also construct new examples using weighing matrices and symmetric $3$-class
association schemes.
Keywords:
adjacency matrix, simple eigenvalue, strongly regular signed graph, vertex-deleted subgraph, weighing matrix, association scheme
References:
- M. An\dj elić, T. Koledin and Z. Stanić, On regular signed graphs with three eigenvalues, Discuss. Math. Graph Theory 40 (2020) 405–416.
https://doi.org/10.7151/dmgt.2279 - J. Araujo and T. Bratten, On the spectrum of the Johnson graphs $J(n,k,r)$, Congr. ``Dr. Antonio A.R. Monteiro" XIII (2015) 57–62.
- P.J. Cameron and J.H. van Lint, Designs, Graphs, Codes and their Links (Cambridge University Press, Cambridge, 1991).
https://doi.org/10.1017/CBO9780511623714 - X.-M. Cheng, A.L. Gavrilyuk, G.R.W. Greaves and J.H. Koolen, Biregular graphs with three eigenvalues, European J. Combin. 56 (2016) 57–80.
https://doi.org/10.1016/j.ejc.2016.03.004 - X.-M. Cheng, G.R.W. Greaves and J.H. Koolen, Graphs with three eigenvalues and second largest eigenvalue at most $1$, J. Combin. Theory Ser. B 129 (2018) 55–78.
https://doi.org/10.1016/j.jctb.2017.09.004 - D. Cvetković, P. Rowlinson and S. Simić, An Introduction to the Theory of Graph Spectra (Cambridge University Press, Cambridge, 2010).
- E.R. van Dam, Nonregular graphs with three eigenvalues, J. Combin. Theory Ser. B 73 (1998) 101–118.
https://doi.org/10.1006/jctb.1998.1815 - T. Koledin and Z. Stanić, On a class of strongly regular signed graphs, Publ. Math. Debrecen 97 (2020) 353–365.
https://doi.org/10.5486/PMD.2020.8760 - L. Lovász, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory 25 (1979) 1–7.
https://doi.org/10.1109/TIT.1979.1055985 - T.-T. Lu and S.-H. Shiou, Inverses of $2× 2$ block matrices, Comput. Math. Appl. 43 (2002) 119–129.
https://doi.org/10.1016/S0898-1221(01)00278-4 - F. Ramezani, Some regular signed graphs with only two distinct eigenvalues, Linear Multilinear Algebra(2020), in press.
https://doi.org/10.1080/03081087.2020.1736979 - F. Ramezani and Y. Bagheri, Constructing strongly regular signed graphs, Ars. Combin., in press.
- F. Ramezani, P. Rowlinson and Z. Stanić, On eigenvalue multiplicity in signed graphs, Discrete Math. 343 (2020) 111982.
https://doi.org/10.1016/j.disc.2020.111982 - F. Ramezani, P. Rowlinson and Z. Stanić, Signed graphs with at most three eigenvalues, Czechoslovak Math. J., in press.
- P. Rowlinson, The main eigenvalues of a graph: A survey, Appl. Anal. Discrete Math. 1 (2007) 445–471.
https://doi.org/10.2298/AADM0702445R - P. Rowlinson, On graphs with just three distinct eigenvalues, Linear Algebra Appl. 507 (2016) 462–473.
https://doi.org/10.1016/j.laa.2016.06.031 - P. Rowlinson, More on graphs with just three distinct eigenvalues, Appl. Anal. Discrete Math. 11 (2017) 74–80.
https://doi.org/10.2298/AADM161111033R - Z. Stanić, On strongly regular signed graphs, Discrete Appl. Math. 271 (2019) 184–190.
https://doi.org/10.1016/j.dam.2019.06.017 - Z. Stanić, Main eigenvalues of real symmetric matrices with application to signed graphs, Czechoslovak Math. J. 70 (2020) 1091–1102.
https://doi.org/10.21136/CMJ.2020.0147-19 - T. Zaslavsky, Matrices in the theory of signed simple graphs, in: Advances in Discrete Mathematics and Applications, Mysore 2008, B.D. Acharya, G.O.H. Katona, J. Nešetřil (Ed(s)), (Mysore, Ramanujan Math. Soc. 2010) 207–229.
Close