BIPARTITE SUBGRAPHS AND THE SIGNLESS LAPLACIAN MATRIX

被引：12

作者：

Kirkland, Steve ^{[1
]}

Paul, Debdas ^{[2
]}

机构：

[1] Natl Univ Ireland, Hamilton Inst, Maynooth, Kildare, Ireland

[2] Jadavpur Univ, Dept Comp Sci & Engn, Kolkata, India

来源：

APPLICABLE ANALYSIS AND DISCRETE MATHEMATICS | 2011年 / 5卷 / 01期

基金：

爱尔兰科学基金会;

关键词：

Bipartite subgraph; signless Laplacian matrix; normalised Laplacian matrix; SPECTRAL THEORY;

D O I：

10.2298/AADM110205006K

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

For a connected graph G, we derive tight inequalities relating the smallest signless Laplacian eigenvalue to the largest normalised Laplacian eigenvalue. We investigate how vectors yielding small values of the Rayleigh quotient for the signless Laplacian matrix can be used to identify bipartite subgraphs. Our results are applied to some graphs with degree sequences approximately following a power law distribution with exponent value 2.1 (scale-free networks), and to a scale-free network arising from protein-protein interaction.

引用

页码：1 / 13

页数：13

共 15 条

[1]

[Anonymous], HDB LINEAR ALGEBRA

[2] Topological structure analysis of the protein-protein interaction network in budding yeast [J].

Bu, DB ;

Zhao, Y ;

Cai, L ;

Xue, H ;

Zhu, XP ;

Lu, HC ;

Zhang, JF ;

Sun, SW ;

Ling, LJ ;

Zhang, N ;

Li, GJ ;

Chen, RS .

NUCLEIC ACIDS RESEARCH, 2003, 31 (09) :2443-2450

[3]

Chung F., 1992, Spectral Graph Theory

[4] Signless Laplacians of finite graphs [J].

Cvetkovic, Dragos ;

Rowlinson, Peter ;

Simic, Slobodan K. .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2007, 423 (01) :155-171

[5] TOWARDS A SPECTRAL THEORY OF GRAPHS BASED ON THE SIGNLESS LAPLACIAN, III [J].

Cvetkovic, Dragos ;

Simic, Slobodan K. .

APPLICABLE ANALYSIS AND DISCRETE MATHEMATICS, 2010, 4 (01) :156-166

[6] TOWARDS A SPECTRAL THEORY OF GRAPHS BASED ON THE SIGNLESS LAPLACIAN, I [J].

Cvetkovic, Dragos ;

Simic, Slobodan K. .

PUBLICATIONS DE L INSTITUT MATHEMATIQUE-BEOGRAD, 2009, 85 (99) :19-33

[7] Towards a spectral theory of graphs based on the signless Laplacian, II [J].

Cvetkovic, Dragos ;

Simic, Slobodan K. .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2010, 432 (09) :2257-2272

[8] Old and new results on algebraic connectivity of graphs [J].

de Abreu, Nair Maria Maia .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2007, 423 (01) :53-73

[9]

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

[10] Bipartite structure of all complex networks [J].

Guillaume, JL ;

Latapy, M .

INFORMATION PROCESSING LETTERS, 2004, 90 (05) :215-221

← 1 2 →