×

The characteristic polynomials of modified graphs. (English) Zbl 0851.05076

The paper is a survey on the relation between the characteristic polynomial of a graph and its modifications. It updates earlier papers by the same author on a similar subject, see the author [Graph perturbations, Surveys in combinatorics, Proc. 13th Br. Comb. Conf., Guildford/UK 1991, Lond. Math. Soc. Lect. Note Ser. 166, 187-219 (1991; Zbl 0738.05058)] and the author [Eutactic stars and graph spectra, IMA Vol. Math. Appl. 50, 153-164 (1993; Zbl 0789.05066)].

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bell, F. K.; Rowlinson, P., On the index of tricyclic Hamiltonian graphs, (Proc. Edinburgh Math. Soc., 33 (1990)), 233-240 · Zbl 0668.05046
[2] Cvetković, D.; Doob, M., Development in the theory of graph spectra, Linear Multilinear Algebra, 19, 153-181 (1985) · Zbl 0615.05039
[3] Cvetković, D.; Doob, M.; Sachs, H., Spectra of Graphs (1980), Academic Press: Academic Press New York · Zbl 0458.05042
[4] Cvetković, D.; Rowlinson, P., Further properties of graph angles, Scientia, 1, 41-51 (1988) · Zbl 0726.05049
[5] Cvetković, D.; Rowlinson, P.; Simić, S. K., A study of eigenspaces of graphs, Linear Algebra Appl., 182, 45-66 (1993) · Zbl 0778.05057
[6] D’Amato, S. S.; Gimarc, B. M.; Trinajstić, N., Isospectral and subspectral molecules, Croatica Chemica Acta, 54, 1-52 (1981)
[7] Godsil, C. D., Walk-generating functions, Christoffel-Darboux identities and the adjacency matrix of a graph, Combin., Probab. Comput., 1, 13-25 (1992) · Zbl 0793.05096
[8] Godsil, C. D.; McKay, B. D., Spectral conditions for the reconstructibility of a graph, J. Combin. Theory Ser. B, 30, 285-289 (1981) · Zbl 0394.05035
[9] Godsil, C. D.; McKay, B. D., Constructing cospectral graphs, Aequ. Math., 25, 257-268 (1982) · Zbl 0527.05051
[10] Heilbronner, E., Das Komposition-Prinzip: Eine anschauliche Methode zur elektronen-theoretischen Behandlung nicht oder niedrig symmetrischer Molekeln im Rahmen der MO-Theorie, Helv. Chim. Acta, 36, 170-188 (1953)
[11] Herndon, W. C.; Ellzey, M. L., Isospectral graphs and molecules, Tetrahedon, 31, 99-107 (1975)
[12] Herndon, W. C.; Ellzey, M. L., The construction of isospectral graphs, Match, 20, 53-79 (1986) · Zbl 0601.05044
[13] Hosoya, H.; Ohkami, N., Operator technique for obtaining the recursion formulas of characteristic and matching polynomials as applied to polyhex graphs, J. Comput. Chem., 4, 585-593 (1983)
[14] Lowe, J. P.; Soto, M. R., Isospectral graphs, symmetry and perturbation theory, Match, 20, 21-51 (1986) · Zbl 0601.05043
[15] Mallion, R. B., Some chemical applications of the eigenvalues and eigenvectors of certain finite planar graphs, (Wilson, R. J., Applications of Combinatorics (1982), Shiva: Shiva Nantwich), 87-114 · Zbl 0511.05043
[16] Neumaier, A., Derived eigenvalues of symmetric matrices, with applications to distance geometry, Linear Alg. Appl., 134, 107-120 (1990) · Zbl 0706.15009
[17] Prabhu, G. M.; Deo, N., On the power of perturbation for testing non-isomorphism of graphs, BIT, 24, 302-307 (1984) · Zbl 0546.68043
[18] Rowlinson, P., A deletion-contraction algorithm for the characteristic polynomial of a multigraph, (Proc. Royal Soc. Edinburgh, 105A (1987)), 153-160 · Zbl 0717.05064
[19] Rowlinson, P., On the characteristic polynomials of spirographs and related graphs, J. Math. Chem., 8, 345-354 (1991)
[20] Rowlinson, P., Graph angles and isospectral molecules, Univ. Beograd Publ. Elektrotehn. Fak. Ser. Mat., 2, 61-66 (1991) · Zbl 0764.05064
[21] Rowlinson, P., Graph perturbations, (Keedwell, A. D., Surveys in Combinatorics 1991 (1991), Cambridge University Press: Cambridge University Press Cambridge), 187-219 · Zbl 0738.05058
[22] Rowlinson, P., The spectrum of a graph modified by the addition of a vertex, Univ. Beograd Publ. Elektrotehn Fak. Ser. Mat., 3, 67-70 (1992) · Zbl 0776.05074
[23] Rowlinson, P., Eutactic stars and graph spectra, (Brualdi, R. A.; etal., Combinatorial and Graph-Theoretic Problems in Linear Algebra (1993), Springer: Springer New York), 153-164 · Zbl 0789.05066
[24] Schwenk, A. J., Computing the characteristic polynomial of a graph, (Bari, R.; Harary, F., Graphs and Combinatorics. Graphs and Combinatorics, Lecture Notes in Mathematics, Vol. 406 (1974), Springer: Springer New York), 153-172
[25] Schwenk, A. J., Removal-cospectral sets of vertices in a graph, (Proc. 10th SE Conference on Combinatorics, Graph Theory and Computing, Utilitas Math (1979), Winnipeg: Winnipeg Manitoba), 849-860
[26] Schwenk, A. J.; Herndon, W. C.; Ellzey, M. L., The construction of cospectral composite graphs, Ann. New York Acad. Sci., 319, 490-496 (1979) · Zbl 0481.05044
[27] Seidel, J. J., Eutactic Stars, (Colloq. Math. Soc. János Bolyai, 18 (1976)), 983-999 · Zbl 0391.05050
[28] Trinajstić, N., The characteristic polynomial of a chemical graph, J. Math Chem., 2, 197-215 (1988)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.