A note on the positive semidefiniteness of A(alpha)(G)

作者：Nikiforov Vladimir^*; Rojo Oscar

来源：Linear Algebra and Its Applications, 2017, 519: 156-163.

DOI：10.1016/j.laa.2016.12.042

• Convex combination of matrices
• Signless Laplacian
• Adjacency matrix
• Bipartite graph
• Positive semidefinite matrix
• Chromatic number

Let G be a graph with adjacency matrix A(G) and let D(G) be the diagonal matrix of the degrees of G. For every real alpha epsilon [0,1], write A alpha (G) for the matrix A alpha (G) = alpha D (G) (1 a)A (G). Let alpha(0) (G) be the smallest a for which A(alpha)(G) is positive semidefinite. It is known that alpha(0) (G) <= 1/2. The main results of this paper are: (1) if G is d-regular then alpha(0) = -lambda(min)(Alpha(G))/d-lambda(min)(Alpha(G))' where Amin(A(G)) is the smallest eigenvalue of A(G); (2)G contains a bipartite component if and only if alpha(0) (G) = 1/2; (3)if G is r-colorable, then alpha(0) (G) >= 1/r.

• 出版日期2017-4-15