Complementary eigenvalues of graphs

In this paper, we study the Eigenvalue Complementarity Problem (EiCP) when its matrix A belongs to the class S(G)={A=[aij]:aij=aji≠0 iff ij∈E}, where G=(V,E) is a connected graph. It is shown that if all nondiagonal elements of A∈S(G) are nonpositive, then A has a unique complementary eigenvalue, which is the smallest eigenvalue of A. In particular, zero is the unique complementary eigenvalue of the Laplacian and the normalized Laplacian matrices of a connected graph. The number c(G) of complementary eigenvalues of the adjacency matrix of a connected graph G is shown to be bounded above by the number b(G) of induced nonisomorphic connected subgraphs of G. Furthermore, c(G)=b(G) if the Perron roots of the adjacency matrices of these subgraphs are all distinct. Finally, the maximum number of complementary eigenvalues for the adjacency matrices of graphs is shown to grow faster than any polynomial on the number of vertices.