Open problem on $\sigma$-invariant

Abstract

Let $G$ be a graph of order $n$ with $m$ edges. Also let ${\mu }_1\ge {\mu }_2\ge \cdots \ge {\mu }_{n-1}\ge {\mu }_n=0$ be the Laplacian eigenvalues of graph $G$ and let $\sigma =\sigma (G)$ $(1\le \sigma \le n)$ be the largest positive integer such that ${\mu }_{\sigma }\ge \frac{2m}{n}$. In this paper, we prove that ${\mu }_2(G)\ge \frac{2m}{n}$ for almost all graphs. Moreover, we characterize the extremal graphs for any graphs. Finally, we provide the answer to Problem 3 in \cite{KMT}, that is, the characterization of all graphs with $\sigma =1$.