1. bookVolume 42 (2022): Issue 4 (November 2022)
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

More on Signed Graphs with at Most Three Eigenvalues

Published Online: 12 Jul 2022
Volume & Issue: Volume 42 (2022) - Issue 4 (November 2022)
Page range: 1313 - 1331
Received: 28 Aug 2020
Accepted: 25 Jan 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
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

MSC 2010

[1] M. Anđ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 Search in Google Scholar

[2] 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. Search in Google Scholar

[3] 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 Search in Google Scholar

[4] 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 Search in Google Scholar

[5] 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 Search in Google Scholar

[6] D. Cvetković, P. Rowlinson and S. Simić, An Introduction to the Theory of Graph Spectra (Cambridge University Press, Cambridge, 2010).10.1017/CBO9780511801518 Search in Google Scholar

[7] 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 Search in Google Scholar

[8] 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 Search in Google Scholar

[9] 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 Search in Google Scholar

[10] 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 Search in Google Scholar

[11] 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 Search in Google Scholar

[12] F. Ramezani and Y. Bagheri, Constructing strongly regular signed graphs, Ars. Combin., in press. Search in Google Scholar

[13] 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 Search in Google Scholar

[14] F. Ramezani, P. Rowlinson and Z. Stanić, Signed graphs with at most three eigenvalues, Czechoslovak Math. J., in press. Search in Google Scholar

[15] P. Rowlinson, The main eigenvalues of a graph: A survey, Appl. Anal. Discrete Math. 1 (2007) 445–471. https://doi.org/10.2298/AADM0702445R Search in Google Scholar

[16] 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 Search in Google Scholar

[17] P. Rowlinson, More on graphs with just three distinct eigenvalues, Appl. Anal. Discrete Math. 11 (2017) 74–80. https://doi.org/10.2298/AADM161111033R Search in Google Scholar

[18] Z. Stanić, On strongly regular signed graphs, Discrete Appl. Math. 271 (2019) 184–190. https://doi.org/10.1016/j.dam.2019.06.017 Search in Google Scholar

[19] 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 Search in Google Scholar

[20] 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. Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo