zbMATH — the first resource for mathematics

Singular distance powers of circuits. (English) Zbl 1172.05040
Summary: A precise condition for the singularity of a circuit distance power \(C_n^{(d)}\) is derived. Namely, either \(n\) and \(d\) are not relatively prime or the order of 2 in \(d+1\) is strictly smaller than in \(n\). It is also shown that the simple eigenvalues of circuit distance powers are contained in \(\{-2,0,2d\}\), generalizing a well-known result for circuits. Further, the nullity of \(C_n^{(d)}\) is calculated.
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
15A18 Eigenvalues, singular values, and eigenvectors
Full Text: DOI
[1] Beineke L. W., and Wilson R. J., Selected topics in graph theory 1-3, Academic Press Inc., London, 1978. · Zbl 0423.00003
[2] Bevis, J. H., Domke, G. S., and Miller V. A., Ranks of trees and grid graphs, J. of Combinatorial Math. and Combinatorial Computing, 18 (1995), 109-119. · Zbl 0832.05027
[3] Biggs, N., Algebraic graph theory , Second Edition, Cambridge Mathematical Library, Cambridge University Press, 1993.
[4] Cvetković, D. M., Doob, M., and Sachs H., Spectra of graphs, Theory and application , Second Edition, VEB Deutscher Verlag der Wissenschaften, Berlin, 1982.
[5] Davis, P. J., Circulant matrices , John Wiley & Sons, New York-Chichester-Brisbane, 1979, A Wiley-Interscience Publication, Pure and Applied Mathematics. · Zbl 0418.15017
[6] Diestel, R, Graph theory , Graduate Texts in Mathematics, Vol. 173, Springer-Verlag, 1959.
[7] Fricke, G. H., Hedetniemi, S. T., Jacobs D. P., and Trevisan, V., Reducing the adjacency matrix of a tree, Electron. J. Linear Algebra, 1 (1996), 34-43. · Zbl 0886.05048
[8] Godsil, C., and Royle, G., Algebraic graph theory , Graduate Texts in Mathematics, Vol. 207, Springer, 2001. · Zbl 0968.05002
[9] Harary, F., Graph theory , Addison-Wesley Publishing Co., Reading, 1969. · Zbl 0182.57702
[10] Li, J., The determinant of a unicyclic graph’s neighborhood matrix, Linear Algebra Appl., 394 (2005), 201-216. · Zbl 1075.65065
[11] Sciriha, I. On the construction of graphs of nullity one, Discrete Math., 181 (1998), 193-211. · Zbl 0901.05069
[12] Xuezhong, T., and Liu B. On the nullity of unicyclic graphs, Linear Algebra Appl., 408 (2005), 212-220. · 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.