Singularity of cycle-spliced signed graphs

Authors

DOI:

https://doi.org/10.22199/issn.0717-6279-6376

Keywords:

Nullity, Cycle-spliced bipartite signed graphs, cyclomatic number

Abstract

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.

Author Biographies

Suliman Khan, University of Campania "Luigi Vanvitelli".

Department of Mathematics and Physics.

Adriana Ciampella, University of Naples Federico II.

Department of Mathematics and Applications.

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.

Published

2024-06-17

How to Cite

[1]
S. Khan and A. Ciampella, “Singularity of cycle-spliced signed graphs”, Proyecciones (Antofagasta, On line), vol. 43, no. 4, pp. 849-871, Jun. 2024.

Issue

Section

Artículos

Most read articles by the same author(s)