Laplacian graph eigenvectors

被引：209

作者：

Merris, R ^{[1
]}

机构：

[1] Calif State Univ Hayward, Dept Math & Comp Sci, Hayward, CA 94542 USA

来源：

LINEAR ALGEBRA AND ITS APPLICATIONS | 1998年 / 278卷 / 1-3期

关键词：

algebraic connectivity; decomposable graph; Faria vector; Fiedler vector; graph join; graph product; graph spectra; isospectral graphs; Kronecker product; Laplacian integral graph; spectrally unique graph; threshold graph;

D O I：

10.1016/S0024-3795(97)10080-5

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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 article 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. (C) 1998 Elsevier Science Inc. All rights reserved.

引用

页码：221 / 236

页数：16

共 21 条

[1]

Anderson W. N., 1985, Linear Multilinear Algebra, V18, P141, DOI [10.1080/03081088508817681, DOI 10.1080/03081088508817681]

[2]

[Anonymous], LECT NOTES MATH

[3] A SPECTRAL ALGORITHM FOR ENVELOPE REDUCTION OF SPARSE MATRICES [J].

BARNARD, ST ;

POTHEN, A ;

SIMON, H .

NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS, 1995, 2 (04) :317-334

[4] ALMOST-ALL TREES SHARE A COMPLETE SET OF IMMANANTAL POLYNOMIALS [J].

BOTTI, P ;

MERRIS, R .

JOURNAL OF GRAPH THEORY, 1993, 17 (04) :467-476

[5]

Bussemaker F.C., 1976, Univ. Beograd. Publ. Elektroehn. Fak. Ser. Mat. Fiz., V544, P43

[6]

CVETKOVIC D, 1997, ENCY MATH APPL, V66

[7]

Cvetkovic D.M., 1995, Spectra of Graphs-Theory and Application

[8] MULTIPLICITY OF INTEGER ROOTS OF POLYNOMIALS OF GRAPHS [J].

FARIA, I .

LINEAR ALGEBRA AND ITS APPLICATIONS, 1995, 229 :15-35

[9]

FIEDLER M, 1973, CZECH MATH J, V23, P298

[10]

FIEDLER M, 1975, CZECH MATH J, V25, P619

← 1 2 3 →