Geodesic
Coalescing Fiedler and core vertices
Czechoslovak Mathematical Journal, Tome 66 (2016) no. 3, pp. 971-985
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.1007/s10587-016-0304-8
Classification : 05B20, 05C50, 15A18
Keywords: nullity; core vertex; Fiedler vertex; cut-vertices; coalescence 
@article{10_1007_s10587_016_0304_8,
     author = {Ali, Didar A. and Gauci, John Baptist and Sciriha, Irene and Sharaf, Khidir R.},
     title = {Coalescing {Fiedler} and core vertices},
     journal = {Czechoslovak Mathematical Journal},
     pages = {971--985},
     year = {2016},
     volume = {66},
     number = {3},
     doi = {10.1007/s10587-016-0304-8},
     mrnumber = {3556879},
     zbl = {06644045},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0304-8/}
}
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
SP  - 971
EP  - 985
VL  - 66
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0304-8/
DO  - 10.1007/s10587-016-0304-8
LA  - en
ID  - 10_1007_s10587_016_0304_8
ER  - 
%0 Journal Article
%A Ali, Didar A.
%A Gauci, John Baptist
%A Sciriha, Irene
%A Sharaf, Khidir R.
%T Coalescing Fiedler and core vertices
%J Czechoslovak Mathematical Journal
%D 2016
%P 971-985
%V 66
%N 3
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-016-0304-8/
%R 10.1007/s10587-016-0304-8
%G en
%F 10_1007_s10587_016_0304_8
Ali, Didar A.; Gauci, John Baptist; Sciriha, Irene; Sharaf, Khidir R. Coalescing Fiedler and core vertices. Czechoslovak Mathematical Journal, Tome 66 (2016) no. 3, pp. 971-985. doi: 10.1007/s10587-016-0304-8

[1] Andelić, M., Fonseca, C. M. Da, Mamede, R.: On the number of P-vertices of some graphs. Linear Algebra Appl. 434 (2011), 514-525. | DOI | MR | Zbl

[2] Brown, M., Kennedy, J. W., Servatius, B.: Graph singularity. Graph Theory Notes N. Y. 25 (1993), 23-32.

[3] Collatz, L., Sinogowitz, U.: Spektren endlicher Grafen. Abh. Math. Semin. Univ. Hamb. 21 (1957), 63-77 German. | DOI | MR | Zbl

[4] Cvetković, D., Doob, M.: Developments in the theory of graph spectra. Linear Multilinear Algebra 18 (1985), 153-181. | DOI | MR | Zbl

[5] Fowler, P. W., Pickup, B. T., Todorova, T. Z., Borg, M., Sciriha, I.: Omni-conducting and omni-insulating molecules. J. Chem. Phys. 140 (2014), no. 054115, 12 pages. | DOI

[6] Fowler, P. W., Pickup, B. T., Todorova, T. Z., Reyes, R. De Los, Sciriha, I.: Omni-conducting fullerenes. Chem. Phys. Lett. 568/569 (2013), 33-35. | DOI

[7] Gong, S. C., Xu, G. H.: On the nullity of a graph with cut-points. Linear Algebra Appl. 436 (2012), 135-142. | MR | Zbl

[8] Gutman, I., Sciriha, I.: Spectral properties of windmills. Graph Theory Notes N. Y. 38 (2000), 20-24. | MR

[9] Gutman, I., Sciriha, I.: Graphs with maximum singularity. Graph Theory Notes N. Y. 30 (1996), 17-20. | MR

[10] Hückel, E.: Quantentheoretische Beiträge zum Benzolproblem I. Die Elektronenkonfiguration des Benzols und verwandter Verbindungen. Z. Phys. German 70 (1931), 204-286. | DOI | Zbl

[11] Johnson, C. R., Sutton, B. D.: Hermitian matrices, eigenvalue multiplicities, and eigenvector components. SIAM J. Matrix Anal. Appl. 26 (2004), 390-399. | DOI | MR | Zbl

[12] Kim, I.-J., Shader, B. L.: On Fiedler- and Parter-vertices of acyclic matrices. Linear Algebra Appl. 428 (2008), 2601-2613. | DOI | MR | Zbl

[13] Marcus, M., Minc, H.: A Survey of Matrix Theory and Matrix Inequalities. Allyn and Bacon, Boston (1964). | MR | Zbl

[14] Pickup, B. T., Fowler, P. W., Borg, M., Sciriha, I.: A new approach to the method of source-sink potentials for molecular conduction. J. Chem. Phys. 143 (2015), \#194105, 20 pages. | DOI

[15] Schwenk, A. J.: Computing the characteristic polynomial of a graph. Graphs and Combin., Proc. Capital Conf., Washington, Lect. Notes Math. 406 R. A. Bari, F. Harary Springer, Berlin (1974), 153-172. | DOI | MR | Zbl

[16] Sciriha, I.: Maximal core size in singular graphs. Ars Math. Contemp. 2 (2009), 217-229. | DOI | MR | Zbl

[17] Sciriha, I.: Coalesced and embedded nut graphs in singular graphs. Ars Math. Contemp. 1 (2008), 20-31. | DOI | MR | Zbl

[18] Sciriha, I.: A characterization of singular graphs. Electron. J. Linear Algebra 16 (2007), 451-462. | DOI | MR | Zbl

[19] Sciriha, I.: On the construction of graphs of nullity one. Discrete Math. 181 (1998), 193-211. | DOI | MR | Zbl

[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. | MR

[21] Sciriha, I., Debono, M., Borg, M., Fowler, P. W., Pickup, B. T.: Interlacing-extremal graphs. Ars Math. Contemp. 6 (2013), 261-278. | DOI | MR | Zbl

[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. | MR

[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. | MR | Zbl

Cité par Sources :