Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
nullity; core vertex; Fiedler vertex; cut-vertices; coalescence
nullity; core vertex; Fiedler vertex; cut-vertices; coalescence
Summary:
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.
References:
[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 10.1016/j.laa.2010.09.017 | MR 2741238 | Zbl 1225.05078
[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 10.1007/BF02941924 | MR 0087952 | Zbl 0077.36704
[4] Cvetković, D., Doob, M.: Developments in the theory of graph spectra. Linear Multilinear Algebra 18 (1985), 153-181. DOI 10.1080/03081088508817683 | MR 0817659 | Zbl 0615.05039
[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 10.1063/1.4863559
[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 10.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. MR 2859917 | Zbl 1243.05147
[8] Gutman, I., Sciriha, I.: Spectral properties of windmills. Graph Theory Notes N. Y. 38 (2000), 20-24. MR 1751021
[9] Gutman, I., Sciriha, I.: Graphs with maximum singularity. Graph Theory Notes N. Y. 30 (1996), 17-20. MR 1661917
[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 10.1007/BF01339530 | Zbl 0002.09601
[11] Johnson, C. R., Sutton, B. D.: Hermitian matrices, eigenvalue multiplicities, and eigenvector components. SIAM J. Matrix Anal. Appl. 26 (2004), 390-399. DOI 10.1137/S0895479802413649 | MR 2124154 | Zbl 1083.15015
[12] Kim, I.-J., Shader, B. L.: On Fiedler- and Parter-vertices of acyclic matrices. Linear Algebra Appl. 428 (2008), 2601-2613. DOI 10.1016/j.laa.2007.12.022 | MR 2416575 | Zbl 1145.15011
[13] Marcus, M., Minc, H.: A Survey of Matrix Theory and Matrix Inequalities. Allyn and Bacon, Boston (1964). MR 0162808 | Zbl 0126.02404
[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 10.1063/1.4935716
[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 10.1007/BFb0066438 | MR 0387126 | Zbl 0308.05121
[16] Sciriha, I.: Maximal core size in singular graphs. Ars Math. Contemp. 2 (2009), 217-229. DOI 10.26493/1855-3974.115.891 | MR 2565361 | Zbl 1190.05084
[17] Sciriha, I.: Coalesced and embedded nut graphs in singular graphs. Ars Math. Contemp. 1 (2008), 20-31. DOI 10.26493/1855-3974.20.7cc | MR 2434268 | Zbl 1168.05330
[18] Sciriha, I.: A characterization of singular graphs. Electron. J. Linear Algebra 16 (2007), 451-462. DOI 10.13001/1081-3810.1215 | MR 2365899 | Zbl 1142.05344
[19] Sciriha, I.: On the construction of graphs of nullity one. Discrete Math. 181 (1998), 193-211. DOI 10.1016/S0012-365X(97)00036-8 | MR 1600771 | Zbl 0901.05069
[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 1667874
[21] Sciriha, I., Debono, M., Borg, M., Fowler, P. W., Pickup, B. T.: Interlacing-extremal graphs. Ars Math. Contemp. 6 (2013), 261-278. DOI 10.26493/1855-3974.275.574 | MR 2996933 | Zbl 1290.05106
[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 3018063
[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 3335833 | Zbl 1323.05083
Search
Partner of
