Non-Singular Trees, Unicyclic Graphs and Bicyclic Graphs

Haicheng  Ma; Danyang  Li; Chengling  Xie

doi:10.4236/am.2020.111001

Haicheng Ma^*, Danyang Li, Chengling Xie

Abstract: We called graph G non-singular if adjacency matrix A (G) of G is non-singular. A connected graph with n vertices and n-1, n and n+1 edges are called the tree, the unicyclic graph and the bicyclic graph. Respectively, as we all know, each connected bicyclic graph must contain ∞(a,s,b) or θ(p,l,q) as the induced subgraph. In this paper, by using three graph transformations which do not change the singularity of the graph, the non-singular trees, unicyclic graphs and bicyclic graphs are obtained.

Keywords: Adjacency Matrix, Non-Singular, Rank, Nullity

Cite this paper: Ma, H. , Li, D. and Xie, C. (2020) Non-Singular Trees, Unicyclic Graphs and Bicyclic Graphs. Applied Mathematics, 11, 1-7. doi: 10.4236/am.2020.111001.

References

[1] Cvetković, D., Doob, M. and Sachs, H. (1980) Spectra of Graphs-Theory and Application. Academic Press, New York.

[2] Collatz, L. and Sinogowitz, U. (1957) Spektren endlicher Grafen. Abhandlungen aus dem Mathematischen Seminar der Universitat Hamburg, 21, 63-77.
https://doi.org/10.1007/BF02941924

[3] Sciriha, I. and Fowler, P.W. (2008) On Nut and Core Singular Fullerenes. Discrete Mathematics, 308, 267-276.
https://doi.org/10.1016/j.disc.2006.11.040

[4] Brown, M., Kennedy, J.W. and Servatius, B. (1993) Graph Singularity. Graph Theory Notes of New York, 25, 23-32.

[5] Sciriha, I. (1998) On Singular Line Graphs of Trees. Congressus Numerantium, 135, 73-91.

[6] Sciriha, I. (2007) A Characterization of Singular Graphs. The Electronic Journal of Linear Algebra, 16, 451-462.
https://doi.org/10.13001/1081-3810.1215

[7] Ashraf, F. and Bamdad, H. (2008) A Note on Graphs with Zero Nullity. MATCH Communications in Mathematical and in Computer Chemistry, 60, 15-19.

[8] Fan, Y.Z. and Qian, K.S. (2009) On the Nullity of Bipartite Graphs. Linear Algebra and Its Applications, 430, 2943-2949.
https://doi.org/10.1016/j.laa.2009.01.007

[9] Guo, J.M., Yan, W. and Yeh, Y.N. (2009) On the Nullity and the Matching Number of Unicyclic Graphs. Linear Algebra and Its Applications, 431, 1293-1301.
https://doi.org/10.1016/j.laa.2009.04.026

[10] Tang, X. and Liu, B. (2005) On the Nullity of Unicyclic Graphs. Linear Algebra and Its Applications, 408, 212-220.
https://doi.org/10.1016/j.laa.2005.06.012

[11] Hu, S., Tan, X. and Liu, B. (2008) On the Nullity of Bicyclic Graphs. Linear Algebra and Its Applications, 429, 1387-1391.
https://doi.org/10.1016/j.laa.2007.12.007

[12] Chang, A. (2006) On the Trees with Maximum Nullity. MATCH Communications in Mathematical and in Computer Chemistry, 56, 501-508.

[13] Omidi, G.R. (2009) On the Nullity of Bipartite Graphs. Graphs and Combinatorics, 25, 111-114.
https://doi.org/10.1007/s00373-008-0825-5

[14] Cheng, B. and Liu, B. (2007) On the Nullity of Graphs. The Electronic Journal of Linear Algebra, 16, 60-67.
https://doi.org/10.13001/1081-3810.1182

[15] Marcus, M. and Minc, H. (1964) A Survey of Matrix Theory and Matrix Inequalities. Allyn and Bacon Inc., Boston.

[16] Ma, H., Yang, W. and Li, S. (2013) Positive and Negative Inertia Index of a Graph. Linear Algebra and Its Applications, 438, 331-341.
https://doi.org/10.1016/j.laa.2012.07.014