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\mathrm{\nabla }{K}_{n-m}\mathrm{\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.

Keywords:

• Laplacian eigenvalue
• independence number
• L-cospectral

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

The first author is supported by the Korea NRF grant NRF-2018R1C1B6005600; the third author is supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (NRF-2016R1D1A1B03933185).