If $G$ is a strongly connected graph and $1\le n< \rho(G)$ is an integer, then must there always exist $H\subset G$ with $\rho(H)=n$?

38 Views Asked by At

$G$ may have loops and multiple, directed edges, and we take $H\subset G$ to mean that the edges and vertices of $H$ are subsets of those in $G$ (not necessarily a vertex-induced subgraph).

We take $\rho(G)$ to be the spectral radius of $G$; that is, the largest absolute value of the eigenvalues of its adjacency matrix. From the Perron-Froebenius theorem, $\rho(G)$ is itself an eigenvalue with an eigenvector that has all positive components.

I was trying to prove the above for $n=2$ (and on graphs satisfying an additional condition) to prove a relationship between indefinite generalized Cartan matrices and affine Cartan matrices, but then began to believe it might be true more generally.

Edit for clarification: $\rho(G)$ needn't be an integer, but $n$ is