×

zbMATH — the first resource for mathematics

Laplacian graph eigenvectors. (English) Zbl 0932.05057
Summary: If \(G\) is a graph, its Laplacian is the difference of the diagonal matrix of its vertex degrees and its adjacency matrix. The main thrust of the present artilce is to prove several Laplacian eigenvector “principles” which in certain cases can be used to deduce the effect on the spectrum of contracting, adding or deleting edges and/or of coalescing vertices. One application is the construction of two isospectral graphs on 11 vertices having different degree sequences, only one of which is bipartite, and only one of which is decomposable.

MSC:
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Anderson, W.N.; Morley, T.D., Eigenvalues of the Laplacian of a graph, Linear and multilinear algebra, 18, 141-145, (1985) · Zbl 0594.05046
[2] Barnard, S.T.; Pothen, A.; Simon, H., A spectral algorithm for envelope reduction of sparse matrices, J. numer. linear algebra appl., 2, 317-334, (1995) · Zbl 0833.65038
[3] Botti, P.; Merris, R., Almost all trees share a complete set of immanantal polynomials, J. graph theory, 17, 467-476, (1993) · Zbl 0782.05038
[4] Bussemaker, F.C.; Cvetković, D.M., There are exactly 13 connected, cubic, integral graphs, Univ. beograd publ. elektrotehn. fak., ser. mat. fiz., 544-576, 43-48, (1976) · Zbl 0357.05064
[5] Cvetković, D.M.; Doob, M.; Sachs, H., Spectra of graphs, (1995), Johann Ambrosius Heidelberg · Zbl 0824.05046
[6] Cvetković, D.M.; Rowlinson, P.; Simić, S., Eigenspaces of graphs, () · Zbl 0878.05057
[7] Faria, I., Multiplicity of integer roots of polynomials of graphs, Linear algebra appl., 229, 15-35, (1995) · Zbl 0843.05074
[8] Fiedler, M., Algebraic connectivity of graphs, Czech. math. J., 23, 298-305, (1973) · Zbl 0265.05119
[9] Fiedler, M., A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, Czech math. J., 25, 619-633, (1975) · Zbl 0437.15004
[10] Grone, R.; Merris, R.; Sunder, V.S., The Laplacian spectrum of a graph, SIAM J. matrix anal. appl., 11, 218-238, (1990) · Zbl 0733.05060
[11] Grone, R.; Zimmermann, G., Large eigenvalues of the Laplacian, Linear and multilinear algebra, 28, 45-47, (1990) · Zbl 0714.05039
[12] Hammer, P.L.; Kelmans, A.K., Laplacian spectra and spanning trees of threshold graphs, Discrete appl. math., 65, 255-273, (1996) · Zbl 0860.05055
[13] McKay, B.D., On the spectral characteristics of trees, Ars combin., 3, 219-232, (1977) · Zbl 0404.05045
[14] Merris, R., Degree maximal graphs are Laplacian integral, Linear algebra appl., 199, 381-389, (1994) · Zbl 0795.05091
[15] Merris, R., Threshold graphs, (), 205-210 · Zbl 0959.05028
[16] Merris, R., Multilinear algebra, (1997), Gordon and Breach Amsterdam · Zbl 0892.15020
[17] Merris, R., Large families of Laplacian isospectral graphs, Linear and multilinear algebra, 43, 201-205, (1997) · Zbl 0887.05036
[18] Moon, J.W.; Moser, L., Almost all (0,1)-matrices are primitive, Studia math. hungar., 1, 153-156, (1996) · Zbl 0142.27102
[19] Schwenk, A.J., Exactly thirteen connected cubic graphs have integral spectra, (), 516-533
[20] West, D.B., Introduction to graph theory, (1996), Prentice-Hall Upper Saddle River, NJ · Zbl 0845.05001
[21] Wolk, E.S., A note on the comparability graph of a tree, (), 17-20 · Zbl 0137.18105
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.