The perturbed Laplacian matrix of a graph

被引:30
作者
Bapat, RB
Kirkland, SJ [1 ]
Pati, S
Merris, R
机构
[1] Univ Regina, Dept Math, Regina, SK S4S 0A2, Canada
[2] Indian Stat Inst, New Delhi 16, India
关键词
Laplacian matrix; algebraic connectivity; characteristic set; interval graphs; perturbed Laplacian matrix; Fiedler vector; Perron component;
D O I
10.1080/03081080108818697
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
For a graph G, we define its perturbed Laplacian matrix as D - A(G) where A(G) is the adjacency matrix of G and D is an arbitrary diagonal matrix. Both the Laplacian matrix and the negative of the adjacency matrix are special instances of the perturbed Laplacian. Several well-known results, contained in the classical work of Fiedler and in more recent contributions of other authors are shown to be true, with suitable modifications, for the perturbed Laplacian. An appropriate generalization of the monotonicity property of a Fiedler vector for a tree is obtained. Some of the results are applied to interval graphs.
引用
收藏
页码:219 / 242
页数:24
相关论文
共 12 条
[1]   A spectral algorithm for seriation and the consecutive ones problem [J].
Atkins, JE ;
Boman, EG ;
Hendrickson, B .
SIAM JOURNAL ON COMPUTING, 1998, 28 (01) :297-310
[2]  
Bondy J.A., 2008, GRAD TEXTS MATH
[3]  
CVETKOVIC DM, 1979, SPECTRA GRAPHS
[4]  
Fallat S, 1998, ELECTRON J LINEAR AL, V3, P48, DOI DOI 10.13001/1081-3810.10140913.05073
[5]  
FIEDLER M, 1975, CZECH MATH J, V25, P607
[6]  
FIEDLER M, 1973, CZECH MATH J, V23, P298
[7]  
FIEDLER M, 1975, CZECH MATH J, V25, P619
[8]  
Fiedler M., 1989, Comb. Graph Theory, V25, P57, DOI [DOI 10.4064/-25-1-57-70, 10.4064/-25-1-57-70]
[9]  
Horn R. A., 1987, MATRIX ANAL
[10]  
Kirkland S., 1998, LINEAR MULTILINEAR A, V44, P131, DOI DOI 10.1080/03081089808818554