A relation between the matching number and Laplacian spectrum of a graph

By G. Ming, T. Wang. 2001

59 citations recorded by the source corpus.

Abstract Let G be a graph, its Laplacian matrix is the difference of the diagonal matrix of its vertex degrees and its adjacency matrix. In this paper, we generalize a result in (R. Merris, Port. Math. 48 (3) 1991) and obtain the following result: Let G be a graph and M(G) be a maximum matching in G. Then the number of edges in M(G) is a lower bound for the number of Laplacian eigenvalues of G exceeding 2.

Subfields: Computational Theory and Mathematics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/313915069290695bae41000af9bd4ae286124896