Tridiagonal matrices and spectral properties of some graph classes

Milica Andelić; Zhibin Du; Carlos M. da Fonseca; Slobodan K. Simić

Czechoslovak Mathematical Journal (2020)

  • Volume: 70, Issue: 4, page 1125-1138
  • ISSN: 0011-4642

Abstract

top
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.

How to cite

top

Andelić, Milica, et al. "Tridiagonal matrices and spectral properties of some graph classes." Czechoslovak Mathematical Journal 70.4 (2020): 1125-1138. <http://eudml.org/doc/297049>.

@article{Andelić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.},
author = {Andelić, Milica, Du, Zhibin, da Fonseca, Carlos M., Simić, Slobodan K.},
journal = {Czechoslovak Mathematical Journal},
keywords = {tridiagonal matrix; threshold graph; chain graph; eigenvalue-free interval},
language = {eng},
number = {4},
pages = {1125-1138},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Tridiagonal matrices and spectral properties of some graph classes},
url = {http://eudml.org/doc/297049},
volume = {70},
year = {2020},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 70
IS - 4
SP - 1125
EP - 1138
AB - 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.
LA - eng
KW - tridiagonal matrix; threshold graph; chain graph; eigenvalue-free interval
UR - http://eudml.org/doc/297049
ER -

References

top
  1. Aguilar, C. O., Lee, J.-Y., Piato, E., Schweitzer, B. J., 10.1016/j.laa.2018.07.028, Linear Algebra Appl. 557 (2018), 84-104. (2018) Zbl1396.05064MR3848263DOI10.1016/j.laa.2018.07.028
  2. Alazemi, A., elić, M. Anđ, Simić, S. K., 10.1016/j.laa.2016.04.030, Linear Algebra Appl. 505 (2016), 194-210. (2016) Zbl1338.05155MR3506491DOI10.1016/j.laa.2016.04.030
  3. elić, M. Anđ, Andrade, E., Cardoso, D. M., Fonseca, C. M. da, Simić, S. K., Tošić, D. V., 10.1016/j.laa.2015.06.010, Linear Algebra Appl. 483 (2015), 323-341. (2015) Zbl1319.05084MR3378905DOI10.1016/j.laa.2015.06.010
  4. elić, M. Anđ, Fonseca, C. M. da, 10.1007/s11117-010-0047-y, Positivity 15 (2011), 155-159 9999DOI99999 10.1007/s11117-010-0047-y . (2011) Zbl1216.15022MR2782752DOI10.1007/s11117-010-0047-y
  5. elić, M. Anđ, Ghorbani, E., Simić, S. K., 10.1016/j.dam.2019.02.040, Discrete Appl. Math. 269 (2019), 159-168. (2019) Zbl1421.05062MR4016594DOI10.1016/j.dam.2019.02.040
  6. elić, M. Anđ, Simić, S. K., Živković, D., Dolićanin, E. Ć., 10.1016/j.amc.2018.03.024, Appl. Math. Comput. 332 (2018), 329-337. (2018) Zbl1427.05127MR3788693DOI10.1016/j.amc.2018.03.024
  7. Cvetković, D., Rowlinson, P., Simić, S., 10.1017/CBO9780511801518, London Mathematical Society Student Texts 75, Cambridge University Press, Cambridge (2010). (2010) Zbl1211.05002MR2571608DOI10.1017/CBO9780511801518
  8. Fonseca, C. M. da, 10.1016/j.cam.2005.08.047, J. Comput. Appl. Math. 200 (2007), 283-286. (2007) Zbl1119.15012MR2276832DOI10.1016/j.cam.2005.08.047
  9. Ghorbani, E., 10.1016/j.laa.2019.08.028, Linear Algebra Appl. 583 (2019), 300-305. (2019) Zbl1426.05096MR4002158DOI10.1016/j.laa.2019.08.028
  10. Jacobs, D. P., Trevisan, V., Tura, F., 10.1016/j.laa.2014.09.043, Linear Algebra Appl. 465 (2015), 412-425. (2015) Zbl1302.05103MR3274686DOI10.1016/j.laa.2014.09.043
  11. Lazzarin, J., Márquez, O. F., Tura, F. C., 10.1016/j.laa.2018.09.033, Linear Algebra Appl. 560 (2019), 133-145. (2019) Zbl1401.05152MR3866549DOI10.1016/j.laa.2018.09.033
  12. Maybee, J. S., Olesky, D. D., Driessche, P. van den, Wiener, G., 10.1137/0610036, SIAM J. Matrix Anal. Appl. 10 (1989), 500-519. (1989) Zbl0701.05038MR1016799DOI10.1137/0610036

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.