LAUSR

Abstract Let G be a graph of order n with m edges and chromatic number χ. Let A ( G ) be the adjacency matrix and D ( G ) be the diagonal matrix of vertex degrees of G. Nikiforov defined the matrix A α ( G ) as A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) , where 0 ≤ α ≤ 1 . Then A 1 2 ( G ) = 1 2 ( D ( G ) + A ( G ) ) = 1 2 Q ( G ) , where Q ( G ) is the signless Laplacian matrix of G. Let q n ( G ) and λ n ( A α ) be the least eigenvalue of Q ( G ) and A α ( G ) , respectively. Lima et al. (2011) [8] proposed some open problems on q n ( G ) , two of which are as follows: (1) To characterize the graphs for which q n ( G ) = 2 m n − 1 ; (2) To characterize the graphs for which q n ( G ) = ( 1 − 1 χ − 1 ) 2 m n . In this paper, we present an upper bound on λ n ( A α ) in terms of n, m and α ( 1 / 2 ≤ α ≤ 1 ), and characterize the extremal graphs. As an application, we completely solve problem (1). Moreover, we examine the more generalized result of problem (2) on A α ( G ) . When α ≠ 1 / χ , we obtain some necessary conditions for λ n ( A α ) = ( α χ − 1 ) 2 m ( χ − 1 ) n and, as a corollary, for the equality in problem (2).