On the spectra of connected graphs

Properties of the spectra of infinite connected graphs outside of some critical circle are investigated by the method of generating functions. The radius $\rho$ of this circle is the inverse value of the maximum $r(G)$ of the radii of convergence $r_v(G)$ of the generating functions $\varphi_{G,v}(z)$ of the numbers of closed walks without intermediate recurrences to the initial vertex $v$. Let $R(G)$ be the radius of convergence of the generating function of the closed walks beginning at a fixed vertex (for connected graph it does not depend on the choice of this vertex). It is known that if $r(G)>R(G)$, then for a directed graph $G$ and any $\varepsilon>0$ there exists a space $\ell^{1}(\mu^{(\varepsilon)})$, where the action of the adjacency matrix $A(G)$ defines the operator with discrete spectrum outside the circle of radius $\rho+\varepsilon$. In the paper, the eigen-values from this domain are represented as the elements of the set $J(G)^{-1}$, where $J(G)$ is the set of zeros of the function $1-\varphi_{G,v}(z)$ corresponding to the vertex $v$ such that $r_v(G)=r(G)$. The geometric multiplicity of each eigen-value from the set $J(G)^{-1}$ is equal to one, and the size of the Jordan square coincides with the multiplicity of the corresponding zero of the function $1-\varphi_{G,v}(z)$. The spectra of finite subgraphs converging to $G$ outside the circle $\rho+\varepsilon$ approximate the eigen-values of the operator $A(G)$. Under the condition $R(G)<r(G)$ the spectrum of the self-adjoint operator on the space $\ell^{2}$ generated by the adjacent matrix of an undirected graph in the domain $|\lambda|>r(G)^{-1}$ is discrete and consists of no more that two points. One of them is the maximal point of the spectrum (the Perron–Frobenius number). The second point (if it exists) is placed on the negative semi-axis and characterizes the size of the maximal parts of bipartite subgraphs (if it is symmetric to the maximal point of the spectrum with respect to the origin, then the graph itself is bipartite).
The research was supported by the INTAS–RFBR, grant 95–418.