| Title:
|
Tridiagonal matrices and spectral properties of some graph classes (English) |
| Author:
|
Andelić, Milica |
| Author:
|
Du, Zhibin |
| Author:
|
da Fonseca, Carlos M. |
| Author:
|
Simić, Slobodan K. |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
70 |
| Issue:
|
4 |
| Year:
|
2020 |
| Pages:
|
1125-1138 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
tridiagonal matrix |
| Keyword:
|
threshold graph |
| Keyword:
|
chain graph |
| Keyword:
|
eigenvalue-free interval |
| MSC:
|
05C50 |
| idZBL:
|
07285984 |
| idMR:
|
MR4181801 |
| DOI:
|
10.21136/CMJ.2020.0182-19 |
| . |
| Date available:
|
2020-11-18T09:48:34Z |
| Last updated:
|
2023-01-02 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/148416 |
| . |
| Reference:
|
[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. Zbl 1396.05064, MR 3848263, 10.1016/j.laa.2018.07.028 |
| Reference:
|
[2] Alazemi, A., elić, M. Anđ, Simić, S. K.: Eigenvalue location for chain graphs.Linear Algebra Appl. 505 (2016), 194-210. Zbl 1338.05155, MR 3506491, 10.1016/j.laa.2016.04.030 |
| Reference:
|
[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. Zbl 1319.05084, MR 3378905, 10.1016/j.laa.2015.06.010 |
| Reference:
|
[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. Zbl 1216.15022, MR 2782752, 10.1007/s11117-010-0047-y |
| Reference:
|
[5] elić, M. Anđ, Ghorbani, E., Simić, S. K.: Vertex types in threshold and chain graphs.Discrete Appl. Math. 269 (2019), 159-168. Zbl 1421.05062, MR 4016594, 10.1016/j.dam.2019.02.040 |
| Reference:
|
[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. Zbl 1427.05127, MR 3788693, 10.1016/j.amc.2018.03.024 |
| Reference:
|
[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). Zbl 1211.05002, MR 2571608, 10.1017/CBO9780511801518 |
| Reference:
|
[8] Fonseca, C. M. da: On the eigenvalues of some tridiagonal matrices.J. Comput. Appl. Math. 200 (2007), 283-286. Zbl 1119.15012, MR 2276832, 10.1016/j.cam.2005.08.047 |
| Reference:
|
[9] Ghorbani, E.: Eigenvalue-free interval for threshold graphs.Linear Algebra Appl. 583 (2019), 300-305. Zbl 1426.05096, MR 4002158, 10.1016/j.laa.2019.08.028 |
| Reference:
|
[10] Jacobs, D. P., Trevisan, V., Tura, F.: Eigenvalues and energy in threshold graphs.Linear Algebra Appl. 465 (2015), 412-425. Zbl 1302.05103, MR 3274686, 10.1016/j.laa.2014.09.043 |
| Reference:
|
[11] Lazzarin, J., Márquez, O. F., Tura, F. C.: No threshold graphs are cospectral.Linear Algebra Appl. 560 (2019), 133-145. Zbl 1401.05152, MR 3866549, 10.1016/j.laa.2018.09.033 |
| Reference:
|
[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. Zbl 0701.05038, MR 1016799, 10.1137/0610036 |
| . |
