Non-Singular Trees, Unicyclic Graphs and Bicyclic Graphs
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.
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

Top