Institute of Mathematics

of the Czech Academy of Sciences
 
 
 
 

Czechoslovak Mathematical Journal, Vol. 70, No. 4, pp. 1125-1138, 2020

Tridiagonal matrices and spectral properties of some graph classes

Milica Anđelić, Zhibin Du, Carlos M. da Fonseca, Slobodan K. Simić

Received April 17, 2019.   Published online April 23, 2020.
Abstract:  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.
Keywords:  tridiagonal matrix; threshold graph; chain graph; eigenvalue-free interval
Classification MSC:  05C50
DOI:  10.21136/CMJ.2020.0182-19
PDF available at:  Springer   Institute of Mathematics CAS   Digital Mathematics Library
References:
[1] C. O. Aguilar, J.-Y. Lee, E. Piato, B. J. Schweitzer: Spectral characterizations of anti-regular graphs. Linear Algebra Appl. 557 (2018), 84-104. DOI 10.1016/j.laa.2018.07.028 | MR 3848263 | Zbl 1396.05064
[2] A. Alazemi, M. Anđelić, S. K. Simić: Eigenvalue location for chain graphs. Linear Algebra Appl. 505 (2016), 194-210. DOI 10.1016/j.laa.2016.04.030 | MR 3506491 | Zbl 1338.05155
[3] M. Anđelić, E. Andrade, D. M. Cardoso, C. M. da Fonseca, S. K. Simić, D. V. Tošić: Some new considerations about double nested graphs. Linear Algebra Appl. 483 (2015), 323-341. DOI 10.1016/j.laa.2015.06.010 | MR 3378905 | Zbl 1319.05084
[4] M. Anđelić, C. M. da Fonseca: Sufficient conditions for positive definiteness of tridiagonal matrices revisited. Positivity 15 (2011), 155-159. DOI 10.1007/s11117-010-0047-y | MR 2782752 | Zbl 1216.15022
[5] M. Anđelić, E. Ghorbani, S. K. Simić: Vertex types in threshold and chain graphs. Discrete Appl. Math. 269 (2019), 159-168. DOI 10.1016/j.dam.2019.02.040 | MR 4016594 | Zbl 1421.05062
[6] M. Anđelić, S. K. Simić, D. Živković, E. Ć. Dolićanin: Fast algorithms for computing the characteristic polynomial of threshold and chain graphs. Appl. Math. Comput. 332 (2018), 329-337. DOI 10.1016/j.amc.2018.03.024 | MR 3788693 | Zbl 1427.05127
[7] D. Cvetković, P. Rowlinson, S. Simić: An Introduction to the Theory of Graph Spectra. London Mathematical Society Student Texts 75, Cambridge University Press, Cambridge (2010). DOI 10.1017/CBO9780511801518 | MR 2571608 | Zbl 1211.05002
[8] C. M. da Fonseca: On the eigenvalues of some tridiagonal matrices. J. Comput. Appl. Math. 200 (2007), 283-286. DOI 10.1016/j.cam.2005.08.047 | MR 2276832 | Zbl 1119.15012
[9] E. Ghorbani: Eigenvalue-free interval for threshold graphs. Linear Algebra Appl. 583 (2019), 300-305. DOI 10.1016/j.laa.2019.08.028 | MR 4002158 | Zbl 1426.05096
[10] D. P. Jacobs, V. Trevisan, F. Tura: Eigenvalues and energy in threshold graphs. Linear Algebra Appl. 465 (2015), 412-425. DOI 10.1016/j.laa.2014.09.043 | MR 3274686 | Zbl 1302.05103
[11] J. Lazzarin, O. F. Márquez, F. C. Tura: No threshold graphs are cospectral. Linear Algebra Appl. 560 (2019), 133-145. DOI 10.1016/j.laa.2018.09.033 | MR 3866549 | Zbl 1401.05152
[12] J. S. Maybee, D. D. Olesky, P. van den Driessche, G. Wiener: Matrices, digraphs, and determinants. SIAM J. Matrix Anal. Appl. 10 (1989), 500-519. DOI 10.1137/0610036 | MR 1016799 | Zbl 0701.05038
Affiliations:   Milica Anđelić (corresponding author), Department of Mathematics, Faculty of Science, Kuwait University, P.O. Box 5969, Safat 13060, Kuwait, e-mail: milica@sci.kuniv.edu.kw; Zhibin Du, School of Software, South China Normal University, Foshan, Guangdong 528225, P. R. China, School of Mathematics and Statistics, Zhaoqing University, Zhaoqing 526061, Guangdong, P. R. China, e-mail: zhibindu@126.com; Carlos M. da Fonseca, Kuwait College of Science and Technology, Doha District, Block 4, P.O. Box 27235, Safat 13133, Kuwait, e-mail: c.dafonseca@kcst.edu.kw, University of Primorska, FAMNIT, Glagoljsaška 8, 6000 Koper, Slovenia, e-mail: carlos.dafonseca@famnit.upr.si; Slobodan K. Simić, Mathematical Institute SANU, Kneza Mihaila 36, 11 000 Belgrade, Serbia, e-mail: sksimic@mi.sanu.ac.rs
Springer subscribers can access the papers on Springer website.
[List of online first articles] [Contents of Czechoslovak Mathematical Journal] [Full text of the older issues of Czechoslovak Mathematical Journal at DML-CZ]
© Institute of Mathematics CAS, 2024



 
PDF available at:


Springer
for subscribers
···

Institute of Mathematics CAS
free access
···

Digital Mathematics Library
free access