Bipartite subgraphs and the signless Laplacian matrix


Recommended citation: Kirkland, S. and Paul, D., 2011. Bipartite subgraphs and the signless Laplacian matrix. Applicable Analysis and Discrete Mathematics 5(1), pp.1-13.


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