On the smallest signless Laplacian eigenvalue of graphs (Q2070846)

Let \(G\) be a graph, and let \(D\) be the diagonal matrix of the vertex degrees. Let \(A\) be the adjacency matrix of \(G\). The matrix \(Q:=D+A\) is called the signless Laplacian of \(G\): like the more usual Laplacian \(L:=D-A\), \(Q\) is a positive semi-definite, real symmetric matrix, but it has different spectral features: among other things, its lowest eigenvalue \(q^\prime\) is 0 with multiplicity agrees with the number of bipartite connected components (so, in particular, 0 is not an eigenvalue if \(G\) is connected and non-bipartite). This article is devoted to finding upper and lower estimates for the lowest eigenvalue \(q'\) of \(Q\) by surgery methods: in other words, the author develops graph operations that consistently raise (or consistently lowers) the lowest signless Laplacian eigenvalue. In the case of the Laplacian \(L\), it is a classical result by Fiedler that the path graph and complete graph have the smallest and largest lowest eigenvalue, respectively. An interesting technical tool, and the deepest result in the article, is presented in Theorem 4: if \(G\) is a complete multipartite graph, the author shows that balancing the clusters (i.e., suitably redistributing vertices between two of the clusters) lowers \(q^\prime\). In Theorem 9, the author presents the extremizers for \(q^\prime\) in the class of complete multipartite graphs: the complete multipartite graphs attaining smallest and largest \(q^\prime\) are the split graph and the Turán graph, respectively. Combining these results, the main estimate in the article is proved: for any graph \(G\) on \(n\) vertices, the largest possible \(q^\prime\) is attained on the Turán graph with \(\chi(G)\) clusters, where \(\chi(G)\) is the chromatic number of \(G\). As a corollary, the author finds in Theorem 12 sufficient conditions on \(G\) for a conjecture of \textit{L. de Lima} et al. [Discrete Math. 339, No. 6, 1744--1752 (2016; Zbl 1333.05192)] (which has been recently disproved for general graphs) to hold after all.