Bipartite subgraphs and the signless Laplacian matrix

Abstract

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

PDF