Classification of graphs by Laplacian eigenvalue distribution and independence number

Abstract

Let $m_{G}I$ denote the number of Laplacian eigenvalues of a graph $G$ in an interval $I$ and let $\alpha (G)$ denote the independence number of $G$. In this paper, we determine the classes of graphs that satisfy the condition $m_G[0,n-\alpha (G)]=\alpha (G)$ when $\alpha (G)=2$ and $\alpha (G)=n-2$, where $n$ is the order of $G$. When $\alpha (G)=2$, $G\cong K_1\nabla K_{n-m}\nabla K_{m-1}$ for some $m\ge 2$. When $\alpha (G)=n-2$, there are two types of graphs $B(p,q,r)$ and $B^{\prime }(p,q,r)$ of order $n=p+q+r+2$, which we call the binary star graphs. Also, we show that the binary star graphs with $p=r$ are determined by their Laplacian spectra.