查看文章

Let q min (G) stand for the smallest eigenvalue of the signless Laplacian of a graph G of order n. This paper gives some results on the following extremal problem: How large can q min (G) be if G is a graph of order n, with no complete subgraph of order r+ 1? It is shown that this problem is related to the well-known topic of making graphs bipartite. Using known classical results, several bounds on q min are obtained, thus extending previous work of Brandt for regular graphs. In addition, the spectra of the Laplacian and the signless Laplacian of blowups of graphs are calculated. Finally, using graph blowups, a general asymptotic result about the maximum q min is established.