CLASSIFICATION OF GRAPHS BY LAPLACIAN EIGENVALUE DISTRIBUTION

For a graph G (V(G), E(G)) of order n. The adjacency matrix of G is denoted by A(G), and the Laplacian matrix is L(G) D(G) – A(G), where D(G) is the diagonal matrix of vertex degrees. The eigenvalues of L(G) are called the Laplacian eigenvalues of G. The multiplicity of a Laplacian eigenvalue μ in a graph G is denoted by MG (μ), while the number Laplacian eigenvalues of G in an interval I is denoted by mGI. It is well known that mG [۰, n] = n for any graph G, however it is not well understood how the eigenvalues are distributed in the interval [۰, n]. Many researchers have focused on the bound of mĠI for some subinterval I of [۰, n]. We show that all graphs G C۳, C۷ with minimum degree at least two, mg[۱,n] ≥ ß′(G) + ۱, where ẞ'(G) is the edge covering number of G. We present a short proof of the known result that mg (n − ۱, n] ≤ k(G), where K(G) is the vertex connectivity of G. Additionally, we classify all trees T such that mà (n − i,n] = j, for ۱ ≤ i, j ≤ ۲. For G with degree sequence d₁ ≥ d۲ ≥ … … · ≥ dn, we determine the classes of graphs that satisfy the condition mg[۰, d۱] = ۲, mg[dn, n] ۲ and mG [dn−۱, n] = ۲.

کلیدواژه ها:

Laplacian eigenvalue ، edge covering number ، vertex connectivity