The singularity of two kinds of tricyclic graphs

Haicheng Ma; Xiaojie You; Shuli Li; Haicheng Ma; Xiaojie You; Shuli Li

doi:10.3934/math.2023448

AIMS Mathematics

2023, Volume 8, Issue 4: 8949-8963. doi: 10.3934/math.2023448

Previous Article Next Article

Research article

The singularity of two kinds of tricyclic graphs

1.
School of Mathematics and Statistics, Qinghai Nationalities University, Xining 810007, China
2.
School of Mathematics and Computer Science, Quanzhou Normal University, Quanzhou 362000, China
3.
Key Laboratory of Intelligent Computing and Information Processing, Fujian Province University, Quanzhou 362000, China

Received: 20 October 2022 Revised: 25 January 2023 Accepted: 28 January 2023 Published: 09 February 2023
MSC : 05C50

Let $ G $ be a finite simple graph and let $ A(G) $ be its adjacency matrix. Then $ G $ is $ singular $ if $ A(G) $ is singular. Suppose $ P_{b_{1}}, P_{b_{2}}, P_{b_{3}} $ are three paths with disjoint vertices, where $ b_i\geq 2 (i = 1, 2, 3) $, and at most one of them is 2. Coalescing together one of the two end vertices of each of the three paths, and coalescing together the other end vertex of each of the three paths, the resulting graph is called the $ \theta $-graph, denoted by $ \theta(b_{1}, b_{2}, b_{3}) $. Let $ \alpha(a, b_{1}, b_{2}, b_{3}, s) $ be the graph obtained by merging one end of the path $ P_{s} $ with one vertex of a cycle $ C_{a} $, and merging the other end of the path $ P_{s} $ with one vertex of $ \theta(b_{1}, b_{2}, b_{3}) $ of degree 3. If $ s = 1 $, denote $ \beta(a, b_{1}, b_{2}, b_{3}) = \alpha(a, b_{1}, b_{2}, b_{3}, 1) $. In this paper, we give the necessity and sufficiency condition for the singularity of $ \alpha(a, b_{1}, b_{2}, b_{3}, s) $ and $ \beta(a, b_{1}, b_{2}, b_{3}) $, and we also prove that the probability that any given $ \alpha(a, b_{1}, b_{2}, b_{3}, s) $ is a singular graph is equal to $ \frac{35}{64} $, the probability that any given $ \beta(a, b_{1}, b_{2}, b_{3}) $ is a singular graph is equal to $ \frac{9}{16} $. From our main results we can conclude that such a $ \alpha(a, b_{1}, b_{2}, b_{3}, s) $ graph ($ \beta(a, b_{1}, b_{2}, b_{3}) $ graph) is singular if $ 4|a $ or three $ b_i (i = 1, 2, 3) $ are all odd numbers or exactly two of the three $ b_i (i = 1, 2, 3) $ are odd numbers and the length of the cycle formed by the two odd paths in $ \alpha(a, b_{1}, b_{2}, b_{3}, s) $ graph ($ \beta(a, b_{1}, b_{2}, b_{3}) $ graph) is a multiple of 4. The theoretical probability of these graphs being singular is more than half.
- adjacency matrix,
- singular graphs,
- probability,
- nullity
Citation: Haicheng Ma, Xiaojie You, Shuli Li. The singularity of two kinds of tricyclic graphs[J]. AIMS Mathematics, 2023, 8(4): 8949-8963. doi: 10.3934/math.2023448

Related Papers:

Abstract

Let $ G $ be a finite simple graph and let $ A(G) $ be its adjacency matrix. Then $ G $ is $ singular $ if $ A(G) $ is singular. Suppose $ P_{b_{1}}, P_{b_{2}}, P_{b_{3}} $ are three paths with disjoint vertices, where $ b_i\geq 2 (i = 1, 2, 3) $, and at most one of them is 2. Coalescing together one of the two end vertices of each of the three paths, and coalescing together the other end vertex of each of the three paths, the resulting graph is called the $ \theta $-graph, denoted by $ \theta(b_{1}, b_{2}, b_{3}) $. Let $ \alpha(a, b_{1}, b_{2}, b_{3}, s) $ be the graph obtained by merging one end of the path $ P_{s} $ with one vertex of a cycle $ C_{a} $, and merging the other end of the path $ P_{s} $ with one vertex of $ \theta(b_{1}, b_{2}, b_{3}) $ of degree 3. If $ s = 1 $, denote $ \beta(a, b_{1}, b_{2}, b_{3}) = \alpha(a, b_{1}, b_{2}, b_{3}, 1) $. In this paper, we give the necessity and sufficiency condition for the singularity of $ \alpha(a, b_{1}, b_{2}, b_{3}, s) $ and $ \beta(a, b_{1}, b_{2}, b_{3}) $, and we also prove that the probability that any given $ \alpha(a, b_{1}, b_{2}, b_{3}, s) $ is a singular graph is equal to $ \frac{35}{64} $, the probability that any given $ \beta(a, b_{1}, b_{2}, b_{3}) $ is a singular graph is equal to $ \frac{9}{16} $. From our main results we can conclude that such a $ \alpha(a, b_{1}, b_{2}, b_{3}, s) $ graph ($ \beta(a, b_{1}, b_{2}, b_{3}) $ graph) is singular if $ 4|a $ or three $ b_i (i = 1, 2, 3) $ are all odd numbers or exactly two of the three $ b_i (i = 1, 2, 3) $ are odd numbers and the length of the cycle formed by the two odd paths in $ \alpha(a, b_{1}, b_{2}, b_{3}, s) $ graph ($ \beta(a, b_{1}, b_{2}, b_{3}) $ graph) is a multiple of 4. The theoretical probability of these graphs being singular is more than half.

References

[1]	F. Ashraf, H. Bamdad, A note on graphs with zero nullity, MATCH Commun. Math. Comput. Chem., 60 (2008), 15–19.
[2]	A. S. AL-Tarimshawy, Singular graphs, arXiv, 2018. https://doi.org/10.48550/arXiv.1806.07786
[3]	M. Brown, J. W. Kennedy, B. Servatius, Graph singularity, Graph Theory Notes, 25 (1993), 23–32.
[4]	B. Cheng, B. Liu, On the nullity of graphs, Electron. J. Linear Algebra, 16 (2007), 60–67. https://doi.org/10.13001/1081-3810.1182 doi: 10.13001/1081-3810.1182
[5]	D. Cvetković, M. Doob, H. Sachs, Spectra of graphs-theory and application, Academic Press, 1980.
[6]	D. Cvetković, I. Gutman, The algebraic multiplicity of the number zero in the spectrum of a bipartite graph, Mat. Ves., 9 (1972), 141–150.
[7]	D. Cvetković, I. Gutman, N. Trinajstic, Graphical studies on the relations between the structure and reactivity of conjugated system: the role of non-bonding molecular orbitals, J. Mol. Struct., 28 (1975), 289–303. https://doi.org/10.1016/0022-2860(75)80099-8 doi: 10.1016/0022-2860(75)80099-8
[8]	L. Collatz, U. Sinogowitz, Spektren endlicher grafen, Abh. Math. Semin. Univer. Hamburg, 21 (1957), 63–77. https://doi.org/10.1007/BF02941924 doi: 10.1007/BF02941924
[9]	Y. Z. Fan, K. S. Qian, On the nullity of bipartite graphs, Linear Algebra Appl., 430 (2009), 2943–2949. https://doi.org/10.1016/j.laa.2009.01.007 doi: 10.1016/j.laa.2009.01.007
[10]	I. Gutman, B. Borovićanin, Nullity of graphs: an updated survey, Zb. Rad., 14 (2011), 137–154.
[11]	A. Graovac, I. Gutman, N. Trinajstić, Topological approach to the chemistry of conjugated molecules, Springer, 1977.
[12]	I. Gutman, I. Sciriha, On the nullity of line graphs of trees, Discrete Math., 232 (2001), 35–45. https://doi.org/10.1016/S0012-365X(00)00187-4 doi: 10.1016/S0012-365X(00)00187-4
[13]	J. M. Guo, W. G. Yan, Y. N. Yeh, On the nullity and the matching number of unicyclic graphs, Linear Algebra Appl., 431 (2009), 1293–1301. https://doi.org/10.1016/j.laa.2009.04.026 doi: 10.1016/j.laa.2009.04.026
[14]	S. Hu, X. Tan, B. Liu, On the nullity of bicyclic graphs, Linear Algebra Appl., 429 (2008), 1387–1391. https://doi.org/10.1016/j.laa.2007.12.007 doi: 10.1016/j.laa.2007.12.007
[15]	W. Li, A. Chang, On the trees with maximum nullity, MATCH Commun. Math. Comput. Chem., 56 (2006), 501–508.
[16]	J. M$\ddot{u}$ller, M. Neunh$\ddot{o}$fer, Some computations regarding Foulkes' conjecture, Exp. Math., 14 (2005), 277–283. https://doi.org/10.1080/10586458.2005.10128928 doi: 10.1080/10586458.2005.10128928
[17]	M. Nath, B. K. Sarma, On the null spaces of acyclic and unicyclic singular graphs, Linear Algebra Appl., 427 (2007), 42–54. https://doi.org/10.1016/j.laa.2007.06.017 doi: 10.1016/j.laa.2007.06.017
[18]	G. R. Omidi, On the nullity of bipartite graphs, Graphs Combin., 25 (2009), 111–114. https://doi.org/10.1007/s00373-008-0825-5 doi: 10.1007/s00373-008-0825-5
[19]	L. Pogliani, From molecular connectivity indices to semiempirical connectivity terms: recent trends in graph theoretical descriptors, Chem. Rev., 100 (2000), 3827–3858. https://doi.org/10.1021/cr0004456 doi: 10.1021/cr0004456
[20]	M. Randić, Aromaticity of polycyclic conjugated hydrocarbons, Chem. Rev., 103 (2003), 3449–3605. https://doi.org/10.1021/cr9903656 doi: 10.1021/cr9903656
[21]	I. Sciriha, On singular line graphs of trees, Congr. Numer., 135 (1998), 73–91.
[22]	I. Sciriha, On the construction of graphs of nullity one, Discrete Math., 181 (1998), 193–211. https://doi.org/10.1016/S0012-365X(97)00036-8 doi: 10.1016/S0012-365X(97)00036-8
[23]	I. Sciriha, A characterization of singular graphs, Electron. J. Linear Algebra, 16 (2007), 451–462. https://doi.org/10.13001/1081-3810.1215 doi: 10.13001/1081-3810.1215
[24]	I. Sciriha, P. W. Fowler, On nut and core singular fullerenes, Discrete Math., 308 (2008), 267–276. https://doi.org/10.1016/j.disc.2006.11.040 doi: 10.1016/j.disc.2006.11.040
[25]	Y. Shang, Further results on distance Estrada index of random graphs, Bull. Malays. Math. Sci. Soc., 41 (2018), 531–544. https://doi.org/10.1007/s40840-016-0306-6 doi: 10.1007/s40840-016-0306-6
[26]	M. Sharma, R. K. Nath, Y. Shang, On $g$-noncommuting graph of a finite group relative to its subgroups, Mathematics, 9 (2021), 3147. https://doi.org/10.3390/math9233147 doi: 10.3390/math9233147
[27]	J. Siemons, A. Zalesski, Remarks on singular Cayley graphs and vanishing elements of simple groups, J. Algebraic Combin., 50 (2019), 379–401. https://doi.org/10.1007/s10801-018-0860-0 doi: 10.1007/s10801-018-0860-0
[28]	A. Sltan, A. AL-Tarimshawy, J. Siemons, Singular graphs with dihedral group action, Discrete Math., 344 (2021), 112119. https://doi.org/10.1016/j.disc.2020.112119 doi: 10.1016/j.disc.2020.112119
[29]	X. Tang, B. Liu, On the nullity of unicyclic graphs, Linear Algebra Appl., 408 (2005), 212–220. https://doi.org/10.1016/j.laa.2005.06.012 doi: 10.1016/j.laa.2005.06.012
[30]	Z. Wang, Y. Mao, K. C. Das, Y. Shang, Nordhaus-Gaddum-type results for the Steiner Gutman index of graphs, Symmetry, 12 (2020), 1711. https://doi.org/10.3390/sym12101711 doi: 10.3390/sym12101711

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)