| Title:
|
Coalescing Fiedler and core vertices (English) |
| Author:
|
Ali, Didar A. |
| Author:
|
Gauci, John Baptist |
| Author:
|
Sciriha, Irene |
| Author:
|
Sharaf, Khidir R. |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
66 |
| Issue:
|
3 |
| Year:
|
2016 |
| Pages:
|
971-985 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
nullity |
| Keyword:
|
core vertex |
| Keyword:
|
Fiedler vertex |
| Keyword:
|
cut-vertices |
| Keyword:
|
coalescence |
| MSC:
|
05B20 |
| MSC:
|
05C50 |
| MSC:
|
15A18 |
| idZBL:
|
Zbl 06644045 |
| idMR:
|
MR3556879 |
| DOI:
|
10.1007/s10587-016-0304-8 |
| . |
| Date available:
|
2016-10-01T15:42:20Z |
| Last updated:
|
2023-10-28 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/145883 |
| . |
| Reference:
|
[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. Zbl 1225.05078, MR 2741238, 10.1016/j.laa.2010.09.017 |
| Reference:
|
[2] Brown, M., Kennedy, J. W., Servatius, B.: Graph singularity.Graph Theory Notes N. Y. 25 (1993), 23-32. |
| Reference:
|
[3] Collatz, L., Sinogowitz, U.: Spektren endlicher Grafen.Abh. Math. Semin. Univ. Hamb. 21 (1957), 63-77 German. Zbl 0077.36704, MR 0087952, 10.1007/BF02941924 |
| Reference:
|
[4] Cvetković, D., Doob, M.: Developments in the theory of graph spectra.Linear Multilinear Algebra 18 (1985), 153-181. Zbl 0615.05039, MR 0817659, 10.1080/03081088508817683 |
| Reference:
|
[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. 10.1063/1.4863559 |
| Reference:
|
[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. 10.1016/j.cplett.2013.03.022 |
| Reference:
|
[7] Gong, S. C., Xu, G. H.: On the nullity of a graph with cut-points.Linear Algebra Appl. 436 (2012), 135-142. Zbl 1243.05147, MR 2859917 |
| Reference:
|
[8] Gutman, I., Sciriha, I.: Spectral properties of windmills.Graph Theory Notes N. Y. 38 (2000), 20-24. MR 1751021 |
| Reference:
|
[9] Gutman, I., Sciriha, I.: Graphs with maximum singularity.Graph Theory Notes N. Y. 30 (1996), 17-20. MR 1661917 |
| Reference:
|
[10] Hückel, E.: Quantentheoretische Beiträge zum Benzolproblem I. Die Elektronenkonfiguration des Benzols und verwandter Verbindungen.Z. Phys. German 70 (1931), 204-286. Zbl 0002.09601, 10.1007/BF01339530 |
| Reference:
|
[11] Johnson, C. R., Sutton, B. D.: Hermitian matrices, eigenvalue multiplicities, and eigenvector components.SIAM J. Matrix Anal. Appl. 26 (2004), 390-399. Zbl 1083.15015, MR 2124154, 10.1137/S0895479802413649 |
| Reference:
|
[12] Kim, I.-J., Shader, B. L.: On Fiedler- and Parter-vertices of acyclic matrices.Linear Algebra Appl. 428 (2008), 2601-2613. Zbl 1145.15011, MR 2416575, 10.1016/j.laa.2007.12.022 |
| Reference:
|
[13] Marcus, M., Minc, H.: A Survey of Matrix Theory and Matrix Inequalities.Allyn and Bacon, Boston (1964). Zbl 0126.02404, MR 0162808 |
| Reference:
|
[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. 10.1063/1.4935716 |
| Reference:
|
[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. Zbl 0308.05121, MR 0387126, 10.1007/BFb0066438 |
| Reference:
|
[16] Sciriha, I.: Maximal core size in singular graphs.Ars Math. Contemp. 2 (2009), 217-229. Zbl 1190.05084, MR 2565361, 10.26493/1855-3974.115.891 |
| Reference:
|
[17] Sciriha, I.: Coalesced and embedded nut graphs in singular graphs.Ars Math. Contemp. 1 (2008), 20-31. Zbl 1168.05330, MR 2434268, 10.26493/1855-3974.20.7cc |
| Reference:
|
[18] Sciriha, I.: A characterization of singular graphs.Electron. J. Linear Algebra 16 (2007), 451-462. Zbl 1142.05344, MR 2365899, 10.13001/1081-3810.1215 |
| Reference:
|
[19] Sciriha, I.: On the construction of graphs of nullity one.Discrete Math. 181 (1998), 193-211. Zbl 0901.05069, MR 1600771, 10.1016/S0012-365X(97)00036-8 |
| Reference:
|
[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 |
| Reference:
|
[21] Sciriha, I., Debono, M., Borg, M., Fowler, P. W., Pickup, B. T.: Interlacing-extremal graphs.Ars Math. Contemp. 6 (2013), 261-278. Zbl 1290.05106, MR 2996933, 10.26493/1855-3974.275.574 |
| Reference:
|
[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 |
| Reference:
|
[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. Zbl 1323.05083, MR 3335833 |
| . |
