Proof of a conjecture on ‘plateaux’ phenomenon of graph Laplacian eigenvalues

Let G be a simple graph. A pendant path of G   is a path such that one of its end vertices has degree 1, the other end has degree ≥3, and all the internal vertices have degree 2. Let pk(G)pk(G) be the number of pendant paths of length k of G  , and qk(G)qk(G) be the number of vertices with degree ≥3 which are an end vertex of some pendant paths of length k. Motivated by the problem of characterizing dendritic trees, N. Saito and E. Woei conjectured that any graph G   has some Laplacian eigenvalue with multiplicity at least pk(G)−qk(G)pk(G)−qk(G). We prove a more general result for both Laplacian and signless Laplacian eigenvalues from which the conjecture follows.