Czechoslovak Mathematical Journal, Vol. 72, No. 1, pp. 59-77, 2022


Signed graphs with at most three eigenvalues

Farzaneh Ramezani, Peter Rowlinson, Zoran Stanić

Received June 22, 2020.   Published online March 5, 2021.

Abstract:  We investigate signed graphs with just 2 or 3 distinct eigenvalues, mostly in the context of vertex-deleted subgraphs, the join of two signed graphs or association schemes.
Keywords:  signed graph; join; adjacency matrix; main eigenvalue; net-degree; association scheme
Classification MSC:  05C22, 05C50


References:
[1] M. Anđelić, T. Koledin, Z. Stanić: On regular signed graphs with three eigenvalues. Discuss. Math., Graph Theory 40 (2020), 405-416. DOI 10.7151/dmgt.2279 | MR 4060992 | Zbl 1433.05139
[2] F. Belardo, S. M. Cioabă, J. Koolen, J. Wang: Open problems in the spectral theory of signed graphs. Art Discrete Appl. Math. 1 (2018), Article ID P2.10, 23 pages. DOI 10.26493/2590-9770.1286.d7b | MR 3997096 | Zbl 1421.05052
[3] F. Belardo, S. K. Simić: On the Laplacian coefficients of signed graphs. Linear Algebra Appl. 475 (2015), 94-113. DOI 10.1016/j.laa.2015.02.007 | MR 3325220 | Zbl 1312.05078
[4] H. C. Chan, C. A. Rodger, J. Seberry: On inequivalent weighing matrices. Ars Comb. 21A (1986), 299-333. MR 0835757 | Zbl 0599.05013
[5] X.-M. Cheng, A. L. Gavrilyuk, G. R. W. Greaves, J. H. Koolen: Biregular graphs with three eigenvalues. Eur. J. Comb. 56 (2016), 57-80. DOI 10.1016/j.ejc.2016.03.004 | MR 3490095 | Zbl 1335.05107
[6] X.-M. Cheng, G. R. W. Greaves, J. H. Koolen: Graphs with three eigenvalues and second largest eigenvalue at most 1. J. Comb. Theory, Ser. B 129 (2018), 55-78. DOI 10.1016/j.jctb.2017.09.004 | MR 3758241 | Zbl 1379.05072
[7] C. J. Colbourn, J. H. Dinitz (eds.): Handbook of Combinatorial Designs. Discrete Mathematics and its Applications. Chapman & Hall/CRC, Boca Raton (2007). DOI 10.1201/9781420010541 | MR 2246267 | Zbl 1101.05001
[8] D. Cvetković, M. Doob, H. Sachs: Spectra of Graphs: Theory and Applications. J. A. Barth, Leipzig (1995). MR 1324340 | Zbl 0824.05046
[9] D. Cvetković, P. Rowlinson, S. Simić: An Introduction to the Theory of Graph Spectra. London Mathematical Society Student Texts 75. Cambridge University Press, Cambridge (2010). DOI 10.1017/CBO9780511801518 | MR 2571608 | Zbl 1211.05002
[10] M. Harada, A. Munemasa: On the classification of weighing matrices and self-orthogonal codes. J. Comb. Des. 20 (2012), 45-57. DOI 10.1002/jcd.20295 | MR 2864617 | Zbl 1252.05026
[11] Y. Hou, Z. Tang, D. Wang: On signed graphs with just two distinct adjacency eigenvalues. Discrete Math. 342 (2019), Article ID 111615, 8 pages. DOI 10.1016/j.disc.2019.111615 | MR 3990025 | Zbl 1422.05049
[12] J. McKee, C. Smyth: Integer symmetric matrices having all their eigenvalues in the interval $[-2,2]$. J. Algebra 317 (2007), 260-290. DOI 10.1016/j.jalgebra.2007.05.019 | MR 2360149 | Zbl 1140.15007
[13] F. Ramezani: On the signed graphs with two distinct eigenvalues. Util. Math. 114 (2020), 33-48. Zbl 07274222
[14] F. Ramezani: Some regular signed graphs with only two distinct eigenvalues. To appear in Linear Multilinear Algebra. DOI 10.1080/03081087.2020.1736979
[15] F. Ramezani, P. Rowlinson, Z. Stanić: On eigenvalue multiplicity in signed graphs. Discrete Math. 343 (2020), Article ID 111982, 8 pages. DOI 10.1016/j.disc.2020.111982 | MR 4107756 | Zbl 07233221
[16] P. Rowlinson: Certain 3-decompositions of complete graphs, with an application to finite fields. Proc. R. Soc. Edinb., Sect. A 99 (1985), 277-281. DOI 10.1017/S0308210500014293 | MR 0785534 | Zbl 0562.05044
[17] P. Rowlinson: On graphs with just three distinct eigenvalues. Linear Algebra Appl. 507 (2016), 462-473. DOI 10.1016/j.laa.2016.06.031 | MR 3536969 | Zbl 1343.05096
[18] P. Rowlinson: More on graphs with just three distinct eigenvalues. Appl. Anal. Discrete Math. 11 (2017), 74-80. DOI 10.2298/AADM161111033R | MR 3648655
[19] J. J. Seidel: Graphs and two-graphs. Proceedings of the 5th Southeastern Conference on Combinatorics, Graph Theory, and Computing. Utilitas Mathematica Publication, Winnipeg (1974), 125-143. MR 0364028 | Zbl 0308.05120
[20] S. K. Simić, Z. Stanić: Polynomial reconstruction of signed graphs. Linear Algebra Appl. 501 (2016), 390-408. DOI 10.1016/j.laa.2016.03.036 | MR 3485074 | Zbl 1334.05056
[21] Z. Stanić: Regular Graphs: A Spectral Approach. De Gruyter Series in Discrete Mathematics and Applications 4. De Gruyter, Berlin (2017). DOI 10.1515/9783110351347 | MR 3753662 | Zbl 1370.05002
[22] Z. Stanić: Integral regular net-balanced signed graphs with vertex degree at most four. Ars Math. Contemp. 17 (2019), 103-114. DOI 10.26493/1855-3974.1740.803 | MR 3998150 | Zbl 1433.05142
[23] Z. Stanić: On strongly regular signed graphs. Discrete Appl. Math. 271 (2019), 184-190; corrigendum ibid. 284 640 (2020). DOI 10.1016/j.dam.2019.06.017 | MR 4030312 | Zbl 1428.05331
[24] Z. Stanić: Spectra of signed graphs with two eigenvalues. Appl. Math. Comput. 364 (2020), Article ID 124627, 9 pages. DOI 10.1016/j.amc.2019.124627 | MR 3996372 | Zbl 1433.05210
[25] E. R. van Dam: Nonregular graphs with three eigenvalues. J. Comb. Theory, Ser. B 73 (1998), 101-118. DOI 10.1006/jctb.1998.1815 | MR 1631983 | Zbl 0917.05044
[26] E. R. van Dam: Three-class association schemes. J. Algebr. Comb. 10 (1999), 69-107. DOI 10.1023/A:1018628204156 | MR 1701285 | Zbl 0929.05096
[27] T. Zaslavsky: Signed graphs. Discrete Appl. Math. 4 (1982), 47-74. DOI 10.1016/0166-218X(82)90033-6 | MR 0676405 | Zbl 0476.05080
[28] T. Zaslavsky: Matrices in the theory of signed simple graphs. Advances in Discrete Mathematics and Applications. Ramanujan Mathematical Society Lecture Notes Series 13. Ramanujan Mathematical Society, Mysore (2010), 207-229. MR 2766941 | Zbl 1231.05120

Affiliations:   Farzaneh Ramezani, Department of Mathematics, K.N. Toosi University of Technology, 470 Mirdamad Ave. West, 19697, P.O. Box 16315-1618, Tehran, Iran, e-mail: ramezani@kntu.ac.ir; Peter Rowlinson, Mathematics and Statistics Group, Division of Computing Science and Mathematics, University of Stirling, Scotland FK9 4LA, United Kingdom, e-mail: p.rowlinson@stirling.ac.uk; Zoran Stanić (corresponding author), Faculty of Mathematics, University of Belgrade, Studentski trg 16, 11 000 Belgrade, Serbia, e-mail: zstanic@math.rs


 
PDF available at: