The clique number and the smallest Q-eigenvalue of graphs

2015/08/07 by de Lima, Leonardo, Nikiforov, Vladimir, Oliveira, Carla
#05C50 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1508.01784

Abstract

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, using graph blowups, a general asymptotic result about the maximum q_min is established. As a supporting tool, the spectra of the Laplacian and the signless Laplacian of blowups of graphs are calculated.

Related

• A lower bound of the least signless Laplacian eigenvalue of a graph
• Maxima of the Q-index: graphs with no K_s,t
• Eigenvalue bounds for the signless p-Laplacian
• Maxima of the Q-index: forbidden even cycles
• Maxima of the Q-index: graphs without long paths