Coalescing Fiedler and core vertices

Didar A. Ali; John Baptist Gauci; Irene Sciriha; Khidir R. Sharaf

Czechoslovak Mathematical Journal (2016)

  • Volume: 66, Issue: 3, page 971-985
  • ISSN: 0011-4642

Abstract

top
The nullity of a graph G is the multiplicity of zero as an eigenvalue in the spectrum of its adjacency matrix. From the interlacing theorem, derived from Cauchy’s inequalities for matrices, a vertex of a graph can be a core vertex if, on deleting the vertex, the nullity decreases, or a Fiedler vertex, otherwise. We adopt a graph theoretical approach to determine conditions required for the identification of a pair of prescribed types of root vertices of two graphs to form a cut-vertex of unique type in the coalescence. Moreover, the nullity of subgraphs obtained by perturbations of the coalescence G is determined relative to the nullity of G . This has direct applications in spectral graph theory as well as in the construction of certain ipso-connected nano-molecular insulators.

How to cite

top

Ali, Didar A., et al. "Coalescing Fiedler and core vertices." Czechoslovak Mathematical Journal 66.3 (2016): 971-985. <http://eudml.org/doc/286823>.

@article{Ali2016,
abstract = {The nullity of a graph $G$ is the multiplicity of zero as an eigenvalue in the spectrum of its adjacency matrix. From the interlacing theorem, derived from Cauchy’s inequalities for matrices, a vertex of a graph can be a core vertex if, on deleting the vertex, the nullity decreases, or a Fiedler vertex, otherwise. We adopt a graph theoretical approach to determine conditions required for the identification of a pair of prescribed types of root vertices of two graphs to form a cut-vertex of unique type in the coalescence. Moreover, the nullity of subgraphs obtained by perturbations of the coalescence $G$ is determined relative to the nullity of $G$. This has direct applications in spectral graph theory as well as in the construction of certain ipso-connected nano-molecular insulators.},
author = {Ali, Didar A., Gauci, John Baptist, Sciriha, Irene, Sharaf, Khidir R.},
journal = {Czechoslovak Mathematical Journal},
keywords = {nullity; core vertex; Fiedler vertex; cut-vertices; coalescence},
language = {eng},
number = {3},
pages = {971-985},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Coalescing Fiedler and core vertices},
url = {http://eudml.org/doc/286823},
volume = {66},
year = {2016},
}

TY - JOUR
AU - Ali, Didar A.
AU - Gauci, John Baptist
AU - Sciriha, Irene
AU - Sharaf, Khidir R.
TI - Coalescing Fiedler and core vertices
JO - Czechoslovak Mathematical Journal
PY - 2016
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 66
IS - 3
SP - 971
EP - 985
AB - The nullity of a graph $G$ is the multiplicity of zero as an eigenvalue in the spectrum of its adjacency matrix. From the interlacing theorem, derived from Cauchy’s inequalities for matrices, a vertex of a graph can be a core vertex if, on deleting the vertex, the nullity decreases, or a Fiedler vertex, otherwise. We adopt a graph theoretical approach to determine conditions required for the identification of a pair of prescribed types of root vertices of two graphs to form a cut-vertex of unique type in the coalescence. Moreover, the nullity of subgraphs obtained by perturbations of the coalescence $G$ is determined relative to the nullity of $G$. This has direct applications in spectral graph theory as well as in the construction of certain ipso-connected nano-molecular insulators.
LA - eng
KW - nullity; core vertex; Fiedler vertex; cut-vertices; coalescence
UR - http://eudml.org/doc/286823
ER -

References

top
  1. Andelić, M., Fonseca, C. M. Da, Mamede, R., 10.1016/j.laa.2010.09.017, Linear Algebra Appl. 434 (2011), 514-525. (2011) Zbl1225.05078MR2741238DOI10.1016/j.laa.2010.09.017
  2. Brown, M., Kennedy, J. W., Servatius, B., Graph singularity, Graph Theory Notes N. Y. 25 (1993), 23-32. (1993) 
  3. Collatz, L., Sinogowitz, U., 10.1007/BF02941924, Abh. Math. Semin. Univ. Hamb. 21 (1957), 63-77 German. (1957) Zbl0077.36704MR0087952DOI10.1007/BF02941924
  4. Cvetković, D., Doob, M., 10.1080/03081088508817683, Linear Multilinear Algebra 18 (1985), 153-181. (1985) Zbl0615.05039MR0817659DOI10.1080/03081088508817683
  5. Fowler, P. W., Pickup, B. T., Todorova, T. Z., Borg, M., Sciriha, I., 10.1063/1.4863559, J. Chem. Phys. 140 (2014), no. 054115, 12 pages. (2014) DOI10.1063/1.4863559
  6. Fowler, P. W., Pickup, B. T., Todorova, T. Z., Reyes, R. De Los, Sciriha, I., 10.1016/j.cplett.2013.03.022, Chem. Phys. Lett. 568/569 (2013), 33-35. (2013) DOI10.1016/j.cplett.2013.03.022
  7. Gong, S. C., Xu, G. H., On the nullity of a graph with cut-points, Linear Algebra Appl. 436 (2012), 135-142. (2012) Zbl1243.05147MR2859917
  8. Gutman, I., Sciriha, I., Spectral properties of windmills, Graph Theory Notes N. Y. 38 (2000), 20-24. (2000) MR1751021
  9. Gutman, I., Sciriha, I., Graphs with maximum singularity, Graph Theory Notes N. Y. 30 (1996), 17-20. (1996) MR1661917
  10. Hückel, E., 10.1007/BF01339530, Z. Phys. German 70 (1931), 204-286. (1931) Zbl0002.09601DOI10.1007/BF01339530
  11. Johnson, C. R., Sutton, B. D., 10.1137/S0895479802413649, SIAM J. Matrix Anal. Appl. 26 (2004), 390-399. (2004) Zbl1083.15015MR2124154DOI10.1137/S0895479802413649
  12. Kim, I.-J., Shader, B. L., 10.1016/j.laa.2007.12.022, Linear Algebra Appl. 428 (2008), 2601-2613. (2008) Zbl1145.15011MR2416575DOI10.1016/j.laa.2007.12.022
  13. Marcus, M., Minc, H., A Survey of Matrix Theory and Matrix Inequalities, Allyn and Bacon, Boston (1964). (1964) Zbl0126.02404MR0162808
  14. Pickup, B. T., Fowler, P. W., Borg, M., Sciriha, I., 10.1063/1.4935716, J. Chem. Phys. 143 (2015), #194105, 20 pages. (2015) DOI10.1063/1.4935716
  15. Schwenk, A. J., 10.1007/BFb0066438, Graphs and Combin., Proc. Capital Conf., Washington, Lect. Notes Math. 406 R. A. Bari, F. Harary Springer, Berlin (1974), 153-172. (1974) Zbl0308.05121MR0387126DOI10.1007/BFb0066438
  16. Sciriha, I., 10.26493/1855-3974.115.891, Ars Math. Contemp. 2 (2009), 217-229. (2009) Zbl1190.05084MR2565361DOI10.26493/1855-3974.115.891
  17. Sciriha, I., 10.26493/1855-3974.20.7cc, Ars Math. Contemp. 1 (2008), 20-31. (2008) Zbl1168.05330MR2434268DOI10.26493/1855-3974.20.7cc
  18. Sciriha, I., 10.13001/1081-3810.1215, Electron. J. Linear Algebra 16 (2007), 451-462. (2007) Zbl1142.05344MR2365899DOI10.13001/1081-3810.1215
  19. Sciriha, I., 10.1016/S0012-365X(97)00036-8, Discrete Math. 181 (1998), 193-211. (1998) Zbl0901.05069MR1600771DOI10.1016/S0012-365X(97)00036-8
  20. Sciriha, I., The characteristic polynomials of windmills with an application to the line graphs of trees, Graph Theory Notes N. Y. 35 (1998), 16-21. (1998) MR1667874
  21. Sciriha, I., Debono, M., Borg, M., Fowler, P. W., Pickup, B. T., 10.26493/1855-3974.275.574, Ars Math. Contemp. 6 (2013), 261-278. (2013) Zbl1290.05106MR2996933DOI10.26493/1855-3974.275.574
  22. Sharaf, K. R., Ali, D. A., Nullity and bounds to the nullity of dendrimer graphs, Raf. J. of Comp. & Math's 10 (2013), 71-86. (2013) MR3018063
  23. Simić, S. K., Andelić, M., Fonseca, C. M. Da, Živković, D., On the multiplicities of eigenvalues of graphs and their vertex deleted subgraphs: old and new results, Electron. J. Linear Algebra (electronic only) 30 (2015), 85-105. (2015) Zbl1323.05083MR3335833

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.