Laplacian eigenvalue distribution and graph parameters (Q2244867): Difference between revisions

The authors prove several inequalities bounding the number of Laplacian eigenvalues of a (simple) graph \(G\) lying in certain intervals by values depending on structural parameters of \(G\) -- in particular on the independence number \(\alpha(G)\) and the diameter \(d(G)\) of \(G\). For an interval \(I\), let \(m_G I\) denote the number of Laplacian eigenvalues of \(G\) in \(I\). The authors prove the following inequalities: \begin{itemize} \item[i)] \(m_G[0,1) \leq \alpha(G) \leq m_G[0, n - \alpha(G)]\) for all connected graphs of order \(n\); \item[ii)] \(m_G(n - d(G) + 3, n] \leq n - d(G) - 1\) for all connected graphs of order \(n\) such that \(d(G) \geq 4\); \item[iii)] \(m_G(n-1, n] \leq 1\) for all connected graphs of order \(n\) that do not contain both a \(3\)-cycle and a \(4\)-cycle. \end{itemize} Moreover, they give an alternative proof of the inequality \(m_G(n-1,n] \leq \chi(G) - 1\) for all connected graphs of order \(n\) with chromatic number \(\chi(G)\), first established by \textit{L. Wang} et al. [ibid. 607, 307--318 (2020; Zbl 1458.05159)]. In addition, the authors characterise bipartite graphs such that \(m_G[0,1) = \alpha(G)\), as well as all connected graphs of order \(n\) such that \(m_G[0,1] = n - 1\) and such that \(m_G[0,1] = n - 2\).