Unbalanced complete bipartite signed graphs ${K_{m, n}}^{\sigma}$ having $m$ and $n$ as Laplacian eigenvalues with maximum multiplicities

Articles in Press

Document Type : Original paper

Author

School of Basic Sciences, IIT Bhubaneswar, Bhubaneswar, 752050, India

Abstract

A signed graph $ {G}^{\sigma} = (G, \sigma) $ consists of an underlying graph $ G = (V, E) $ along with a signature function $ \sigma: E \rightarrow \{-1, 1\} $. A cycle in a signed graph is termed positive if it contains an even number of negative edges, and negative if it contains an odd number of negative edges. A signed graph is considered { balanced} if it has no negative cycles; otherwise, it is { unbalanced}. Let $K_{m,n}$ be a { complete bipartite graph} on $m+n$ vertices. It is well known that for a balanced complete bipartite signed graph $ {K_{m,n}}^{\sigma} $, the parameters $ m $ and $ n $ are Laplacian eigenvalues with multiplicities $ n-1 $ and $ m-1 $, respectively. This raises a natural question about the maximum multiplicities of Laplacian eigenvalues $ m $ and $ n $ in an unbalanced complete bipartite signed graph $ {K_{m,n}}^{\sigma} $. In this paper, we demonstrate that the multiplicities of the Laplacian eigenvalues $ m $ and $ n $ in an unbalanced complete bipartite signed graph $ {K_{m,n}}^{\sigma} $ are at most $ n-2 $ and $ m-2 $, respectively. Additionally, we characterize all the signed graphs for which $ m $ and $ n $ are Laplacian eigenvalues with these maximum multiplicities.

Keywords

Main Subjects

References

[1] S. Akbar, S. Dalvandi, F. Heydari, and M. Maghasedi, On the multiplicity of −1 and 1 in signed complete graphs, Util. Math. 116 (2020).
[2] S. Akbari, S. Dalvandi, F. Heydari, and M. Maghasedi, On the eigenvalues of signed complete graphs, Linear Multilinear Algebra 67 (2019), no. 3, 433–441. https://doi.org/10.1080/03081087.2017.1403548
[3] S. Akbari, S. Dalvandi, F. Heydari, and M. Maghasedi, Signed complete graphs with maximum index, Discuss. Math. Graph Theory 40 (2020), no. 2, 393–403.  https://doi.org/10.7151/dmgt.2276
[4] S. Akbari, H.R. Maimani, and P.L. Majd, On the spectrum of some signed complete and complete bipartite graphs, Filomat 32 (2018), no. 17, 5817–5826.  https://doi.org/10.2298/FIL1817817A
[5] F. Belardo and P. Petecki, Spectral characterizations of signed lollipop graphs, Linear Algebra Appl. 480 (2015), 144–167.   https://doi.org/10.1016/j.laa.2015.04.022
[6] A.E. Brouwer and W.H. Haemers, Spectra of Graphs, Springer New York, 2011.
[7] M. Brunetti and Z. Stanic, Ordering signed graphs with large index, Ars Math. Contemp. 22 (2022), no. 4, #P4.05 https://doi.org/10.26493/1855-3974.2714.9b3
[8] S. Dalvandi, F. Heydari, and M. Maghasedi, Signed complete graphs with exactly  m non-negative eigenvalues, Bull. Malays. Math. Sci. Soc. 45 (2022), no. 5, 2107–2122.  https://doi.org/10.1007/s40840-022-01331-y
[9] E. Ghorbani and A. Majidi, Signed graphs with maximal index, Discrete Math. 344 (2021), no. 8, Article ID: 112463. https://doi.org/10.1016/j.disc.2021.112463
[10] N. Kafai and F. Heydari, Maximizing the indices of a class of signed complete graphs, Commun. Comb. Optim. 9 (2024), no. 1, 169–175.  https://doi.org/10.22049/cco.2022.28103.1442
[11] M.R. Kannan and S. Pragada, Signed spectral Turán type theorems, Linear Algebra Appl. 663 (2023), 62–79. https://doi.org/10.1016/j.laa.2023.01.002
[12] T. Koledin and Z. Stanić, Connected signed graphs of fixed order, size, and number of negative edges with maximal index, Linear Multilinear Algebra 65 (2017), no. 11, 2187–2198. https://doi.org/10.1080/03081087.2016.1265480
[13] S. Pirzada, T. Shamsher, and M.A. Bhat, On the eigenvalues of complete bipartite signed graphs, Ars Math. Contemp. 24 (2024), no. 4, #P4.08  https://doi.org/10.26493/1855-3974.3180.7ea
[14] T. Shamsher, Exploring spectral properties of the Laplacian matrix of a complete bipartite signed graph, Submitted (2024).
[15] T. Shamsher, S. Pirzada, and M.A. Bhat, On adjacency and Laplacian cospectral switching non-isomorphic signed graphs, Ars Math. Contemp. 23 (2023), no. 3, #P3.09  https://doi.org/10.26493/1855-3974.2902.f01
[16] X. Zhang, H. Wang, J. Yu, C. Chen, X. Wang, and W. Zhang, Polarity-based graph neural network for sign prediction in signed bipartite graphs, World Wide Web 25 (2022), no. 2, 471–487. https://doi.org/10.1007/s11280-022-01015-4
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 23 October 2024

Files

Share

How to cite

Statistics