2-fold covers of graphs, their spectrum and the matching polynomial

81 Views Asked by At

A $k$-regular $G$ is called Ramanujan if with the exception of the trivial eigenvalue $k$, all eigenvalues of its adjacency matrix $A_G$ are in the interval $[-2\sqrt{k-1}, 2\sqrt{k-1}]$.

Related to this, Bilu and Linial conjectured here that it was possible to create a family of Ramanujan graphs by taking successive $2$-fold covers of some graphs. It is important to mention that if $G'$ is a $2$-fold cover of $G$, then the characteristic polynomial of $G$, $p_{A_G}(x)$ divides $p_{A_{G'}}(x)$ and the new roots of the latter are the eigenvalues of a signed adjacency matrix.

As is explained in this paper by D. Gregory, the signed adjacency matrix associated to $G$ and $G'$ is obtained from $A_G$ by replacing each entry by $-1$ if the lift of the corresponding edge crosses in $G'$, and keeping it as $1$ or $0$ otherwise.

My question is: what is known about the new eigenvalues of $A_{G'}$?

In particular, we can exclude the cases when $G'$ is equal to two disconnect copies of $G$, or bipartite. In each of these cases, the new eigenvalues are roots of $p_{A_G}(x)^2$ or $p_{A_G}(x^2)$, respectively. Moreover, note that up to isomorphism in the $2$-fold cover there $2^r$ different edge-signings of $G$ ($r = E-V + 1$), and the average of the characteristic polynomials of the signed adjacency matrices is $m_G(x)$, the matching polynomial.

Another question: what is known about the roots of $2^r m_G(x) - p_{A_G}(x)^2 - p_{A_G}(x^2)$?