Proof of a conjecture on `plateaux' phenomenon of graph Laplacian eigenvalues

2015/10/17 by Ghorbani, Ebrahim
#05C38 #05C50 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1510.05117

Abstract

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 p_k(G) be the number of pendant paths of length k of G, and q_k(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 p_k(G)-q_k(G). We prove a more general result for both Laplacian and signless Laplacian eigenvalues from which the conjecture follows.

Related

• On the multiplicity of 1 as a Laplacian eigenvalue of a graph
• Graphs with maximal Laplacian eigenvalue multiplicity
• Proof of a conjecture on distribution of Laplacian eigenvalues and diameter, and beyond
• Eigenvalues of Graph Laplacians Via Rank-One Perturbations
• Tree simplification and the 'plateaux' phenomenon of graph Laplacian eigenvalues