On the nullity of cycle-spliced T-gain graphs

Document Type : Original paper

Authors

1 Department of Mathematics and Applications, University of Naples “Federico II”, Piazzale Tecchio 80, Napoli 80125, Italy

2 Department of Mathematics and Physics, University of Campania “Luigi Vanvitelli”, Viale Lincoln 5, Caserta, I–81100, Italy

Abstract

Let Φ=(G,φ) be a T-gain (or complex unit gain) graph and A(Φ) be its adjacency matrix. The nullity of Φ, denoted by η(Φ), is the multiplicity of zero as an eigenvalue of A(Φ), and the cyclomatic number of Φ is defined by c(Φ)=e(Φ)−n(Φ)+κ(Φ), where n(Φ), e(Φ) and κ(Φ) are the number of vertices, edges and connected components of Φ, respectively. A connected graph is said to be cycle-spliced if every block in it is a cycle. We consider the nullity of cycle-spliced T-gain graphs. Given a cycle-spliced T-gain graph Φ with c(Φ) cycles, we prove that 0≤η(Φ)≤c(Φ)+1. Moreover, we show that there is no cycle-spliced  T-gain graph Φ of any order with η(Φ)=c(Φ) whenever there are no odd cycles whose gain has real part 0. We give examples of cycle-spliced  T-gain graphs whose nullity equals the cyclomatic number, and we show some properties of those graphs Φ such that η(Φ)=c(Φ)−ε, ε∈{0,1}. A characterization is given in case η(Φ)=c(Φ) when Φ is obtained by identifying a unique common vertex of 2 cycle-spliced T-gain graphs Φ1 and Φ2. Finally, we compute the nullity of all T-gain graphs Φ with c(Φ)=2.

Keywords

Main Subjects

References

[1] J.A. Barnes, Graph theory and social networks: A technical comment on connectedness and connectivity, Sociology 3 (1969), no. 2, 215–232.  https://doi.org/10.1177/003803856900300205
[2] F. Belardo, M. Brunetti, and A. Ciampella, On the multiplicity of α as an aα(γ)-eigenvalue of signed graphs with pendant vertices, Discrete Math. 342 (2019), no. 8, 2223–2233.  https://doi.org/10.1016/j.disc.2019.04.024
[3] D. Bravo and J. Rada, Coalescence of difans and diwheels., Bull. Malays. Math. Sci. Soc. Second Series 30 (2007), no. 1, 49–56.
[4] S. Chang, J. Li, and Y. Zheng, The nullities of signed cycle-spliced graphs, J. Math. Res. Appl. 43 (2023), no. 6, 631–647. https://doi.org/10.3770/j.issn:2095-2651.2023.06.001
[5] S. Chang, B.S. Tam, J. Li, and Y. Zheng, Graphs g with nullity 2c(g)+p(g)−1, Discrete Appl. Math. 311 (2022), 38–58. https://doi.org/10.1016/j.dam.2022.01.008
[6] A. Ciampella and S. Khan, Singularity of cycle-spliced signed graphs, Proyecciones (Antofagasta) 43 (2024), no. 4, 849–871.  https://doi.org/10.22199/issn.0717-6279-6376
[7] S. Derrible and C. Kennedy, Applications of graph theory and network science to transit network design, Transp. Rev. 31 (2011), no. 4, 495–519.  https://doi.org/10.1080/01441647.2010.543709
[8] Y.Z. Fan, W .X. Du, and C.L. Dong, The nullity of bicyclic signed graphs, Linear Multilinear Algebra 62 (2014), no. 2, 242–251.  https://doi.org/10.1080/03081087.2013.771638
[9] Y.Z. Fan, Y. Wang, and Y. Wang, A note on the nullity of unicyclic signed graphs, Linear Algebra Appl. 438 (2013), no. 3, 1193–1200.  https://doi.org/10.1016/j.laa.2012.08.027
[10] S. He, R.X. Hao, and F. Dong, The rank of a complex unit gain graph in terms of the matching number, Linear Algebra Appl. 589 (2020), 158–185.  https://doi.org/10.1016/j.laa.2019.12.014
[11] R.A. Horn and C.R. Johnson, Matrix Analysis, Cambridge University Press, 2012.
[12] R. Likaj, A. Shala, M. Mehmetaj, P. Hyseni, and X. Bajrami, Application of graph theory to find optimal paths for the transportation problem, IFAC Proceedings Volumes 46 (2013), no. 8, 235–240.  https://doi.org/10.3182/20130606-3-XK-4037.00031
[13] Y. Lu, L. Wang, and P. Xiao, Complex unit gain bicyclic graphs with rank 2, 3 or 4, Linear Algebra Appl. 523 (2017), 169–186.  https://doi.org/10.1016/j.laa.2017.02.031
[14] Y. Lu, L. Wang, and Q. Zhou, The rank of a complex unit gain graph in terms of the rank of its underlying graph, J. Comb. Optim. 38 (2019), no. 2, 570–588. https://doi.org/10.1007/s10878-019-00397-y
[15] Y. Lu and J. Wu, No signed graph with the nullity η(g,σ)=∥v(g)∥−2m(g)+2c(g)−1$, Linear Algebra Appl. 615 (2021), 175–193.  https://doi.org/10.1016/j.laa.2021.01.002
[16] X. Ma, D. Wong, and F. Tian, Nullity of a graph in terms of the dimension of cycle space and the number of pendant vertices, Discrete Appl. Math. 215 (2016), 171–176.  https://doi.org/10.1016/j.dam.2016.07.010
[17] A. Majeed and I. Rauf, Graph theory: A comprehensive survey about graph theory applications in computer science and social networks, Inventions 5 (2020), no. 1, Article number: 10.  https://doi.org/10.3390/inventions5010010
[18] R. Mehatari, M.R. Kannan, and A. Samanta, On the adjacency matrix of a complex unit gain graph, Linear Multilinear Algebra 70 (2022), no. 9, 1798–1813.  https://doi.org/10.1080/03081087.2020.1776672
[19] N. Reff, Spectral properties of complex unit gain graphs, Linear Algebra Appl. 436 (2012), no. 9, 3165–3176.  https://doi.org/10.1016/j.laa.2011.10.021
[20] A.B. Sadavare and R.V. Kulkarni, A review of application of graph theory for network, Int. J. Computer Sci. Info. Tec. 3 (2012), no. 6, 5296–5300.
[21] S.G. Srinivas, S. Vetrivel, and N.M. Elango, Applications of graph theory in computer science: An overview, Int. J. Eng. Sci. Technol. 2 (2010), no. 9, 4610–4621.
[22] Z. Stanić, Rank of signed cacti, Am. J. Comb. 2 (2023), 72–78.
[23] H. Tamura, K. Nakano, M. Sengoku, and S. Shinoda, On applications of graph/network theory to problems in communication systems, ECTI Trans. Comput. Inf. Technol. 5 (2011), no. 1, 15–21.
[24] L. Von Collatz and U. Sinogowitz, Spektren endlicher grafen: Wilhelm Blaschke zum 70. Geburtstag gewidmet, Abh. Math. Semin. Univ. Hambg. 21 (1957), no. 1, 63–77.  https://doi.org/10.1007/BF02941924
[25] L. Wang, X. Fang, and X. Geng, Graphs with nullity 2c(G)+p(G)−1, Discrete Math. 345 (2022), no. 5, Article ID: 112786.  https://doi.org/10.1016/j.disc.2021.112786
[26] Y. Wang, S.C. Gong, and Y.Z. Fan, On the determinant of the laplacian matrix of a complex unit gain graph, Discrete Math. 341 (2018), no. 1, 81–86.  https://doi.org/10.1016/j.disc.2017.07.003
[27] D. Wong, Q. Zhou, and F. Tian, Nullity and singularity of a graph in which every block is a cycle, Discrete Math. 345 (2022), no. 6, Article ID: 112851.  https://doi.org/10.1016/j.disc.2022.112851
[28] B. Xie, C. Qi, H. Ben, and W. Yu, The applications of graph theory in electric network, 2019 International Conference on Sensing, Diagnostics, Prognostics, and Control (SDPC), IEEE, 2019, pp. 780–784.
[29] G. Yu, H. Qu, and J. Tu, Inertia of complex unit gain graphs, Appl. Math. Comput. 265 (2015), 619–629. https://doi.org/10.1016/j.amc.2015.05.105
[30] T. Zaslavsky, Biased graphs. I. Bias, balance, and gains, J. Combin. Theory Ser. B 47 (1989), no. 1, 32–52. https://doi.org/10.1016/0095-8956(89)90063-4
Communications in Combinatorics and Optimization
Volume 10, Issue 2
June 2025
Pages 381-403

Files

Share

How to cite

Statistics