A construction of cospectral signed line graphs

Document Type : Original paper

Author

Faculty of Mathematics, University of Belgrade, Studentski trg 16, 11 000 Belgrade, Serbia

Abstract

For an ordinary graph $G$, we compute the eigenvalues and the eigenspaces of the signed line graph $\mathcal{L}(\ddot{G})$, where $\ddot{G}$ is obtained from $G$ by inserting a negative parallel edge between every pair of adjacent vertices. As an application, we prove that if $G$ and $H$ share the same vertex degrees, then $\mathcal{L}(\ddot{G})$ and $\mathcal{L}(\ddot{H})$ share the same spectrum. To the best of our knowledge, this construction does not follow the line of any known construction developed for either graphs or signed graphs. Among the other consequences, we emphasize that $\mathcal{L}(\ddot{G})$ is integral (i.e., its spectrum consists entirely of integers), which means that a construction of integral signed graphs has been established simultaneously.

Keywords

Main Subjects

References

[1] K. Balińska, D. Cvetković, M. Lepović, and S. Simić, There are exactly 150 connected integral graphs up to 10 vertices, Publ. Elektroteh. fak., Ser. Mat. 10 (1999), 95–105.
[2] R.B. Bapat and M. Karimi, Construction of cospectral regular graphs, Mat. Vesn. 68 (2016), no. 1, 66–76.
[3] F. Belardo, Balancedness and the least eigenvalue of Laplacian of signed graphs, Linear Algebra Appl. 446 (2014), 133–147. https://doi.org/10.1016/j.laa.2014.01.001
[4] F. Belardo, M. Brunetti, M. Cavaleri, and A. Donno, Constructing cospectral signed graphs, Linear Multilinear Algebra 69 (2021), no. 14, 2717–2732. https://doi.org/10.1080/03081087.2019.1694483
[5] F. Belardo, M. Brunetti, M. Cavaleri, Construction of cospectral graphs, signed graphs and T-gain graphs via
partial transpose, J. Algebraic Combin. 60 (2024), no. 1, 191–224. https://doi.org/10.1007/s10801-024-01332-z
[6] F. Belardo, S. Cioabă, J. Koolen, and J. Wang, Open problems in the spectral theory of signed graphs, Art Discrete Appl. Math. 1 (2018), no. 2, #P2.10.
[7] F. Belardo, E.M.L. Marzi, and S.K. Simić, Signed line graphs with least eigenvalue- 2: the star complement technique, Discrete Appl. Math. 207 (2016), 29–38.  https://doi.org/10.1016/j.dam.2016.02.018
[8] F. Belardo, Z. Stanić, and T. Zaslavsky, Total graph of a signed graph, Ars Math. Contemp. 23 (2023), no. 1, P1.02 https://doi.org/10.26493/1855-3974.2842.6b5
[9] S. Butler, A note about cospectral graphs for the adjacency and normalized Laplacian matrices, Linear Multilinear Algebra 58 (2010), no. 3, 387–390. https://doi.org/10.1080/03081080902722741
[10] D. Cvetković, Constructing trees with given eigenvalues and angles, Linear Algebra Appl. 105 (1988), 1–8. https://doi.org/10.1016/0024-3795(88)90002-X
[11] S. Dutta and B. Adhikari, Construction of cospectral graphs, J. Algebraic Combin. 52 (2020), no. 2, 215–235. https://doi.org/10.1007/s10801-019-00900-y
[12] C. Godsil and B. Mckay, Products of graphs and their spectra, Combinatorial Mathematics IV (Berlin, Heidelberg) (L.R.A. Casse and W.D. Wallis, eds.), Springer Berlin Heidelberg, 1976, pp. 61–72.
[13] C.D. Godsil and B.D. McKay, Constructing cospectral graphs, Aequationes Math. 25 (1982), no. 1, 257–268. https://doi.org/10.1007/BF02189621
[14] G. Greaves, J. Koolen, A. Munemasa, Y. Sano, and T. Taniguchi, Edge-signed graphs with smallest eigenvalue greater than −2, J. Combin. Theory Ser. B 110 (2015), 90–111. https://doi.org/10.1016/j.jctb.2014.07.006
[15] W.H. Haemers, Are almost all graphs determined by their spectrum, Not. S. Afr. Math. Soc. 47 (2016), no. 1, 42–45.
[16] J. McKee and C. Smyth, Integer symmetric matrices having all their eigenvalues in the interval [−2, 2], J. Algebra 317 (2007), no. 1, 260–290. https://doi.org/10.1016/j.jalgebra.2007.05.019
[17] L. Qiu, Y. Ji, and W. Wang, On a theorem of Godsil and McKay concerning the construction of cospectral graphs, Linear Algebra Appl. 603 (2020), 265–274. https://doi.org/10.1016/j.laa.2020.05.025
[18] A.J. Schwenk, Exactly thirteen connected cubic graphs have integral spectra, Theory and Applications of Graphs (Berlin, Heidelberg) (Y. Alavi and D.R. Lick, eds.), Springer Berlin Heidelberg, 1978, pp. 516–533.
[19] J.J. Seidel, A survey of two-graphs, Colloquio Internazionale sulle Teorie Combinatorie, vol. I (P.G. Pal, ed.), Accademia nazionale dei Lincei, Rome, 1973, pp. 481–511.
[20] Z. Stanić, Recognizing signed line graphs with a single root, Submitted.
[21] Z. Stanić, Integral regular net-balanced signed graphs with vertex degree at most four., Ars Math. Contemp. 17 (2019), no. 1, 103–114. https://doi.org/10.26493/1855-3974.1740.803
[22] Z. Stanić, A decomposition of signed graphs with two eigenvalues, Filomat 34 (2020), no. 6, 1949–1957.
[23] Z. Stanić, Spectra of signed graphs with two eigenvalues, Appl. Math. Comput. 364 (2020), 124627. https://doi.org/10.1016/j.amc.2019.124627
[24] Z. Stanić, On cospectral oriented graphs and cospectral signed graphs, Linear Multilinear Algebra 70 (2022), no. 19, 3689–3701. https://doi.org/10.1080/03081087.2020.1852153
[25] D. Wang and Y. Hou, Integral signed subcubic graphs, Linear Algebra Appl. 593 (2020), 29–44. https://doi.org/10.1016/j.laa.2020.01.037
[26] T. Zaslavsky, Matrices in the theory of signed simple graphs, Advances in Discrete Mathematics and Applications (B.D. Acharya, G.O.H. Katona, and Jaroslav Nešetˇril, eds.), Mysore 2008, Ramanujan Math. Soc., 2010, pp. 207–229.
Communications in Combinatorics and Optimization
Volume 11, Issue 3
September 2026
Pages 985-993

Files

Share

How to cite

Statistics