DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

F. Ramezani

Farzaneh Ramezani

K.N. Toosi University of Technology

email: ramezani@kntu.ac.ir

P. Rowlinson

Peter Rowlinson

Mathematics and Statistics Group
8 Division of Computing Science and Mathematics

email: p.rowlinson@stirling.ac.uk

Z. Stanić

Zoran Stanić

University of Belgrade

email: zstanic@matf.bg.ac.rs

Title:

More on signed graphs with at most three eigenvalues

PDF

Source:

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:

  1. 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
  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.
  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
  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
  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
  6. D. Cvetković, P. Rowlinson and S. Simić, An Introduction to the Theory of Graph Spectra (Cambridge University Press, Cambridge, 2010).
  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
  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
  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
  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
  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
  12. F. Ramezani and Y. Bagheri, Constructing strongly regular signed graphs, Ars. Combin., in press.
  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
  14. F. Ramezani, P. Rowlinson and Z. Stanić, Signed graphs with at most three eigenvalues, Czechoslovak Math. J., in press.
  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
  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
  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
  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
  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
  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.

Close