On the nullity of cycle-spliced $\mathbb{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 $\Phi=(G,\varphi)$ be a $\mathbb{T}$-gain (or complex unit gain) graph and $A(\Phi)$ be its adjacency matrix. The nullity of $\Phi$, denoted by $\eta(\Phi)$, is the multiplicity of zero as an eigenvalue of $A(\Phi)$, and the cyclomatic number of $\Phi$ is defined by $c(\Phi)=e(\Phi)-n(\Phi)+\kappa(\Phi)$, where $n(\Phi)$, $e(\Phi)$ and $\kappa(\Phi)$ are the number of vertices, edges and connected components of $\Phi$, 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 $\mathbb{T}$-gain graphs. Given a cycle-spliced $\mathbb{T}$-gain graph $\Phi$ with $c(\Phi)$ cycles, we prove that $0 \leq \eta(\Phi)\leq c(\Phi)+1$. Moreover, we show that there is no cycle-spliced  $\mathbb{T}$-gain graph $\Phi$ of any order with $\eta(\Phi)=c(\Phi)$ whenever there are no odd cycles whose gain has real part $0$. We give examples of cycle-spliced  $\mathbb{T}$-gain graphs whose nullity equals the cyclomatic number, and we show some properties of those graphs $\Phi$ such that $\eta(\Phi)=c(\Phi)-\varepsilon$, $\varepsilon \in \{0,1\}$. A characterization is given in case $\eta(\Phi)=c(\Phi)$ when $\Phi$ is obtained by identifying a unique common vertex of $2$ cycle-spliced $\mathbb{T}$-gain graphs $\Phi_1$ and $\Phi_2$. Finally, we compute the nullity of all $\mathbb{T}$-gain graphs $\Phi$ with $c(\Phi)=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\alpha(\gamma)$-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 $\eta(g, \sigma) = ∥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