1. A note on the positive semidefiniteness of Aα(G).
- Author
-
Nikiforov, Vladimir and Rojo, Oscar
- Subjects
- *
SEMIDEFINITE programming , *GRAPH theory , *EIGENVALUES , *BIPARTITE graphs , *LAPLACIAN matrices - Abstract
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 α ∈ [ 0 , 1 ] , write A α ( G ) for the matrix A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) . Let α 0 ( G ) be the smallest α for which A α ( G ) is positive semidefinite. It is known that α 0 ( G ) ≤ 1 / 2 . The main results of this paper are: (1) if G is d -regular then α 0 = − λ min ( A ( G ) ) d − λ min ( A ( G ) ) , where λ min ( A ( G ) ) is the smallest eigenvalue of A ( G ) ; (2) G contains a bipartite component if and only if α 0 ( G ) = 1 / 2 ; (3) if G is r -colorable, then α 0 ( G ) ≥ 1 / r . [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF