DIMACS TR: 99-45

The Adjacency Matrix and Spectrum of a Graph with Negative Third Largest Eigenvalue



Authors: Paul A. Dreyer, Jr. and Xuerong Yong

ABSTRACT

Let $G$ be a simple connected graph with $n$ vertices, let $\lambda_i(G)$ be the $i$th largest eigenvalue of $G$. This paper provides the following results:

1. If $\lambda_3(G)<0$, then the adjacency matrix of $G$, $A(G)$ is cogredient to the matrix:

where $a_{ij}=1$ iff $i\ne j$ and $a_{ij}=0$ otherwise, and $$l_1+l_2+\ldots+l_k\le l.$$ Furthermore, if there exists an index $i$ such that $l_i > 1$, then $ G $ has the eigenvalue $-1$ with multiplicity at least $n-2r-1$, where $2r$ is the rank of $A(G^c)$.

2. $\lambda_3(G)<0 $ implies that $ \lambda_j(G)\ge -1$, $j=3,4,\ldots,n-r $, where $2r$ is the rank of the adjacency matrix of the complement of $G$, $2r \le n-1$.



Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-45.ps.gz
DIMACS Home Page