Singularity of cycle-spliced signed graphs
DOI:
https://doi.org/10.22199/issn.0717-6279-6376Keywords:
Nullity, Cycle-spliced bipartite signed graphs, cyclomatic numberAbstract
We consider the adjacency spectrum of cycle-spliced signed graphs (CSSG), i.e., signed graphs whose blocks are (independent) signed cycles. For a signed graph Σ, the nullity η(Σ) is the multiplicity of the 0-eigenvalue. The adjancency spectrum of cycle-spliced (signed) graphs is studied in the literature for the relation between the nullity η and the cyclomatic number c, in particular, it is known that 0≤η(Σ) ≤ c(Σ)+1. In this paper, nonsingular cycle-spliced bipartite signed graphs are characterized. For cycle-spliced signed graphs Σ having only odd cycles, we show that η(Σ) is 0 or 1. Finally, we compute the nullity of CSSGs consisting of at most three cycles.
Downloads
References
B. D. Acharya, Spectral criterion for cycle balance in networks, J. Graph Theory, Vol. 4, pp. 1-11, 1980. https://doi.org/10.1002/jgt.3190040102
F. Belardo, S. Simi'c, On the Laplacian coefficients of signed graphs, Linear Algebra Appl., Vol. 475, pp. 94-113, 2015. https://doi.org/10.1016/j.laa.2015.02.007
F. Belardo, Y. Zhou, Signed graphs with extremal least laplacian eigenvalue, Linear Algebra Appl., Vol. 497, pp. 167-180, 2016. https://doi.org/10.1016/j.laa.2016.02.028
F. Belardo, S. Cioaba, J. Koolen, J. Wang, Open problems in the spectral theory of signed graphs, Art Discrete Appl. Math., Vol. 1 (2), 2018, article n. #P2.10. https://doi.org/10.26493/2590-9770.1286.d7b
F. Belardo, M. Brunetti, A. Ciampella, Signed bicyclic graphs minimizing the least laplacian eigenvalue, Linear Algebra Appl., Vol. 557, pp. 201-233, 2018. https://doi.org/10.1016/j.laa.2018.07.026
F. Belardo, M. Brunetti, A. Ciampella, Unbalanced unicyclic and bicyclic graphs with extremal spectral radius, Czechoslovak Math. J., Vol. 71 (2), pp. 417-433, 2021. https://doi.org/10.21136/CMJ.2020.0403-19
D. Bravo, J. Rada, Coalescence of difans and diwheels, Bulletin of the Malaysian Mathematical Sciences Society. Second Series, Vol. 30 (1), pp.49-56, 2007. https://doi.org/10.1155/2007/46851
M. Brunetti, A. Ciampella, Signed bicyclic graphs with minimal index, Commun. Comb. Optim., Vol. 8 (1), pp. 207-241, 2023.
S. Chang, J. Li, Y. Zheng, Nullities of cycle-spliced bipartite graphs, Electronic J. of Linear Algebra, Vol. 39, pp. 327-338, 2023. https://doi.org/10.13001/ela.2023.7377
S. Chang, J. Li, Y. Zheng, The Nullities of Signed Cycle-Spliced Graphs, Journal of Mathematical Research with Applications, Vol. 43 (6), pp. 631-647, 2023.
S. Chang, B. S. Tam, J. Li, Y. Zheng, Graphs G with nullity 2c(G) +p(G) − 1, Discr. Appl. Math., Vol. 311, pp. 38-58, 2022.
C. L. Coates, Flow-graph solutions of linear algebraic equations, IRE Trans. Circuit Theory CT-6, pp. 170-187, 1959. https://doi.org/10.1109/TCT.1959.1086537
L. Collatz, U. Sinogowitz, Spektren endlicher grafen, Abh. Math. Semin. Univ. Hamb., Vol. 21, pp. 63-77, 1957. https://doi.org/10.1007/BF02941924
D. Cvetkovi'c, On reconstruction of the characteristic polynomial of a graph, Discrete Math., Vol. 212, pp. 45-52, 2000. https://doi.org/10.1016/S0012-365X(99)00207-1
D. Cvetkovi'c, M. Doob, H. Sachs, Spectra of graphs, third ed., Johann Ambrosius Barth, Heidelberg, 1995.
D. Cvetkovi'c, I. Gutman, The algebraic multiplicity of the number zero in the spectrum of a bipartite graph, Mat. Vesnik, Vol. 9 (24), pp. 141-150, 1972.
Y. Z. Fan, W. X. Du, C. L. Dong, The nullity of bicyclic signed graphs, Linear Multilinear A., Vol. 62 (2),pp. 242-251, 2014. https://doi.org/10.1080/03081087.2013.771638
Y. Z. Fan, Y. Wang, Y. Wang, A note on the nullity of unicyclic signed graphs, Linear Algebra Appl., Vol. 438 (3), pp. 1193-1200, 2013. https://doi.org/10.1016/j.laa.2012.08.027
Y. Z. Fan, Y. Wang, Y. Wang, A note on the nullity of unicyclic signed graphs, Linear Algebra Appl., Vol. 438 (3), pp. 1193-1200, 2013. https://doi.org/10.1016/j.laa.2012.08.027
Y. Fan, Largest eigenvalue of a unicyclic mixed graph, Appl. Math. J. Chinese Univ. Ser. B, Vol. 19 (2), pp. 140-148, 2004. https://doi.org/10.1007/s11766-004-0047-4
M.K. Gill, B. D. Acharya, A recurrence formula for computing the characteristic polynomial of a sigraph, J. Combin. Inform. System Sci., Vol. 5, pp. 68-72, 1980.
Y. Hou, J. Li, Y. Pan, On the Laplacian eigenvalues of signed graphs, Linear Multilinear A., Vol. 51 (1), pp 21-30, 2003. https://doi.org/10.1080/0308108031000053611
Y. Lu, J. Wu, No signed graph with the nullity η(G, σ) = |V (G)| −2m(G)+2c(G)−1, Linear Algebra Appl., Vol. 615, pp. 175-193, 2021. https://doi.org/10.1016/j.laa.2021.01.002
X. Ma, D. Wong, F. Tian, Nullity of a graph in terms of the dimension of cycle space and the number of pendant vertices, Discr. Appl. Math., Vol. 215, pp. 171-176, 2016. https://doi.org/10.1016/j.dam.2016.07.010
L. Wang, X. Fang, X. Geng, Graph with nullity 2c(G) + p(G) − 1, Discr. Math., Vol. 345, 112786, 2022. https://doi.org/10.1016/j.disc.2021.112786
D. Wong, Q. Zhou, F. Tian, Nullity and singularity of a graph in which every block is a cycle, Discr. Math., Vol. 345 112851, 2022. https://doi.org/10.1016/j.disc.2022.112851
Q. Wu, Y. Lu, B. S. Tam, On connected signed graphs with rank equal to girth, Linear Algebra Appl., Vol. 651, pp. 90-115, 2022. https://doi.org/10.1016/j.laa.2022.06.019
L. Yu,Y. Lihua, Further results on the nullity of signed graphs, J. Appl. Math., (2014), Art. ID 483735, 8 pp. https://doi.org/10.1155/2014/483735
T. Zaslavsky, A mathematical bibliography of signed and gain graphs and allied areas, Electron. J. Combin., Vol. 8 124, 1998.
Downloads
Published
Issue
Section
License
Copyright (c) 2024 Adriana Ciampella, Suliman Khan
This work is licensed under a Creative Commons Attribution 4.0 International License.
-
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
