Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5773391 | Linear Algebra and its Applications | 2017 | 14 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory
Authors
Rafael Fernandes, Joaquim Judice, Vilmar Trevisan,