×

On the nullity of a graph with cut-points. (English) Zbl 1243.05147

Let \(G\) be a graph with the vertex set \(\{v_1,\ldots,v_n\}\). The adjacency matrix of \(G\) is an \(n\times n\) matrix \(A(G)\) whose \((i, j)\)-entry is 1 if \(v_i\) is adjacent to \(v_j\) and 0 otherwise. The nullity of \(G\) is the multiplicity of zero as an eigenvalue of \(A(G)\). It is shown that the set of the nullities of all graphs with exactly \(k\) induced cycles is \(\{0,1,\ldots,k+1\}\). Moreover, it is proved that for a graph \(G\) with \(k\) induced cycles if the nullity of the line graph of \(G\) is \(k+1\), then \(G\) has an even number of vertices.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A18 Eigenvalues, singular values, and eigenvectors
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chen, B.; Liu, B. L., On the nullity of graphs, Electron. J. Linear Algebra, 16, 60-67 (2007) · Zbl 1142.05336
[2] Collatz, L.; Sinogowitz, U., Spektren endlicher Grafen, Abh. Math. Sem. Univ. Hamburg, 21, 63-77 (1957) · Zbl 0077.36704
[3] Cvetković, D.; Doob, M.; Sachs, H., Spectra of Graphs (1980), Academic Press: Academic Press New York · Zbl 0458.05042
[4] Fiorini, S.; Gutman, I.; Sciriha, I., Trees with maximum nullity, Linear Algebra Appl., 397, 245-251 (2005) · Zbl 1068.05015
[5] Gong, S. C.; Fan, Y. Z.; Yin, Z. X., On the nullity of the graphs with pendent trees, Linear Algebra Appl., 433, 1374-1380 (2010) · Zbl 1194.05086
[6] Gutman, I.; Sciriha, I., On the nullity of line graphs of trees, Discrete Math., 232, 35-45 (2001) · Zbl 0971.05070
[7] Horn, R. A.; Johnson, C. R., Matrix Analysis (1985), Cambridge University Press · Zbl 0576.15001
[8] Hu, S.; Liu, B. L.; Tan, X. Z., On the nullity of bicyclic graphs, Linear Algebra Appl., 429, 1387-1391 (2008) · Zbl 1144.05319
[9] Li, W.; Chang, A., Describing the nonsingular unicyclic graph, J. Math. Study, 4, 442-445 (2007) · Zbl 1150.05037
[10] Li, S. C., On the nullity of graphs with pendent vertices, Linear Algebra Appl., 429, 1619-1628 (2008) · Zbl 1144.05321
[11] Longuet-Higgins, H. C., Resonance structures and MO in unsaturated hydrocarbons, J. Chem. Phys., 18, 265-274 (1950)
[12] Marino, M. C.; Sciriha, I.; Simić, S. K.; Tošić, D. V., More about singular line graphs of trees, Publ. Inst. Math. (N.S.), 79, 93, 1-12 (2006) · Zbl 1121.05073
[13] Nath, M.; Sarma, B. K., On the null-spaces of acyclic and unicyclic singular graphs, Linear Algebra Appl., 427, 42-54 (2007) · Zbl 1124.05065
[14] Sciriha, I., On the construction of graphs of nullity one, Discrete Math., 181, 193-211 (1998) · Zbl 0901.05069
[15] Sciriha, I., On singular line graphs of trees, Congr. Numer., 135, 73-91 (1998) · Zbl 0952.05047
[16] Tan, X. Z.; Liu, B. L., On the nullity of unicyclic graphs, Linear Algebra Appl., 408, 212-220 (2005) · Zbl 1073.05044
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.