zbMATH — the first resource for mathematics

Tridiagonal matrices and spectral properties of some graph classes. (English) Zbl 07285984
Summary: A graph is called a chain graph if it is bipartite and the neighbourhoods of the vertices in each colour class form a chain with respect to inclusion. In this paper we give an explicit formula for the characteristic polynomial of any chain graph and we show that it can be expressed using the determinant of a particular tridiagonal matrix. Then this fact is applied to show that in a certain interval a chain graph does not have any nonzero eigenvalue. A similar result is provided for threshold graphs.

MSC:
 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text:
References:
  Aguilar, C. O.; Lee, J.-Y.; Piato, E.; Schweitzer, B. J., Spectral characterizations of anti-regular graphs, Linear Algebra Appl. 557 (2018), 84-104  Alazemi, A.; elić, M. Anđ; Simić, S. K., Eigenvalue location for chain graphs, Linear Algebra Appl. 505 (2016), 194-210  elić, M. Anđ; Andrade, E.; Cardoso, D. M.; Fonseca, C. M. da; Simić, S. K.; Tošić, D. V., Some new considerations about double nested graphs, Linear Algebra Appl. 483 (2015), 323-341  elić, M. Anđ; Fonseca, C. M. da, Sufficient conditions for positive definiteness of tridiagonal matrices revisited, Positivity 15 (2011), 155-159 \99999DOI99999 10.1007/s11117-010-0047-y \goodbreak  elić, M. Anđ; Ghorbani, E.; Simić, S. K., Vertex types in threshold and chain graphs, Discrete Appl. Math. 269 (2019), 159-168  elić, M. Anđ; Simić, S. K.; Živković, D.; Dolićanin, E. Ć., Fast algorithms for computing the characteristic polynomial of threshold and chain graphs, Appl. Math. Comput. 332 (2018), 329-337  Cvetković, D.; Rowlinson, P.; Simić, S., An Introduction to the Theory of Graph Spectra, London Mathematical Society Student Texts 75, Cambridge University Press, Cambridge (2010)  Fonseca, C. M. da, On the eigenvalues of some tridiagonal matrices, J. Comput. Appl. Math. 200 (2007), 283-286  Ghorbani, E., Eigenvalue-free interval for threshold graphs, Linear Algebra Appl. 583 (2019), 300-305  Jacobs, D. P.; Trevisan, V.; Tura, F., Eigenvalues and energy in threshold graphs, Linear Algebra Appl. 465 (2015), 412-425  Lazzarin, J.; Márquez, O. F.; Tura, F. C., No threshold graphs are cospectral, Linear Algebra Appl. 560 (2019), 133-145  Maybee, J. S.; Olesky, D. D.; Driessche, P. van den; Wiener, G., Matrices, digraphs, and determinants, SIAM J. Matrix Anal. Appl. 10 (1989), 500-519
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.