Geodesic
Tridiagonal matrices and spectral properties of some graph classes
Czechoslovak Mathematical Journal, Tome 70 (2020) no. 4, pp. 1125-1138
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/CMJ.2020.0182-19
Classification : 05C50
Keywords: tridiagonal matrix; threshold graph; chain graph; eigenvalue-free interval 
@article{10_21136_CMJ_2020_0182_19,
     author = {Andeli\'c, Milica and Du, Zhibin and da Fonseca, Carlos M. and Simi\'c, Slobodan K.},
     title = {Tridiagonal matrices and spectral properties of some graph classes},
     journal = {Czechoslovak Mathematical Journal},
     pages = {1125--1138},
     year = {2020},
     volume = {70},
     number = {4},
     doi = {10.21136/CMJ.2020.0182-19},
     mrnumber = {4181801},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2020.0182-19/}
}
TY  - JOUR
AU  - Andelić, Milica
AU  - Du, Zhibin
AU  - da Fonseca, Carlos M.
AU  - Simić, Slobodan K.
TI  - Tridiagonal matrices and spectral properties of some graph classes
JO  - Czechoslovak Mathematical Journal
PY  - 2020
SP  - 1125
EP  - 1138
VL  - 70
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2020.0182-19/
DO  - 10.21136/CMJ.2020.0182-19
LA  - en
ID  - 10_21136_CMJ_2020_0182_19
ER  - 
%0 Journal Article
%A Andelić, Milica
%A Du, Zhibin
%A da Fonseca, Carlos M.
%A Simić, Slobodan K.
%T Tridiagonal matrices and spectral properties of some graph classes
%J Czechoslovak Mathematical Journal
%D 2020
%P 1125-1138
%V 70
%N 4
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2020.0182-19/
%R 10.21136/CMJ.2020.0182-19
%G en
%F 10_21136_CMJ_2020_0182_19
Andelić, Milica; Du, Zhibin; da Fonseca, Carlos M.; Simić, Slobodan K. Tridiagonal matrices and spectral properties of some graph classes. Czechoslovak Mathematical Journal, Tome 70 (2020) no. 4, pp. 1125-1138. doi: 10.21136/CMJ.2020.0182-19

[1] Aguilar, C. O., Lee, J.-Y., Piato, E., Schweitzer, B. J.: Spectral characterizations of anti-regular graphs. Linear Algebra Appl. 557 (2018), 84-104. | DOI | MR | JFM

[2] Alazemi, A., elić, M. Anđ, Simić, S. K.: Eigenvalue location for chain graphs. Linear Algebra Appl. 505 (2016), 194-210. | DOI | MR | JFM

[3] 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. | DOI | MR | JFM

[4] 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. | DOI | MR | JFM

[5] elić, M. Anđ, Ghorbani, E., Simić, S. K.: Vertex types in threshold and chain graphs. Discrete Appl. Math. 269 (2019), 159-168. | DOI | MR | JFM

[6] 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. | DOI | MR | JFM

[7] 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). | DOI | MR | JFM

[8] Fonseca, C. M. da: On the eigenvalues of some tridiagonal matrices. J. Comput. Appl. Math. 200 (2007), 283-286. | DOI | MR | JFM

[9] Ghorbani, E.: Eigenvalue-free interval for threshold graphs. Linear Algebra Appl. 583 (2019), 300-305. | DOI | MR | JFM

[10] Jacobs, D. P., Trevisan, V., Tura, F.: Eigenvalues and energy in threshold graphs. Linear Algebra Appl. 465 (2015), 412-425. | DOI | MR | JFM

[11] Lazzarin, J., Márquez, O. F., Tura, F. C.: No threshold graphs are cospectral. Linear Algebra Appl. 560 (2019), 133-145. | DOI | MR | JFM

[12] 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. | DOI | MR | JFM

Cité par Sources :