# The Spectral Geometry of Biregular Graphs:
a Quantum Graph Approach

Robert Carlson
Department of Mathematics
University of Colorado at Colorado Springs
Colorado Springs, Colorado USA
<EMAIL_ADDRESS>
(2023)

###### Abstract

The spectral theory of the Laplace differential operator for biregular quantum
graphs is developed. Trees are studied in detail. Generating functions for
closed nonbacktracking walks appear when resolvents for trees are related to
resolvents for biregular graphs they cover. The relationship between resolvent
traces for finite graphs and walk generating functions is especially
productive. A detailed description of the rational extension of
nonbacktracking walk generating functions is presented.

Mathematics Subject Classification: 34B45, O5C50

Keywords: Biregular quantum graphs, graph spectral geometry, resolvent traces,
nonbacktracking walk generating functions

##  1 Introduction

Let ${\mathcal{G}}$ denote a locally finite connected simple graph with a
countable vertex set $\mathcal{V}$ and edge set $\mathcal{E}$. Edges are
treated as intervals of length $1$. As a consequence of this identification
one may use the Hilbert space
$L^{2}({\mathcal{G}})=\oplus_{e\in\mathcal{E}}L^{2}(e)$ and a standard
construction to equip ${\mathcal{G}}$ with a self-adjoint differential
operator ${\mathcal{L}}$ which acts by $-D^{2}$ on its domain.

This work treats the spectral theory of ${\mathcal{L}}$ when ${\mathcal{G}}$
is a biregular graph, that is a bipartite graph whose vertex degrees are the
same for all vertices in one of the two vertex classes. Following the plan of
[7], where regular graphs were studied, an essential part of the analysis is
the spectral theory of ${\mathcal{L}}$ for the biregular tree $\mathcal{T}$,
including a detailed description of the spectrum and resolvent
$R_{\mathcal{T}}(\lambda)=({\mathcal{L}}-\lambda I)^{-1}$. The biregular trees
are universal covering spaces for biregular graphs. This allows resolvents
$R_{{\mathcal{G}}}(\lambda)=({\mathcal{L}}-\lambda I)^{-1}$ for graphs
${\mathcal{G}}$ to be constructed using the tree resolvents.

When ${\mathcal{G}}$ is finite, the resolvent $R_{{\mathcal{G}}}(\lambda)$ is
a trace class operator. Two expressions for the trace of the resolvent are
developed. The first is a conventional series based on eigenvalues. The second
expression describes the trace as a product of a term coming from
$\mathcal{T}$ and a term involving a generating function for closed
nonbacktracking walks in ${\mathcal{G}}$. Given two finite biregular graphs
with the same covering tree, the quotient of their resolvent traces is equal
to a quotient involving their walk generating functions. This formula is
combined with complex variable methods to show that the walk generating
functions extend as rational functions, with considerable information about
pole numbers and locations.

The work starts with a discussion of quantum graphs and the differential
operator ${\mathcal{L}}$. For the finite graphs studied here, the eigenvalues
of ${\mathcal{L}}$ can be computed from the eigenvalues of a conventional
discrete graph Laplacian $\Delta$ together with some additional combinatorial
data. The regular behavior of the eigenvalue sequence of ${\mathcal{L}}$
allows for a compact description of the trace of $R_{{\mathcal{G}}}(\lambda)$
with explicit dependence on the eigenvalues of $\Delta$.

The next section introduces biregular graphs. Important examples for this work
are the complete bipartite graphs whose resolvent trace is computed.
Conveniently, from the quantum graph perspective regular graphs can be
converted to biregular graphs with minimal effect on the spectrum, allowing
this work to subsume some of the previous analysis of regular graphs.

The spectral theory for a biregular tree $\mathcal{T}$ is then developed.
Given an edge $e$ in $\mathcal{T}$, there are special solutions of the
eigenvalue equation $-D^{2}y=\lambda y$ which are functions of the distance
from $e$. The propagation of these solutions depends on multipliers
$\mu^{\pm}(\lambda)$ whose behavior largely determines the spectrum of
${\mathcal{L}}$ for the tree. The functions $\mu^{\pm}(\lambda)$ have a
central role in the construction of the resolvents $R_{\mathcal{T}}(\lambda)$;
their properties as analytic functions are discussed.

The final section opens with a discussion of closed nonbacktracking walks in
finite graphs and their generating functions. The generating functions for
complete bipartite trees are computed. This is followed by material on
covering spaces and the construction of resolvents
$R_{{\mathcal{G}}}(\lambda)$ from $R_{\mathcal{T}}(\lambda)$. When
${\mathcal{G}}$ is a finite biregular graph the resolvent traces are closely
related to walk generating functions, which are described in detail.

In the case of regular graphs, where each vertex has the same degree,
connections between the spectral theory of the discrete Laplacian and such
generating functions were previously explored in [6], and later from a quantum
graph viewpoint in [7]. A more recent and extensive treatment of related
material is [18]. Spectral gaps for biregular graphs have also been treated;
see [1] and the references given there. Many years ago Bob Brooks suggested
that the techniques of [7] could be used in the biregular case. His suggestion
is gratefully acknowledged.

##  2 Differential operators on graphs

Background material on quantum graphs [3], tailored to our purposes, will be
used. In this work edges have length one, and are usually identified with
$[0,1]$. By using the identification of edges with intervals, function spaces
and differential operators may be defined. Let $L^{2}(e)=L^{2}[0,1]$ be the
usual Lebesgue space. $L^{2}({\mathcal{G}})$ denotes the Hilbert space
$\oplus_{e\in\mathcal{E}}L^{2}(e)$. For $f\in L^{2}({{\mathcal{G}}})$, the
function $f_{e}:[0,1]\to\mathbb{C}$ is the restriction of $f$ to the edge $e$.
The inner product is

$\langle
f,g\rangle=\int_{{\mathcal{G}}}f\overline{g}=\sum_{e\in\mathcal{E}}\int_{0}^{1}f_{e}(x)\overline{g_{e}(x)}\
dx.$

A formal second derivative operator $-D^{2}$ acts componentwise on functions
$f\in L^{2}({\mathcal{G}})$ in its domain ${\mathcal{D}}$. Functions
$f\in{\mathcal{D}}$ are continuous on ${\mathcal{G}}$, and continuously
differentiable on each edge, with $f_{e}^{\prime}$ absolutely continuous for
each edge $e$, and $f^{\prime\prime}\in L^{2}({\mathcal{G}})$. At each vertex
$v$ the function $f$ must satisfy

$\sum_{e\sim v}\partial_{\nu}f_{e}(v)=0,$ (2.1)

where $e\sim v$ indicates an edge $e$ incident on the vertex $v$. Here
$\partial_{\nu}$ denotes the derivative computed in ’outward pointing’ local
coordinates which identify each edge $e$ incident on $v$ with a copy of
$[0,1]$ and identify $v$ with $0$. The operator
${\mathcal{L}}:L^{2}({\mathcal{G}})\to L^{2}({\mathcal{G}})$ acting by
$-D^{2}$ with domain ${\mathcal{D}}$ is self-adjoint [3]. The spectrum is a
subset of $[0,\infty)$.

If the vertex set $\mathcal{V}$ is finite then ${\mathcal{L}}$ has discrete
spectrum, with eigenvalues
$\lambda_{0}=0<\lambda_{1}\leq\lambda_{2}\leq\dots$, listed with multiplicity,
and an orthonormal basis of eigenfunctions $\phi_{n}$ with eigenvalues
$\lambda_{n}$ [3, p. 67]. The resolvent
$R_{{\mathcal{G}}}(\lambda)=({\mathcal{L}}-\lambda I)^{-1}$ is trace class
[16, p. 206-212] or [13, p. 521-525] with summable eigenvalue sequence
$1/(\lambda_{n}-\lambda)$ for $\lambda$ in the resolvent set $\rho$, the
complement of the spectrum. The resolvent can be written as an integral
operator with kernel

$R_{{\mathcal{G}}}(\lambda,x,y)=\sum_{n}\frac{\phi_{n}(x)\overline{\phi_{n}(y)}}{\lambda_{n}-\lambda},\quad
x,y\in{\mathcal{G}}.$

Since $\\{\phi_{n}\\}$ is an orthonormal sequence the trace is

${\rm
tr}R_{{\mathcal{G}}}(\lambda)=\sum_{n}\frac{1}{\lambda_{n}-\lambda}=\int_{{\mathcal{G}}}R(\lambda,x,x)dx.$
(2.2)

The next proposition records some simple facts.

######  Proposition 2.1.

Suppose ${\mathcal{G}}$ is finite. If $\Im(\lambda)\not=0$ then
$\Im(\lambda)\Im({\rm tr}R_{{\mathcal{G}}}(\lambda))>0$. The function ${\rm
tr}R_{{\mathcal{G}}}(\lambda)$ has exactly one root between distinct
eigenvalues $\lambda_{n}$ and $\lambda_{n+1}$, and no other roots.

###### Proof.

Since $\lambda_{n}\in\mathbb{R}$,

$\Im(\frac{1}{\lambda_{n}-\lambda})=\frac{1}{2i}[\frac{1}{\lambda_{n}-\lambda}-\frac{1}{\lambda_{n}-\overline{\lambda}}]=\frac{1}{2i}\frac{\lambda-\overline{\lambda}}{|\lambda_{n}-\lambda|^{2}},$

leading to the first claim, which also shows that any roots of ${\rm
tr}R_{{\mathcal{G}}}(\lambda)$ must be real. If $\lambda<0$ then ${\rm
tr}R_{{\mathcal{G}}}(\lambda)$ is a sum of positive terms, and there is a pole
at $\lambda=0$. Finally, for $\lambda\in\mathbb{R}$,
$\lim_{\lambda\downarrow\lambda_{n}}=-\infty$,
$\lim_{\lambda\uparrow\lambda_{n}}=+\infty$ and

$\frac{d}{d\lambda}\sum_{n}\frac{1}{\lambda_{n}-\lambda}=\sum_{n}\frac{1}{(\lambda_{n}-\lambda)^{2}},$

so ${\rm tr}R_{{\mathcal{G}}}(\lambda)$ is increasing between the eigenvalues.
∎

###  2.1 Trace formula 1

When ${\mathcal{G}}$ is finite, a strong link between the eigenvalues of
${\mathcal{L}}$ and a discrete Laplacian $\Delta$ leads to a formula for ${\rm
tr}R_{{\mathcal{G}}}(\lambda)$. Given a vertex $v\in{\mathcal{G}}$, let
$w_{1},\dots,w_{deg(v)}$ be the vertices adjacent to $v$. On the vertex space
${\mathbb{V}}$ consisting of functions $f:\mathcal{V}\to\mathbb{C}$, one has
the adjacency operator

$Af(v)=\sum_{i=1}^{deg(v)}f(w_{i}),$

and the degree operator

$Tf(v)=deg(v)f(v).$

The operator $\Delta$ defined by

$\Delta f(v)=f(v)-T^{-1}Af(v)$ (2.3)

is similar (in the sense of matrix conjugation) [10, pp. 3-7] to the symmetric
discrete Laplacian $I-T^{-1/2}AT^{-1/2}$; the eigenvalues are real and
nonnegative. In case ${\mathcal{G}}$ is biregular the matrix
$T^{-1/2}AT^{-1/2}$ is a constant multiple of $A$.

Suppose $y(x)$ is an eigenfunction of ${\mathcal{L}}$ with eigenvalue
$\lambda=\omega^{2}$. If the edge from $v$ to $w_{i}$ is identified with
$[0,1]$, then

$y(x)=y(v)\cos(\omega
x)+\frac{y(w_{i})-y(v)\cos(\omega)}{\sin(\omega)}\sin(\omega
x),\quad\sin(\omega)\not=0,$

and $y$ may be recovered from its values at $0,1$ except when
$\sin(\omega)=0$. The condition (2.1) gives

$f(v)\cos(\omega)=\frac{1}{{\rm deg}(v)}\sum_{j}f(w_{j}).$

The argument can be reversed, leading to the following well known result [2,
9] or [3, p. 90-92].

######  Proposition 2.2.

If $\lambda_{k}\notin\\{n^{2}\pi^{2}\ |\ n=0,1,2,\dots\\}$, then $\lambda_{k}$
is an eigenvalue of ${\mathcal{L}}$ if and only if
$\nu=1-\cos(\sqrt{\lambda_{k}})$ is an eigenvalue of $\Delta$. In this case
$\lambda_{k}$ and $\nu$ have the same geometric multiplicity.

Henceforth, ${\mathcal{G}}$ is assumed to be bipartite with $N_{\mathcal{V}}$
vertices and $N_{\mathcal{E}}$ edges. Following [8], additional spectral
information is available. Let $E(\lambda)$ denote the eigenspace of
${\mathcal{L}}$ with eigenvalue $\lambda$. First a standard observation: if
$y\in E(0)$ then

$0=\int_{{\mathcal{G}}}y{\mathcal{L}}y=\int_{{\mathcal{G}}}(y^{\prime})^{2},$

so $y$ must be constant on each edge. Since $y$ is continuous on
${\mathcal{G}}$, $E(0)$ consists of the functions constant on ${\mathcal{G}}$.

The edge space ${\mathbb{E}}$ of ${\mathcal{G}}$ consists of functions
$f:\mathcal{E}\to\mathbb{C}$. Pick a spanning tree $\mathcal{T}$ for
${\mathcal{G}}$, letting $e_{1},\dots,e_{M}$, with
$M=N_{\mathcal{E}}-N_{\mathcal{V}}+1$, be the edges of ${\mathcal{G}}$ not in
$\mathcal{T}$. For each $m=1,\dots,M$ there is [5, p. 53] a cycle $C_{m}$
containing $e_{m}$ together with a path in $\mathcal{T}$ connecting the
vertices of $e_{m}$. Let $Z_{0}({\mathcal{G}})$ be the subspace of
${\mathbb{E}}$ generated by the independent functions with the value $1$ on
$C_{m}$ and zero on the complement.

######  Theorem 2.3.

If ${\mathcal{G}}$ is finite and bipartite, then

$\dim E(n^{2}\pi^{2})=N_{\mathcal{E}}-N_{\mathcal{V}}+2,\quad n=1,2,\dots.$

###### Proof.

First note that if $y$ is an eigenfunction of ${\mathcal{L}}$ with eigenvalue
$n^{2}\pi^{2}$ that vanishes at any vertex, then it vanishes at all vertices.
Let $E_{0}(n^{2}\pi^{2})\subset E(n^{2}\pi^{2})$ denote those eigenfunctions
of ${\mathcal{L}}$ with eigenvalue $n^{2}\pi^{2}$ vanishing at the vertices.

Since ${\mathcal{G}}$ is bipartite all cycles $C_{m}$ are even. Suppose
$C_{m}$ has distinct vertices $v_{0},\dots,v_{2k-1}$ and edges
$\\{v_{j-1},v_{j}\\}$ for $j=1,\dots,2k-1$ and $\\{v_{2k-1},v_{0}\\}$. Pick
coordinates $x$ identifying $\\{v_{j-1},v_{j}\\}$ with $[j-1,j]$ and
$\\{v_{2k-1},v_{0}\\}$ with $[2k-1,2k]$. The functions $f_{m}$ with values
$\sin(n\pi x)$ on the edges of $C_{m}$ and $0$ on all other edges are
independent eigenfunctions of ${\mathcal{L}}$.

Now suppose that $y\in E_{0}(n^{2}\pi^{2})$. By subtracting a linear
combination $\sum a_{m}f_{m}$ we may assume that $y$ vanishes on the edges
$e_{m}$. If $v$ is a boundary vertex $v$ of the spanning tree $\mathcal{T}$
with $v$ in edge $e$ of $\mathcal{T}$, then $y=0$ on all edges of
${\mathcal{G}}$ incident on $v$ except possibly $e$. But the vertex conditions
(2.1) force $y$ to vanish on $e$ as well, and thus on all of $\mathcal{T}$. So
${\rm dim}E_{0}(n^{2}\pi^{2})={\rm
dim}Z_{0}({\mathcal{G}})=N_{\mathcal{E}}-N_{\mathcal{V}}+1$.

Finally, identify each edge with $[0,1]$ so that the $R$ vertices are $0$ and
the $B$ vertices are $1$. If $\lambda=n^{2}\pi^{2}$, an eigenfunction
vanishing at no vertices is given by $\cos(n\pi x)$ on each edge. ∎

######  Theorem 2.4.

If ${\mathcal{G}}$ is finite and bipartite, then the eigenvalues $\lambda$ of
${\mathcal{L}}$ satisfy

(i) there are precisely $N_{\mathcal{V}}-2$ eigenvalues with
$0<\lambda<\pi^{2}$, counted with multiplicity.

(ii) there are precisely $N_{\mathcal{V}}-2$ eigenvalues with
$\pi^{2}<\lambda<(2\pi)^{2}$, counted with multiplicity, and these have the
form $\lambda=(2\pi-\mu)^{2}$ for $\mu$ an eigenvalue of ${\mathcal{L}}$ with
$0<\mu<\pi^{2}$; $\lambda$ and $\mu$ have the same multiplicity.

###### Proof.

Since ${\mathcal{G}}$ is bipartite [10, p. 7], $\Delta$ has eigenvalues
$\nu_{0}=0,\nu_{N_{\mathcal{V}}-1}=2$, both with multiplicity $1$. All
eigenvalues $\nu$ of $\Delta$ satisfy $0\leq\nu\leq 2$. Thus there are
$N_{\mathcal{V}}-2$ eigenvalues $\nu$ of $\Delta$ with $0<\nu<2$. These
correspond to eigenvalues $\lambda$ of ${\mathcal{L}}$ with
$0<\sqrt{\lambda}<\pi$. Since $1-\cos(\sqrt{\lambda})$ is symmetric about
$\sqrt{\lambda}=\pi$, conclusion (ii) holds.

∎

Let $\alpha_{k}^{2}$, $k=1,\dots,2N_{\mathcal{V}}-4$ be the eigenvalues of
${\mathcal{L}}$, with multiplicity, satisfying $0<\alpha_{k}^{2}<(2\pi)^{2}$
and $\alpha_{k}^{2}\not=\pi^{2}$. The description of the eigenvalues of
${\mathcal{L}}$ implies that the trace of $R_{{\mathcal{G}}}(\lambda)$ can be
rewritten as

${\rm
tr}(R_{{\mathcal{G}}}(\lambda))=-\frac{1}{\lambda}+\sum_{k=1}^{2N_{\mathcal{V}}-4}\sum_{m=-\infty}^{\infty}\frac{1}{[\alpha_{k}+2m\pi]^{2}-\lambda}+(N_{\mathcal{E}}-N_{\mathcal{V}}+2)\sum_{m=1}^{\infty}\frac{1}{[m\pi]^{2}-\lambda}$

A standard residue calculation will be sketched to evaluate these sums; more
details are in [14, p.149]. The function $\pi\cot(\pi z)/[(\alpha+2\pi
z)^{2}-\lambda]$ has simple poles with residues $1/[(\alpha+2\pi
m)^{2}-\lambda]$ at the integers $m$, and simple poles at
$z=(-\alpha\pm\sqrt{\lambda})/(2\pi)$. Integrate over the contours
$\gamma_{N}$ which bound the squares with vertices $(N+1/2)(\pm 1\pm i)$ to
get

$0=\lim_{N\to\infty}\frac{1}{2\pi i}\int_{\gamma_{N}}\frac{\pi\cot(\pi
z)}{(\alpha+2\pi z)^{2}-\lambda}\
dz=\sum_{m=-\infty}^{\infty}\frac{1}{(\alpha+2\pi m)^{2}-\lambda}$
$+\frac{1}{4\sqrt{\lambda}}\cot(\frac{-\alpha+\sqrt{\lambda}}{2})-\frac{1}{4\sqrt{\lambda}}\cot(\frac{-\alpha-\sqrt{\lambda}}{2}).$

Trigonometric identies give

$\sum_{m=-\infty}^{\infty}\frac{1}{[\alpha+2\pi
m]^{2}-\lambda}=\frac{\sin(\sqrt{\lambda})}{2\sqrt{\lambda}}\frac{1}{\cos(\sqrt{\lambda})-\cos(\alpha)}$
(2.4)

Similarly,

$\sum_{m=1}^{\infty}\frac{1}{[m\pi]^{2}-\lambda}=\frac{1}{2\lambda}-\frac{\cot(\sqrt{\lambda})}{2\sqrt{\lambda}},$

and so

${\rm
tr}(R_{{\mathcal{G}}}(\lambda))=\frac{N_{\mathcal{E}}-N_{\mathcal{V}}}{2\lambda}+\frac{\sin(\sqrt{\lambda})}{2\sqrt{\lambda}}\sum_{k=1}^{2N_{\mathcal{V}}-4}\frac{1}{\cos(\sqrt{\lambda})-\cos(\alpha_{k})}$
(2.5)
$-(N_{\mathcal{E}}-N_{\mathcal{V}}+2)\frac{\cot(\sqrt{\lambda})}{2\sqrt{\lambda}}$

##  3 Biregular graphs

A graph ${\mathcal{G}}$ is bipartite if the vertex set $\mathcal{V}$ can be
partitioned into two subsets, $\mathcal{V}_{R}$ and $\mathcal{V}_{B}$, and all
edges $e$ of the edgeset $\mathcal{E}$ have the form $e=\\{r,b\\}$ with
$r\in\mathcal{V}_{R}$ and $b\in\mathcal{V}_{B}$. ${\mathcal{G}}$ is biregular
if the degree of each vertex depends only on the vertex class, $R$ or $B$. A
simple example is the complete bipartite graph. Another important example is
the biregular tree $\mathcal{T}$, with vertices in $\mathcal{V}_{B}$ having
degree $\delta_{B}+1>1$, and vertices in $\mathcal{V}_{R}$ have degree
$\delta_{R}+1>1$.

Here are two ways of generating biregular graphs from a regular graph
$\Gamma$. Suppose $\mathcal{V}_{1}$ and $\mathcal{V}_{2}$ are two copies of
the vertex set of $\Gamma$. The bipartite cover $\widetilde{\Gamma}$ of
$\Gamma$ has vertex set the disjoint union of $\mathcal{V}_{1}$ and
$\mathcal{V}_{2}$. If $v_{1}\in\mathcal{V}_{1}$ and $v_{2}\in\mathcal{V}_{2}$,
then there is an edge $\\{v_{1},v_{2}\\}$ in $\widetilde{\Gamma}$ if and only
if the corresponding vertices $v_{1},v_{2}$ in $\Gamma$ are adjacent.
$\widetilde{\Gamma}$ is connected if and only if $\Gamma$ is connected and not
bipartite. The second method works well for quantum graphs. For each edge $e$
of $\Gamma$, simply add a vertex $v$ to the middle of $e$, using the
continuity and derivative condition of (2.1). The vertex $v$ will have degree
$2$, but the domain of ${\mathcal{L}}$ is not affected [3, p. 14]. When all
edges are required to have length $1$, the edges of the original graph
effectively have length $2$. Rescaling of edge lengths for a finite graph by a
factor $2$ converts eigenvalues of ${\mathcal{L}}$ from $\lambda_{n}$ to
$\lambda_{n}/4$. In this fashion the spectral theory of regular quantum graphs
is subsumed into the spectral theory of biregular quantum graphs.

Computations for the complete bipartite graphs will be useful later. The
complete bipartite graph $K(m_{B},m_{R})$ has $m_{B}$ vertices in
$\mathcal{V}_{B}$ and $m_{R}$ vertices in $\mathcal{V}_{R}$, with edges
$\\{v,w\\}$ whenever $v\in\mathcal{V}_{B}$ and $w\in\mathcal{V}_{R}$. To
compute the $\Delta$ spectrum for $K(m_{B},m_{R})$, index the $R$ vertices as
$v_{1},\dots,v_{m_{R}}$ and the $B$ vertices as
$v_{m_{R}+1},\dots,v_{m_{B}+m_{R}}$. The matrix $T^{-1}A$ of (2.3) is

$T^{-1}A=\begin{pmatrix}0_{m_{R},m_{R}}&C_{1}\cr
C_{2}&0_{m_{B},m_{B}},\end{pmatrix}$

where $C_{1}$ is an $m_{R}\times m_{B}$ block with all entries $1/m_{B}$ and
$C_{2}$ is an $m_{B}\times m_{R}$ block with all entries $1/m_{R}$. Since

$(T^{-1}A)^{2}=\begin{pmatrix}C_{1}C_{2}&0_{m_{R},m_{B}}\cr
0_{m_{B},m_{R}}&C_{2}C_{1}\end{pmatrix},$

and ${\rm tr}T^{-1}A=0$ one finds that $0$ is an eigenvalue of $T^{-1}A$ with
multiplicity $m_{R}+m_{B}-2$, while the other eigenvalues are $\pm 1$. Thus
the eigenvalues of $\Delta=I-T^{-1}A$ are $1$ with multiplicity
$m_{R}+m_{B}-2$, $0$ and $2$.

By Proposition 2.2 the eigenvalues $\lambda\not=n^{2}\pi^{2}$ of the
corresponding differential operator ${\mathcal{L}}$ are
$(\frac{\pi}{2}+n\pi)^{2}$ for $n=0,1,2,\dots$, each with multiplicity
$m_{R}+m_{B}-2$. By Theorem 2.3 the multiplicity of $\lambda=n^{2}\pi^{2}$ for
$n=1,2,3,\dots$ is $m_{R}m_{B}-(m_{R}+m_{B})+2$. Finally $\lambda=0$ is a
eigenvalue with multiplicity $1$. In particular, $\cos(\alpha_{k})=0$. Letting
${\rm tr}R_{CB}(\lambda)$ denote the trace of the resolvent for
${\mathcal{L}}$ on a complete bipartite graph, (2.5) gives

${\rm
tr}R_{CB}(\lambda)=\frac{m_{R}m_{B}-(m_{R}+m_{B})}{2\lambda}+(\delta_{R}+\delta_{B})\frac{\tan(\sqrt{\lambda})}{\sqrt{\lambda}}$
(3.1)
$-(m_{R}m_{B}-(m_{R}+m_{B})+2)\frac{\cot(\sqrt{\lambda})}{2\sqrt{\lambda}}.$

##  4 Biregular trees

###  4.1 Multipliers

Now consider the case of the biregular tree $\mathcal{T}$ whose edges all have
length $1$. Vertices in $\mathcal{V}_{B}$ have degree $d_{B}=\delta_{B}+1>1$,
and vertices in $\mathcal{V}_{R}$ have degree $d_{R}=\delta_{R}+1>1$,

Fix a vertex $r_{0}$, identified with $0\in\mathbb{R}$, and an initial edge
$e_{0}=\\{r_{0},b_{0}\\}$, which is identified with the interval $[0,1]$. Two
classes of rays, extending from the edge $e_{0}$, will be used: one whose
vertex sequence starts $r_{0},b_{0}$, the other starting with $b_{0},r_{0}$.
The rays rooted at $r_{0}$ are subgraphs of $\mathcal{T}$ with vertex set
$\\{r_{0},b_{0},r_{1},b_{1},\dots\\}$, indexed by nonnegative integers $n$,
with edges $\\{r_{n},b_{n}\\}$ and $\\{b_{n},r_{n+1}\\}$. The rays rooted at
$b_{0}$ will have a vertex sets $\\{b_{0},r_{0},b_{-1},r_{-1}\dots\\}$ indexed
by nonpositive integers $n$, with edges $\\{b_{n},r_{n}\\}$ and
$\\{r_{n},b_{n-1}\\}$ . As metric graphs, a ray rooted at $r_{0}$ may be
identified with $[0,\infty)$, and a ray rooted at $b_{0}$ may be identified
with $(-\infty,1]$. With these identifications, even integers $2n$ correspond
to vertices $r_{n}$ and odd integers $2n+1$ correspond to vertices $b_{n}$.
Let $\mathcal{T}_{0}$ (resp. $\mathcal{T}_{1}$) denote the subtree of
$\mathcal{T}$ obtained as the union of the rays rooted at $r_{0}$ (resp.
$b_{0}$).

Solutions $y(x,\lambda)$ of

$-D^{2}y=\lambda y$ (4.1)

on $[0,1]$ will be extended to $\mathcal{T}_{0}$ (resp. $\mathcal{T}_{1}$),
with values depending only on $x\in[0,\infty)$ (resp. $x\in(-\infty,1]$).
These extended solutions will be continuous at each vertex, with (2.1)
satisfied. Such solutions $y(x,\lambda)$ may be continued from edge $e_{0}$
along the indicated rays by using the following jump conditions at integers
$x$. The continuity requirement is $y(x^{-},\lambda)=y(x^{+},\lambda)$. For
rays rooted at $r_{0}$ the derivative conditions are satisfied by taking

$\begin{matrix}y^{\prime}(x^{+},\lambda)=y^{\prime}(x^{-},\lambda)/\delta_{R},&x>0,{\rm
even},\cr
y^{\prime}(x^{+},\lambda)=y^{\prime}(x^{-},\lambda)/\delta_{B},&x>0,{\rm
odd},\end{matrix}$ (4.2)

while for rays rooted at $b_{0}$ the conditions are

$\begin{matrix}y^{\prime}(x^{-},\lambda)=y^{\prime}(x^{+},\lambda)/\delta_{R},&x<1,{\rm
even},\cr
y^{\prime}(x^{-},\lambda)=y^{\prime}(x^{+},\lambda)/\delta_{B},&x<1,{\rm
odd}.\end{matrix}$ (4.3)

The propagation of initial data $y(v,\lambda),y^{\prime}(v,\lambda)$ for the
extended solutions is described by transition matrices. When initial data is
decomposed using the eigenvectors of the transition matrix, the eigenvalues
act as multipliers.

Let $\omega=\sqrt{\lambda}$, with $\omega\geq 0$ for $\lambda\geq 0$ and the
square root taken continuously for $\lambda\in\mathbb{C}\setminus
i(-\infty,0)$. On the initial edge $e_{0}$ the equation (4.1) has a solution
basis $\cos(\omega x),\sin(\omega x)/\omega$. At $x=0^{+}$ this basis
satisfies

$\begin{pmatrix}\cos(\omega 0^{+})&\sin(\omega
0^{+})/\omega\cr-\omega\sin(\omega 0^{+})&\cos(\omega
0^{+})\end{pmatrix}=\begin{pmatrix}1&0\cr 0&1\end{pmatrix}.$ (4.4)

The abbreviations

$c(\lambda)=\cos(\omega),\quad c^{\prime}(\lambda)=-\omega\sin(\omega)$
$s(\lambda)=\sin(\omega)/\omega,\quad s^{\prime}(\lambda)=\cos(\omega)$

will be used.

Suppose a solution $y$ of (4.1) satisfies $y(0^{+},\lambda)=a$ and
$y^{\prime}(0^{+},\lambda)=b$. At $x=1^{-}$ the solution will have values
given by

$\begin{pmatrix}y(1^{-},\lambda)\cr
y^{\prime}(1^{-},\lambda)\end{pmatrix}=M_{0}(\lambda)\begin{pmatrix}a\cr
b\end{pmatrix},\quad M_{0}(\lambda)=\begin{pmatrix}c(\lambda)&s(\lambda)\cr
c^{\prime}(\lambda)&s^{\prime}(\lambda)\end{pmatrix}.$

By (4.2), the initial data at $x=1^{+}$ is then

$\begin{pmatrix}y(1^{+},\lambda)\cr
y^{\prime}(1^{+},\lambda)\end{pmatrix}=J_{0,B}\begin{pmatrix}y(1^{-},\lambda)\cr
y^{\prime}(1^{-},\lambda)\end{pmatrix},\quad J_{0,B}=\begin{pmatrix}1&0\cr
0&1/\delta_{B}\end{pmatrix}.$

Initial data propagation from $x=1^{+}$ to $x=2^{-}$ is again given by
multiplication by $M_{0}(\lambda)$, while

$\begin{pmatrix}y(2^{+},\lambda)\cr
y^{\prime}(2^{+},\lambda)\end{pmatrix}=J_{0,R}\begin{pmatrix}y(2^{-},\lambda)\cr
y^{\prime}(2^{-},\lambda)\end{pmatrix},\quad J_{0,R}=\begin{pmatrix}1&0\cr
0&1/\delta_{R}\end{pmatrix}.$

Continuing in this fashion, the propagation of initial data from $x=2n^{+}$ to
$x=(2n+2)^{+}$ for $n\geq 0$, is given by

$T_{0}(\lambda)=J_{0,R}M_{0}J_{0,B}M_{0}$ $=\begin{pmatrix}1&0\cr
0&1/\delta_{R}\end{pmatrix}\begin{pmatrix}c(\lambda)&s(\lambda)\cr
c^{\prime}(\lambda)&s^{\prime}(\lambda)\end{pmatrix}\begin{pmatrix}1&0\cr
0&1/\delta_{B}\end{pmatrix}\begin{pmatrix}c(\lambda)&s(\lambda)\cr
c^{\prime}(\lambda)&s^{\prime}(\lambda)\end{pmatrix}$
$=\begin{pmatrix}c^{2}+sc^{\prime}/\delta_{B}&cs+ss^{\prime}/\delta_{B}\cr
c^{\prime}c/\delta_{R}+s^{\prime}c^{\prime}/(\delta_{R}\delta_{B})&sc^{\prime}/\delta_{R}+(s^{\prime})^{2}/(\delta_{R}\delta_{B})\end{pmatrix}$

Note that

$\det(T_{0}(\lambda))=\det(J_{0,R}M_{0}J_{0,B}M_{0})=\frac{1}{\delta_{B}\delta_{R}},$
(4.5)
$trT_{0}(\lambda)=\cos^{2}(\omega)(1+\frac{1}{\delta_{B}\delta_{R}})-\sin^{2}(\omega)(\frac{1}{\delta_{R}}+\frac{1}{\delta_{B}}).$

Next, treat the behavior of similar solutions which start at $x=1^{-}$ and
extend to decreasing values of $x$. Still using the basis $\cos(\omega
x),\sin(\omega x)/\omega$, the matrix taking initial data from $x=1^{-}$ to
$x=0^{+}$ is

$M_{1}(\lambda)=M_{0}^{-1}(\lambda)=\begin{pmatrix}s^{\prime}(\lambda)&-s(\lambda)\cr-c^{\prime}(\lambda)&c(\lambda)\end{pmatrix}.$

From (4.3) the jump in initial data from $x=0^{+}$ to $x=0^{-}$ is given by

$J_{1,R}=\begin{pmatrix}1&0\cr 0&1/\delta_{R}\end{pmatrix}.$

Similarly, the jump from $x=-1^{+}$ to $x=-1^{-}$ is given by

$J_{1,B}=\begin{pmatrix}1&0\cr 0&1/\delta_{B}\end{pmatrix}.$

More generally, the propagation of initial data from $x=(2n+1)^{-}$ to
$x=(2n-1)^{-}$ for $n\leq 0$, is given by

$T_{1}(\lambda)=J_{1,B}M_{1}J_{1,R}M_{1}$ $=\begin{pmatrix}1&0\cr
0&1/\delta_{B}\end{pmatrix}\begin{pmatrix}s^{\prime}(\lambda)&-s(\lambda)\cr-c^{\prime}(\lambda)&c(\lambda)\end{pmatrix}\begin{pmatrix}1&0\cr
0&1/\delta_{R}\end{pmatrix}\begin{pmatrix}s^{\prime}(\lambda)&-s(\lambda)\cr-c^{\prime}(\lambda)&c(\lambda)\end{pmatrix}$
$=\begin{pmatrix}(s^{\prime})^{2}+sc^{\prime}/\delta_{R}&-s^{\prime}s-sc/\delta_{R}\cr-c^{\prime}s^{\prime}/\delta_{B}-cc^{\prime}/(\delta_{B}\delta_{R})&c^{\prime}s/\delta_{B}+c^{2}/(\delta_{B}\delta_{R})\end{pmatrix}$

Again $\det(T_{1}(\lambda))=\frac{1}{\delta_{B}\delta_{R}}$ and ${\rm
tr}(T_{1}(\lambda))={\rm tr}(T_{0}(\lambda))$ Since the transition matrices
$T_{j}(\lambda)$ have the same determinants and traces, they have the same
eigenvalues

$\mu^{\pm}(\lambda)={\rm tr}T_{j}/2\pm\sqrt{{\rm
tr}(T_{j})^{2}/4-\det(T_{j})},$ (4.6)

Again, take the square root nonnegative when the argument is nonnegative, and
continuous if the argument is in $\mathbb{C}\setminus i(-\infty,0)$.

Suppose the $2\times 2$ matrix

$\begin{pmatrix}a&b\cr c&d\end{pmatrix}$

has eigenvalues $\mu^{\pm}$. Then

$\begin{pmatrix}a-\mu^{\pm}&b\cr
c&d-\mu^{\pm}\end{pmatrix}\begin{pmatrix}b\cr\mu^{\pm}-a\end{pmatrix}=\begin{pmatrix}0\cr
0\end{pmatrix},$

so the vectors $[b,\mu^{\pm}-a]$ are eigenvectors. Using
$s^{\prime}(\lambda)=c(\lambda)$ these eigenvectors for $T_{j}(\lambda)$ are

$E_{0}^{\pm}(\lambda)=\begin{pmatrix}sc+sc/\delta_{B}\cr\mu^{\pm}-c^{2}-sc^{\prime}/\delta_{B}\end{pmatrix},\quad
E_{1}^{\pm}(\lambda)=\begin{pmatrix}-sc-
sc/\delta_{R}\cr\mu^{\pm}-c^{2}-sc^{\prime}/\delta_{R}\end{pmatrix}$ (4.7)

The eigenvectors $E_{0}^{\pm}(\lambda),E_{1}^{\pm}(\lambda)$ are nonzero
except for a discrete set of $\lambda\in\mathbb{R}$.

When $\lambda$ is real the matrices $T_{j}(\lambda)$ are real-valued. Then if
${\rm tr}(T_{j})^{2}/4-\det(T_{j})$ is nonpositive the eigenvalues are
conjugate pairs, with

$|\mu^{\pm}(\lambda)|=\frac{1}{\sqrt{\delta_{B}\delta_{R}}},\quad\frac{-2}{\sqrt{\delta_{B}\delta_{R}}}\leq{\rm
tr}(T_{j})\leq\frac{2}{\sqrt{\delta_{B}\delta_{R}}}.$ (4.8)

If ${\rm tr}(T_{j})^{2}/4-\det(T_{j})$ is nonnegative, the eigenvalues are
real. Since $\mu^{+}\mu^{-}=1/(\delta_{B}\delta_{R})$, the eigenvalues have
the same sign.

######  Lemma 4.1.

The eigenvalues $\mu^{\pm}(\lambda)$ satisfy

$\lim_{\lambda\to-\infty}e^{-2|{\rm
Im}\sqrt{\lambda}|}\mu^{+}(\lambda)=\frac{\delta_{R}+1}{2\delta_{R}}\frac{\delta_{B}+1}{2\delta_{B}},\quad\lim_{\lambda\to-\infty}e^{2|{\rm
Im}\sqrt{\lambda}|}\mu^{-}(\lambda)=\frac{2}{\delta_{R}+1}\frac{2}{\delta_{B}+1}$
(4.9)

###### Proof.

For $\lambda<0$ let $\omega=\sqrt{\lambda}$ as before. In exponential form

$c(\lambda)=(e^{i\omega}+e^{-i\omega})/2=(e^{-|\omega|}+e^{|\omega|})/2,\quad
c^{\prime}(\lambda)=-\omega(e^{i\omega}-e^{-i\omega})/2i,$
$s(\lambda)=(e^{i\omega}-e^{-i\omega})/(2i\omega)=(e^{-|\omega|}-e^{|\omega|})/(2i\omega),$

Since ${\rm tr}T_{0}(\lambda)={\rm tr}T_{1}(\lambda)$, equation (4.5) gives

$\lim_{\lambda\to-\infty}e^{-2|{\rm Im}\sqrt{\lambda}|}{\rm
tr}\,(T_{j})=\frac{1}{4}[1+\frac{1}{\delta_{R}}+\frac{1}{\delta_{B}}+\frac{1}{\delta_{R}\delta_{B}}]=\frac{\delta_{R}+1}{2\delta_{R}}\frac{\delta_{B}+1}{2\delta_{B}}$

(4.6) first gives the estimate for $\mu^{+}(\lambda)$, with the estimate for
$\mu^{-}(\lambda)$ following from
$\mu^{+}\mu^{-}=\frac{1}{\delta_{R}\delta_{B}}$. ∎

######  Lemma 4.2.

If $|\mu^{\pm}(\lambda)|=1/\sqrt{\delta_{B}\delta_{R}}$, then $\lambda$ is in
the spectrum of ${\cal L}$, and so is real.

###### Proof.

The cases being similar, suppose that $y$ is a nontrivial solution of (4.1) on
$e_{0}$ whose initial data at the left endpoint $x=0$ is an eigenvector for
$T_{0}(\lambda)$ with eigenvalue $\mu^{-}$. Extend $y$ to the subtree
$\mathcal{T}_{0}$ using $y(x+2)=\mu^{-}y(x)$ along each ray based at $r_{0}$.
The self adjoint conditions (2.1) hold for $y$ except possibly at $r_{0}$.

These extended solutions decay as $x\to\infty$. For $2(n+1)>0$ let
$\mathcal{T}_{2n+1}$ denote the subtree of $\mathcal{T}_{0}$ with
$x\leq(2n+1)$. Then

$\int_{\mathcal{T}_{2n+1}}|y|^{2}\geq\sum_{k=1}^{n}(\delta_{B}\delta_{R})^{k}\int_{0\leq
x\leq 2}|(\mu^{-})^{k}y|^{2}=(n-1)\int_{0\leq x\leq 2}|y|^{2},$

while $y$ satisfies (4.1) on $\mathcal{T}_{2n+1}$. The functions $y$ on
$\mathcal{T}_{2n+1}$ can be modified [7, Lem 3.2] on the edges with $0\leq
x\leq 1$ and $2n\leq x\leq 2n+2$ to put $y$ in the domain of ${\mathcal{L}}$
with $\|{\mathcal{L}}y\|_{2}\leq C$. Then $f=y/\|y\|_{2}$ has norm $1$ while
$\|{\mathcal{L}}f\|_{2}\to 0$ as $n\to\infty$. $\lambda$ is thus in the
spectrum of the self adjoint operator ${\mathcal{L}}$. ∎

By Lemma 4.2 the set

$\sigma_{1}=\\{\lambda\in\mathbb{C}\ \bigl{|}\
|\mu^{\pm}(\lambda)|=|\delta_{R}\delta_{B}|^{-1/2}\\}=\\{\lambda\in\mathbb{R}\
\big{|}{\rm tr}(T_{j})^{2}-4\det(T_{j})\leq 0\\}$

is contained in a half line $[0,\infty)$. The next result describes the main
features of $\mu^{\pm}(\lambda)$.

######  Theorem 4.3.

The eigenvalues $\mu^{\pm}(\lambda)$ may be chosen to be single valued
analytic functions in the complement of $\sigma_{1}$ with the asymptotic
behaviour given in Lemma 4.1. On this domain
$|\mu^{+}(\lambda)|>1/\sqrt{\delta_{R}\delta_{B}}$ and
$|\mu^{-}(\lambda)|<1/\sqrt{\delta_{R}\delta_{B}}$. These functions
$\mu^{+}(\lambda)$ and $\mu^{-}(\lambda)$ have continuous extensions to the
real axis from the upper and lower half planes which are analytic except on
the discrete set where ${\rm tr}(T_{j})^{2}=4/(\delta_{R}\delta_{B})$. If
$\nu\in\sigma_{1}$ then

$\lim_{\epsilon\to
0^{+}}\mu^{\pm}(\nu+i\epsilon)-\mu^{\pm}(\nu-i\epsilon)=2i\,{\rm
Im}\,(\mu^{\pm}(\nu))\,.$ (4.10)

###### Proof.

Since ${\rm tr}(T_{j})$ and $\det(T_{j})$ are entire functions of $\lambda$,
the eigenvalues $\mu^{\pm}(\lambda)$ (and eigenvectors (4.7)) will be analytic
in any simply connected domain with ${\rm
tr}(T_{j})^{2}-4/(\delta_{R}\delta_{B})\not=0$. Use
$U=\mathbb{C}\setminus[0,\infty)$ as such a domain.

The eigenvalues satisfy $\mu^{+}\mu^{-}=1/(\delta_{R}\delta_{B})$, so
$|\mu^{+}|$ and $|\mu^{-}|$ and are distinct in
$\mathbb{C}\setminus\sigma_{1}$. Since
$|\mu^{+}(\lambda)|>1/\sqrt{\delta_{R}\delta_{B}}$ and
$|\mu^{-}(\lambda)|<1/\sqrt{\delta_{R}\delta_{B}}$ in $U$, the extensions
across $\mathbb{R}\setminus\sigma_{1}$ are single valued.

To obtain the continuous extension to the real axis, note that the set of
points where the eigenvalues coalesce, or ${\rm
tr}(T_{j})^{2}-4/(\delta_{R}\delta_{B})=0$, is the zero set of an entire
function, which has isolated (real) zeroes $r_{i}$. The analytic functions
$\mu^{\pm}(\lambda)$, given by (4.6), thus have an analytic continuation from
either half plane to the real axis with these points $r_{i}$ omitted. At these
points

$\lim_{\lambda\to r_{i}}\mu^{\pm}(\lambda)=\mbox{tr}\,(T_{j})/2$

independent of the branch of the square root.

We have observed in Lemma 4.2 that if
$|\mu^{\pm}(\nu)|=1/\sqrt{\delta_{R}\delta_{B}}$, then $\nu\in\mathbb{R}$. If
${\rm tr}\,(T_{j})^{2}=\det(T_{j})=4/(\delta_{R}\delta_{B})$, then both sides
of (4.10) are $0$. Suppose instead that ${\rm
tr}\,(T_{j})^{2}/4-\det(T_{j})<0$, so that the eigenvalues $\mu^{\pm}(\nu)$
are a nonreal conjugate pair. Since the eigenvalues are distinct, they extend
analytically across the real axis. There are two possibilities: either (i)
(4.10) holds, in which case the extension of $\mu^{\pm}(\nu+i\epsilon)$ is
$\mu^{\mp}(\nu-i\epsilon)$, or (ii) $\mu^{\pm}(\nu+i\epsilon)$ extends to
$\mu^{\pm}(\nu-i\epsilon)$. The second case will be excluded because
$|\mu^{+}|>1/\sqrt{\delta_{R}\delta_{B}}$ in the complement of $\sigma_{1}$.
If (ii) held, then $\mu^{+}$ would be an analytic function of $\lambda$ in a
neighborhood of $\nu$ satisfying
$|\mu^{+}(\nu)|=1/\sqrt{\delta_{R}\delta_{B}}$, and $|\mu^{+}(\lambda)|\geq
1/\sqrt{\delta_{R}\delta_{B}}$. But this violates the open mapping theorem
[11, p. 162], so (i) must hold. The treatment of $\mu^{-}$ is the same. ∎

Define additional solutions of (4.1) on $(0,1)$ by

$V(x,\lambda)=sc(1+\frac{1}{\delta_{B}})\cos(\omega
x)+[\mu^{-}-c^{2}-\frac{sc^{\prime}}{\delta_{B}}]\sin(\omega x)/\omega,$
$U(x,\lambda)=-sc(1+\frac{1}{\delta_{R}})\cos(\omega(1-x))-[\mu^{-}-c^{2}-\frac{sc^{\prime}}{\delta_{R}}]\sin(\omega(1-x))/\omega.$

$V(x,\lambda)$ (resp. $U(x,\lambda)$) has initial data at $x=0^{+}$ (resp.
$x=1^{-}$) given by the eigenvector $E_{0}^{-}$ (resp. $E_{1}^{-}$).

######  Theorem 4.4.

If $\lambda\in\mathbb{C}\setminus\sigma_{1}$ then $V(x,\lambda)$ may be
extended to a solution of (4.1) on $\mathcal{T}_{0}$ which satisfies the
vertex conditions (4.2), and so (2.1), for $x>0$, and is square integrable on
$\mathcal{T}_{0}$. The analogous statements hold for $U(x,\lambda)$ on
$\mathcal{T}_{1}$.

###### Proof.

If $\lambda\in\mathbb{C}\setminus\sigma_{1}$ then by Theorem 4.3 the
eigenvalue $\mu^{-}(\lambda)$ is well defined. Extend $V(x,\lambda)$ as a
solution to (4.1) on $x>1$ using the conditions (4.2). For integers $n>0$, the
initial data at $x=2n^{+}$ is given by

$\begin{pmatrix}V(2n^{+},\lambda)\cr
V^{\prime}(2n^{+},\lambda)\end{pmatrix}=T_{0}^{n}(\lambda)\begin{pmatrix}V(0^{+},\lambda)\cr
V^{\prime}(0^{+},\lambda)\end{pmatrix}=(\mu^{-})^{n}\begin{pmatrix}V(0^{+},\lambda)\cr
V^{\prime}(0^{+},\lambda)\end{pmatrix}.$

Since $|\mu^{-}(\lambda)|<1/\sqrt{\delta_{R}\delta_{B}}$ the computation

$\int_{\cal
T_{R}}|y|^{2}=\sum_{k=0}^{\infty}(\delta_{B}\delta_{R})^{k}\int_{0\leq x\leq
2}|(\mu^{-})^{k}y|^{2}=\sum_{k=0}^{\infty}\big{(}\delta_{B}\delta_{R}(\mu^{-})^{2}\big{)}^{k}\int_{0\leq
x\leq 2}|y|^{2},$

establishes the square integrability. ∎

###  4.2 The resolvent and spectrum for trees

The resolvent $({\mathcal{L}}-\lambda I)^{-1}$ is defined in the resolvent set
$\rho$, the complement of the spectrum of ${\mathcal{L}}$. The solutions $U$
and $V$ of Theorem 4.4 can be used to construct the resolvent of ${\cal L}$ on
${\cal T}$. The Wronskian
$W(\lambda)=W(U,V)=U(x,\lambda)V^{\prime}(x,\lambda)-U^{\prime}(x,\lambda)V(x,\lambda)$,
defined for $x\in(0,1)$, is independent of $x$. Evaluation at $x=1^{-}$ gives

$W(\lambda)=\Bigl{[}sc(1+\frac{1}{\delta_{B}})c^{\prime}+(\mu^{-}-c^{2}-\frac{sc^{\prime}}{\delta_{B}})c\Bigr{]}sc(1+\frac{1}{\delta_{R}})$
(4.11)
$+s\Bigl{[}(1+\frac{1}{\delta_{B}})c^{2}+(\mu^{-}-c^{2}-\frac{sc^{\prime}}{\delta_{B}})\Bigr{]}\Bigl{[}(\mu^{-}-c^{2}-\frac{sc^{\prime}}{\delta_{R}})\Bigr{]}$

The identity $sc^{\prime}-c^{2}=sc^{\prime}-cs^{\prime}=-1$ leads to a
simplification,

$W(\lambda)=s\Bigl{[}c^{2}(1+\frac{1}{\delta_{B}})+(\mu^{-}-c^{2}-\frac{sc^{\prime}}{\delta_{B}})\Bigr{]}\Bigl{[}c^{2}(1+\frac{1}{\delta_{R}})+(\mu^{-}-c^{2}-\frac{sc^{\prime}}{\delta_{R}})\Bigr{]}$
$-sc^{2}(1+\frac{1}{\delta_{B}})(1+\frac{1}{\delta_{R}})$
$=s\Bigl{[}\frac{1}{\delta_{B}}+\mu^{-}\Bigr{]}\Bigl{[}\frac{1}{\delta_{R}}+\mu^{-}\Bigr{]}-sc^{2}(1+\frac{1}{\delta_{B}})(1+\frac{1}{\delta_{R}}).$

Define

$\sigma_{2}=\\{\lambda\in\mathbb{C}\setminus\sigma_{1}\ |\ W(\lambda)=0\\}.$

######  Lemma 4.5.

$\sigma_{2}$ is a discrete subset of $\mathbb{R}\setminus\sigma_{1}$. If
$\delta_{R}\delta_{B}>1$ and $s(\lambda)=0$ then $\lambda\in\sigma_{2}$. If
$\lambda\in\sigma_{2}$ and $U$ and $V$ are not identically zero, which is the
case if $s(\lambda)=0$, then $\lambda$ is a eigenvalue of ${\mathcal{L}}$.

###### Proof.

Having initial data $E_{0}^{-}(\lambda)$ and $E_{1}^{-}(\lambda)$, the
solutions $V(x,\lambda)$ and $U(x,\lambda)$ are not identically $0$ except for
a discrete set of $\lambda\in\mathbb{R}$. The vanishing of $W(\lambda)$ means
that $V$ and $U$ are linearly dependent on $(0,1)$. If
$U(x,\lambda)=bV(x,\lambda)$ for some constant $b$ and
$\lambda\in\mathbb{C}\setminus\sigma_{1}$, the function

$w(x,\lambda)=\Bigl{\\{}\begin{matrix}bV(x,\lambda),x\in\mathcal{T}_{0}\cr
U(x,\lambda),x\in\mathcal{T}_{1}\end{matrix}\Bigr{\\}}$

is an nontrivial eigenfunction of ${\mathcal{L}}$. Since ${\mathcal{L}}$ is
self-adjoint, $\lambda\in\mathbb{R}$ and $W(\lambda)\not=0$ for
$\lambda\in\mathbb{C}\setminus\mathbb{R}$. The discreteness of $\sigma_{2}$
follows since $W(\lambda)$ is analytic in $\mathbb{C}\setminus\sigma_{1}$.

If $s(\lambda)=0$ then $W(\lambda)=0$ and $c^{2}(\lambda)=1$. Thus
$tr(T_{j}(\lambda))^{2}/4-\det T_{j}(\lambda)=(1-1/(\delta_{B}\delta_{R}))/4$,
which is strictly positive if $\delta_{R}\delta_{B}>1$, and
$\lambda\notin\sigma_{1}$ by (4.6). Since
$|\mu^{-}|<1/\sqrt{\delta_{B}\delta_{R}}$, the initial data for $V(x,\lambda)$
and $U(x,\lambda)$ is nonzero by (4.7).

∎

For $\lambda\in\mathbb{C}\setminus(\sigma_{1}\cup\sigma_{2})$ define the
kernel

$R_{e}(x,t,\lambda)=\left\\{\begin{array}[]{ll}-U(x,\lambda)V(t,\lambda)/W,\quad-\infty<x\leq
t,0\leq t\leq 1\,,\\\ -U(t,\lambda)V(x,\lambda)/W,\quad 0\leq t\leq 1,t\leq
x<\infty\,.\end{array}\right\\}.$ (4.12)

Suppose $f_{e}:[0,1]\to\mathbb{C}$ has support in $(0,1)$. A simple
computation [4, p. 309] shows that the function

$h_{e}(x)=\int_{0}^{1}R_{e}(x,t,\lambda)f_{e}(t)\,dt$

satisfies $[-D^{2}-\lambda]h_{e}=f_{e}$. By Theorem 4.4 $h_{e}$ is square
integrable on ${\cal T}$ and satisfies the boundary conditions (2.1) at each
vertex of $\mathcal{T}$. Thus $h_{e}$ is in the domain of ${\cal L}$. Since
integration of $f_{e}$ against the meromorphic kernel $R_{e}(x,t,\lambda)$
agrees with the resolvent $R(\lambda)f_{e}$ as long as $W(\lambda)\not=0$,
they must agree for all $\lambda\in\rho$.

For $f\in L^{2}({\cal T})$, let $f_{e}$ denote the restriction of $f$ to the
edge $e$ with the edge orientation described for (4.12).

######  Theorem 4.6.

For $\lambda\in\mathbb{C}\setminus(\sigma_{1}\cup\sigma_{2})$,

$R(\lambda)f=\sum_{e}\int_{0}^{1}R_{e}(x,t,\lambda)f_{e}(t)\,dt,$ (4.13)

the sum converging in $L^{2}({\cal T})$.

###### Proof.

The formula (4.13) agrees with the resolvent of ${\mathcal{L}}$ in the
resolvent set, which includes $\mathbb{C}\setminus\mathbb{R}$. Let $[a,b]$ be
a compact interval contained in
$\mathbb{R}\setminus\\{\sigma_{1}\cup\sigma_{2}\\}$. If $P$ denotes the family
of spectral projections for ${\cal L}$, then [17, p. 237,264] for any $f\in
L^{2}({\cal T})$

$\frac{1}{2}[P_{[a,b]}+P_{(a,b)}]f=\lim_{\epsilon\downarrow 0}\frac{1}{2\pi
i}\int_{a}^{b}[R(\lambda+i\epsilon)-R(\lambda-i\epsilon)]f\ d\lambda\,.$
(4.14)

By the observations above, the right hand side of (4.14) vanishes on the dense
set of $f$ supported on finitely many edges. This means that
$[P_{[a,b]}+P_{(a,b)}]f=0$ for all $f\in L^{2}({\cal T})$, and $[a,b]$ is in
the resolvent set $\rho$. Thus
$\mathbb{C}\setminus\\{\sigma_{1}\cup\sigma_{2}\\}\subset\rho$.

∎

##  5 Closed walks and resolvent traces

In this section the analysis of the resolvent of the biregular tree $R_{\cal
T}(\lambda)$ is extended to the resolvent $R_{\cal G}(\lambda)$ of a general
biregular graph ${\cal G}$. $\mathcal{T}$ and ${\mathcal{G}}$ are linked via
the theory of covering spaces; see [15] and [12] for this material are sources
for the theory and its application to graphs. A feature of the approach using
covering spaces is that generating functions for closed nonbacktracking walks
in ${\mathcal{G}}$ arise naturally.

###  5.1 Walks

A combinatorial walk of length $l$ in ${\mathcal{G}}$ (or $\mathcal{T}$)
starting at the vertex $v_{1}$ and ending at $v_{l+1}$ is a sequence
$v_{1},e_{1},v_{2},e_{2},\dots,e_{l},v_{l+1}$ with adjacent vertices
$v_{i},v_{i+1}$ joined by edges $e_{i}$. A walk is closed if $v_{1}=v_{l+1}$,
and nonbacktracking if consecutive undirected edges are distinct. A closed
walk may be nonbacktracking if the edge $\\{v_{1},v_{2}\\}$ is the same as
$\\{v_{1},v_{l+1}\\}$; in the terminology of [18] tails are allowed.

If $\eta_{l}$ denotes the number of nonbacktracking closed walks of length
$l\geq 1$ in ${\mathcal{G}}$, then
$p_{{\mathcal{G}}}(z)=N_{\mathcal{E}}+\sum_{l=1}^{\infty}\eta_{l}z^{l}$ will
be the associated generating function. When ${\mathcal{G}}$ is finite with
adjacency matrix $A$, an elementary result in graph spectral theory gives the
number ${\widetilde{\eta}_{l}}$ of closed walks of length $l$ (with
backtracking allowed) as the trace of the $l-th$ power of $A$. The comparison
$\eta_{l}\leq{\widetilde{\eta}_{l}}$ can be used to show that
$p_{{\mathcal{G}}}(z)$ converges to an analytic function in a neighborhood of
$z=0$.

Using an identification of the edges with intervals of unit length, there is
an edgepath $\gamma:[0,l]\to{\mathcal{G}}$ which traverses the edges $e_{i}$
of a walk in order at unit speed. Any loop in ${\mathcal{G}}$ with basepoint
$v_{1}$ is homotopic [12, p. 86] to such an edgepath. By adding vertices of
degree $2$ (without changing the lengths of the original edges), closed
edgepaths may be assumed to start and end at edge midpoints.

It will be useful to determine the walk generating function
$p_{{\mathcal{G}}}(z)$ for the complete bipartite graphs $K(m_{B},m_{R})$ with
$m_{B}$ vertices in $\mathcal{V}_{B}$ and $m_{R}$ vertices in
$\mathcal{V}_{R}$. Closed walks in bipartite graphs have even length, so
assume $l=2k$ is even. Start by counting the number of nonbacktracking walks
of length $2k-1$ starting at $v\in\mathcal{V}_{R}$ and ending in
$\mathcal{V}_{B}$. The vertex $v$ may be followed by any of $m_{B}$ vertices
in $\mathcal{V}_{B}$. To avoid backtracking, there are then $m_{R}-1$
available vertices in $\mathcal{V}_{R}$, then $m_{B}-1$ available vertices in
$\mathcal{V}_{B}$, and so on. After $2k-1$ steps the number of such walks is
$m_{B}(m_{R}-1)^{k-1}(m_{B}-1)^{k-1}$. The last step must return to $v$, but
to avoid backtracking the walks which returned to $v$ after $2k-2$ steps are
omitted. The count $C_{k}$ of closed nonbacktracking walks of length $2k$
starting at $v$ satisfies $C_{k}=m_{B}(m_{R}-1)^{k-1}(m_{B}-1)^{k-1}-C_{k-1}$.
Multiplying by the number of starting $R$ vertices and doing the same for
starts in $\mathcal{V}_{B}$ shows that the total number $W_{k}$ of closed
nonbacktracking walks of length $2k$ with designated starting vertex satisfies

$W_{k}=2m_{R}m_{B}(m_{R}-1)^{k-1}(m_{B}-1)^{k-1}-W_{k-1},\quad k\geq 2,\quad
W_{1}=0.$

That is, for $k\geq 2$,

$W_{k}=2m_{R}m_{B}(-1)^{1-k}\sum_{j=1}^{k-1}(-1)^{j}(m_{R}-1)^{j}(m_{B}-1)^{j}$
$=\frac{2m_{R}m_{B}(m_{R}-1)(m_{B}-1)}{1+(m_{R}-1)(m_{B}-1)}[(m_{R}-1)^{k-1}(m_{B}-1)^{k-1}+(-1)^{k}]$

Adding the number of edges for order zero term gives the generating function

$P_{CG}(z)=\frac{m_{R}m_{B}}{2}+\frac{2m_{R}m_{B}(m_{R}-1)(m_{B}-1)}{1+(m_{R}-1)(m_{B}-1)}\times$
(5.1)
$\times\Big{[}\sum_{k=2}^{\infty}(m_{R}-1)^{k-1}(m_{B}-1)^{k-1}z^{k}+\sum_{k=2}^{\infty}(-1)^{k}z^{k}\Big{]}$
$=\frac{m_{R}m_{B}}{2}+\frac{2m_{R}m_{B}(m_{R}-1)(m_{B}-1)}{1+(m_{R}-1)(m_{B}-1)}\Big{[}\frac{(m_{R}-1)(m_{B}-1)z^{2}}{1-(m_{R}-1)(m_{B}-1)z}+\frac{z^{2}}{1+z}\Big{]}.$

$W_{k}$ is a count of walks of length $2k$, so the closed nonbacktracking walk
generating function is

$p_{CG}(z)=P_{CG}(z^{2})=$ (5.2)
$\frac{m_{R}m_{B}}{2}+\frac{2m_{R}m_{B}(m_{R}-1)(m_{B}-1)}{1+(m_{R}-1)(m_{B}-1)}\Big{[}\frac{(m_{R}-1)(m_{B}-1)z^{4}}{1-(m_{R}-1)(m_{B}-1)z^{2}}+\frac{z^{4}}{1+z^{2}}\Big{]}.$

Suppose $\\{r,b\\}$ is an edge of $K(m_{B},m_{R})$, or any bipartite graph,
with midpoint $w$. The closed nonbacktracking walks have one walk starting at
$b$ and followed by $r$, and one starting at $r$ and followed by $b$. Without
changing the count, these walks can be viewed as starting at $w$ followed by
$b$ or $r$. This alternate view will be useful later.

###  5.2 Coverings

Each biregular graph ${\mathcal{G}}$ has a universal covering space
$({\mathcal{T}},p)$, where as before $\mathcal{T}$ is the biregular tree. The
continuous map $p:\mathcal{T}\to{\mathcal{G}}$ is such that for each
$x\in{\mathcal{G}}$ there is an open neighborhood $N$ containing $x$ such that
$p^{-1}(N)$ is a union of pairwise disjoint sets, each homeomorphic to $N$.
The $R,B$ labeling of tree vertices can be chosen so that $p$ preserves vertex
class.

Pick basepoints $\xi_{0}\in{\mathcal{G}}$ and $\widetilde{\xi}_{0}\in
p^{-1}(\xi_{0})$. If $\widetilde{\gamma}$ is a nonbacktracking edgepath in
$\mathcal{T}$ starting at $\widetilde{\xi}_{0}$ and ending at
$\widetilde{\xi}_{1}\in p^{-1}(\xi_{0})$, then $\gamma=p(\widetilde{\gamma})$
will be a closed nonbacktracking edgepath in ${\mathcal{G}}$. Every closed
nonbacktracking edgepath arises in this way [12, p. 86].

Suppose that $\xi_{0}$ is a point in the interior of the edge $e_{0}\in{\cal
G}$, and that $\widetilde{\xi}_{0}\in p^{-1}(\xi_{0})$. Let
$\widetilde{e}_{0}$ be the edge of ${\cal T}$ containing
$\widetilde{\xi}_{0}$. Then given any function $f\in L^{2}(e_{0})$, there is a
corresponding function $\widetilde{f}\in L^{2}(\mathcal{T})$ such that

$\widetilde{f}(\widetilde{\xi})=\left\\{\begin{array}[]{ll}f(p(\widetilde{\xi})),&\widetilde{\xi}\in\widetilde{e}_{0}\,,\\\
0,&\widetilde{\xi}\notin\widetilde{e}_{0}\end{array}\right\\}.$

######  Proposition 5.1.

Suppose that $f\in L^{2}({\cal G})$ has support on an edge $e_{0}$. There is a
$C>0$ such that if $|Im(\sqrt{\lambda})|>C$ then for $\xi\in{\cal G}$

$[R_{\cal G}(\lambda)f](\xi)=\sum_{\widetilde{\xi}\in p^{-1}(\xi)}[R_{\cal
T}(\lambda)\widetilde{f}](\widetilde{\xi}).$

The sum and its first two derivatives converge uniformly for $\xi\in{\cal G}$.

###### Proof.

The proof has two parts: a formal verification and a proof that the sum
converges. Consider the two sums

$H(\xi,\lambda)=\sum_{\widetilde{\xi}\in p^{-1}(\xi)}[R_{\cal
T}(\lambda)\widetilde{f}](\widetilde{\xi}),\quad
h(\xi,\lambda)=\sum_{\widetilde{\xi}\notin\widetilde{e}_{0}}[R_{\cal
T}(\lambda)\widetilde{f}](\widetilde{\xi}).$

Note that

$(-D^{2}-\lambda)H(\xi,\lambda)=\left\\{\begin{array}[]{ll}f(\xi),&\xi\in
e_{0},\\\ 0,&\xi\notin e_{0}.\end{array}\right.$

Since the vertex conditions are satisfied in the tree, they are still
satisfied when we sum over vertices in the tree.

To check on the convergence of $H(\xi,\lambda)$ it suffices to check
$h(\xi,\lambda)$. Since the local homeomorphism of edges extends to edge pairs
$\\{r_{n},b_{n}\\},\\{b_{n},r_{n+1}\\}$, uniform convergence of the series for
the $k-th$ derivative, $k=0,1,2$ of $h(\xi,\lambda)$ is implied by

$\sum_{n=0}^{\infty}(\delta_{B}\delta_{R}|\mu^{-}|)^{n}<\infty,$

or $\delta_{B}\delta_{R}|\mu^{-}(\lambda)|<1$. For $C$ sufficiently large,
this holds for $|\,{\rm Im}\,(\sqrt{\lambda})|>C$ by Lemma 4.1.

If ${\cal G}$ is not a finite graph we must still check that $h\in
L^{2}({\mathcal{G}})$. Let $e_{a}\in{\mathcal{G}}$ denote an edge pair as
above. It will suffice to consider the summands of $h$ with
$\widetilde{\xi}\in\mathcal{T}_{0}$. This contribution to the
$L^{2}({\mathcal{G}})$ norm is dominated by a sum

$\sum_{e_{a}\in{\cal
G}}\int_{0}^{2}|V(x,\lambda)|^{2}|\sum_{\widetilde{e_{a}}\in
p^{-1}(e_{a})}(\mu^{-})^{k(m)/2}|^{2},$

where the sum is taken over distinct edge pairs $e_{a}$, and $k(m)$ (which may
be taken even) is the distance from the tree root $r_{0}$ to
$\widetilde{e_{a}}$.

This sum converges with

$\sum_{e_{a}}|S_{e_{a}}|^{2},\quad S_{e_{a}}=\sum_{\widetilde{e_{a}}\in
p^{-1}(e_{a})}(\mu^{-})^{k(m)}.$

If the largest magnitude of a term in $S_{e_{a}}$ is $|\mu^{-}|^{n}$, then

$|S_{e_{a}}|\leq\sum_{j=n}^{\infty}(\delta_{R}\delta_{B}|\mu^{-}|)^{j}\leq\frac{\delta_{R}\delta_{B}|\mu^{-}|^{n}}{1-\delta_{R}\delta_{B}|\mu^{-}|}.$

There are at most $(\delta_{R}\delta_{B})^{n}$ sums $S_{e_{a}}$ with a leading
term whose magnitude is as large as $|\mu^{-}|^{n}$. This count gives the
bound

$\sum_{e_{a}}|S_{e_{a}}|^{2}\leq\sum_{n}(\delta_{R}\delta_{B})^{n}\Bigl{(}\frac{(\delta_{R}\delta_{B})^{n}|\mu^{-}|^{n}}{1-\delta_{R}\delta_{B}|\mu^{-}|}\Bigr{)}^{2}\leq\frac{1}{[1-\delta_{R}\delta_{B}|\mu^{-}|]^{2}}\sum_{n}(\delta_{R}\delta_{B})^{3n}|\mu^{-}|^{2n}.$

Thus $h$ is square integrable if $(\delta_{R}\delta_{B})^{3}|\mu^{-}|^{2}<1$.

After modifying $C$, it follows that $H(\xi,\lambda)$ is in the domain of
$\cal L$, with $(-D^{2}-\lambda)H(\xi,\lambda)=f$.

∎

The diagonal of the resolvent kernel and the trace of the resolvent of a
finite biregular graph ${\mathcal{G}}$ contain information about closed walks
in ${\mathcal{G}}$. Let $e$ be an edge of the biregular graph ${\mathcal{G}}$
with midpoint $g$ and vertices $r$ and $b$ of $e$ identified with $[0,1]$ as
above. Define $P_{e}(z)=1+\sum_{l>0}\eta_{l}z^{l/2}$ with coefficients
$\eta_{l}$ counting closed nonbacktracking walks of length $l$ starting at
$g$. Recall that $\eta_{l}=0$ if $l$ is odd.

######  Theorem 5.2.

For $|\,{\rm Im}\,(\sqrt{\lambda})|>C$ and $t\in e$ the diagonal of the
resolvent may be written as

$R_{\cal
G}(t,t,\lambda)=P_{e}(\mu^{-}(\lambda))\frac{U(t,\lambda)V(t,\lambda)}{-W(\lambda)},\quad
t\in e.$ (5.3)

If ${\cal G}$ is a finite biregular graph with $N_{\mathcal{E}}$ edges, then

${\rm tr}R_{\cal
G}(\lambda)=\frac{P_{{\mathcal{G}}}(\mu^{-}(\lambda))}{-W(\lambda)}\int_{0}^{1}U(t,\lambda)V(t,\lambda)\
dt,$ (5.4)

The function
$P_{{\mathcal{G}}}(z)=\sum_{e}P_{e}(z)=N_{\mathcal{E}}+\sum_{l>0}\eta_{l}z^{l/2}$,
where $\eta_{l}$ counts closed nonbacktracking walks of length $l$, with one
of the $N_{\mathcal{E}}$ basepoints at the midpoint of an edge.

###### Proof.

Fix $\widetilde{g}\in\mathcal{T}$, identifying the edge containing $g$ with
$[0,1]$ and let the function $x:\mathcal{T}\to\mathbb{R}$ be as described
above.

Suppose first that $\xi\in e$, where $f$ is supported. Split the resolvent sum
into three parts,

$[R_{\cal G}(\lambda)f](\xi)=[R_{\cal
T}^{0}(\lambda)\widetilde{f}](\xi)+[R_{\cal
T}^{+}(\lambda)\widetilde{f}](\xi)+[R_{\cal
T}^{-}(\lambda)\widetilde{f}](\xi),$ (5.5)

where the $0,+,-$ terms are the resolvent sums of Theorem 5.1 coming
respectively from $\widetilde{\xi}\in\widetilde{e}$, $x(\widetilde{\xi})>1$
and $x(\widetilde{\xi})<0$. In the following sums, $e_{m}\in p^{-1}(e)$ means
that there is a closed edgepath $\gamma$ starting at $g$ which lifts to a path
$\widetilde{\gamma}$ based at $\widetilde{g}$ and ending in $e_{m}$. Let
$l(m)=2k$ be the length of $\widetilde{\gamma}$. The three terms are given by
integration against kernels, with $0\leq t\leq 1$. $R_{\cal
T}^{0}(x,t,\lambda)$ is given by (4.12), while

$R^{+}(x,t,\lambda)=\frac{U(t,\lambda)V(x,\lambda)}{-W(\lambda)}\sum_{x(e_{m})>1}[\mu^{-}(\lambda)]^{l(m)/2},\quad
e_{m}\in p^{-1}(e),$ (5.6)

and

$R^{-}(x,t,\lambda)=\frac{V(t,\lambda)U(x,\lambda)}{-W(\lambda)}\sum_{x(e_{m})<0}[\mu^{-}(\lambda)]^{l(m)/2},\quad
e_{m}\in p^{-1}(e).$ (5.7)

That is, a closed nonbacktracking walk of length $l$ contributes powers
$\mu^{-}(\lambda)^{l/2}$. In case $\xi\notin e$ the term $R_{\cal T}^{0}$ will
be missing, but otherwise the representation of the resolvent will have the
same form.

Introduce the functions

$P^{+}_{e}(z)=\sum_{x(e_{m})>1}z^{l(m)/2}=\sum_{l>0}\eta^{+}_{l}z^{l/2},\quad
P^{-}_{e}(z)=\sum_{x(e_{m})<0}z^{l(m)/2}=\sum_{l>0}\eta^{-}_{l}z^{l/2},$

and $P_{e}(z)=1+P^{+}_{e}(z)+P^{-}_{e}(z)$. The coefficients $\eta^{+}_{l}$,
$\eta^{-}_{l}$, count closed edgepaths in ${\mathcal{G}}$ based at the
midpoint of $e$, and whose lift from the midpoint of $\tilde{e}$ to the
midpoint of $\tilde{e}$ has length $l$, with $x(\tilde{e})$ respectively
greater than $1$ or less than $0$. Setting $x=t$ and including the three terms
in (5.5) gives the description of the diagonal of the resolvent in the
statement of the theorem. ∎

Notice that (5.4) expresses ${\rm tr}R_{\cal G}(\lambda)$ as a product, with
the factor

$\frac{1}{W(\lambda)}\int_{0}^{1}U(t,\lambda)V(t,\lambda)\ dt$

independent of ${\mathcal{G}}$. Dividing the general case of (5.4) by the
example of the complete bipartite graph with the same degrees gives the
corollary

$\frac{P_{{\mathcal{G}}}(\mu^{-}(\lambda))}{P_{CB}(\mu^{-}(\lambda))}=\frac{{\rm
tr}R_{\cal G}(\lambda)}{{\rm tr}R_{CB}(\lambda)}.$ (5.8)

###  5.3 Structure of $P_{{\mathcal{G}}}(z)$

The effectiveness of (5.8) is based on our knowledge of three of the four
functions which appear. The resolvent trace ${\rm tr}R_{\cal G}(\lambda)$ is
computed in (2.5) from the eigenvalues of the discrete Laplacian $\Delta$. The
special case ${\rm tr}R_{CB}(\lambda)$ is then presented in (3.1). For the
complete bipartite graph $m_{B}=\delta_{R}+1$ and $m_{R}=\delta_{B}+1$, so
(5.2) becomes

$P_{CG}(\mu^{-}(\lambda))=\frac{(\delta_{B}+1)(\delta_{R}+1)}{2}$ (5.9)
$+\frac{2(\delta_{B}+1)(\delta_{R}+1)\delta_{B}\delta_{R}}{1+\delta_{B}\delta_{R}}\Big{[}\frac{\delta_{B}\delta_{R}\mu^{-}(\lambda)^{2}}{1-\delta_{B}\delta_{R}\mu^{-}(\lambda)}+\frac{\mu^{-}(\lambda)^{2}}{1+\mu^{-}(\lambda)}\Big{]}$

The tree based term in (5.4) satisfies

$-\frac{1}{W(\lambda)}\int_{0}^{1}U(t,\lambda)V(t,\lambda)\ dt={\rm
tr}R_{CB}(\lambda)/P_{CB}(\mu^{-}(\lambda)).$

From (5.1) it is easy to verify that the generating function $P_{CG}(z)$ in
series form converges to an analytic function for
$|z|<\frac{1}{\delta_{B}\delta_{R}}$, and that it extends to a rational
function for $z\in\mathbb{C}$. Currently, the function
$P_{{\mathcal{G}}}(\mu^{-}(\lambda))$ is only defined on the range of
$\mu^{-}(\lambda)$. As described in Theorem 4.3,
$|\mu^{-}(\lambda)|<1/\sqrt{\delta_{B}\delta_{R}}$. Since $P_{CG}(z)$ has a
rational extension, (5.8) can be used to extend $P_{{\mathcal{G}}}(z)$ by
taking $z=\Psi(\lambda)$, where

$z=\Psi(\lambda)=\Bigl{\\{}\begin{matrix}\mu^{-}(\lambda),&|z|<1/\sqrt{\delta_{R}\delta_{B}},\cr\mu^{+}(\lambda),&|z|>1/\sqrt{\delta_{R}\delta_{B}}.\end{matrix}\Bigr{\\}}$
(5.10)

The trace formula

$\mu^{+}(\lambda)+\mu^{-}(\lambda)=\mu^{-}+1/(\delta_{R}\delta_{B}\mu^{-})={\rm
tr}(T_{j}(\lambda))$ (5.11)

leads to consideration of the mapping $\phi(z)=z+1/(cz)$, where
$z\in\mathbb{C}\setminus\\{0\\}$ and $c>0$. This discussion follows [14, p.
89], where additional information is available. If $w=z+1/(cz)$, then
$2z=w\pm\sqrt{w^{2}-4/c}$, and $\phi(z)$ is two to one unless $w=\pm
2c^{-1/2}$. Since $w\pm\sqrt{w^{2}-4/c}\not=0$ for $w\in\mathbb{C}$, $\phi(z)$
is also surjective.

In addition, $\phi(z)=\phi(1/(cz))$, so $\phi$ is injective for $|z|<c^{-1/2}$
and $|z|>c^{-1/2}$. The image of the circle $z=c^{-1/2}e^{i\theta}$ is the
interval $[-2c^{-1/2},2c^{-1/2}]$. Thus
$\phi:\\{0<|z|<c^{-1/2}\\}\to\mathbb{C}\setminus[-2c^{-1/2},2c^{-1/2}]$ and
$\phi:\\{|z|>c^{-1/2}\\}\to\mathbb{C}\setminus[-2c^{-1/2},2c^{-1/2}]$ are both
conformal maps.

To extend the definition of $z$ in (5.10), first note that
${\mathcal{C}}=\\{(\lambda,\mu^{\pm}(\lambda))\in\mathbb{C}^{2}\\}$ is a
Riemann surface presented as a two-sheeted branched cover of $\mathbb{C}$. As
long as the eigenvalues of $T_{j}(\lambda)$ are distinct,
$\Psi(\lambda)=\mu(\lambda)$ is a locally defined analytic function. The proof
of Theorem 4.3 shows that ${\mathcal{C}}$ is connected. The definition of $z$
in (5.10) may be extended as the value of $\mu$ as a function from
${\mathcal{C}}$ to $\mathbb{C}$.

######  Lemma 5.3.

The extended map $z=\mu$ taking ${\mathcal{C}}$ to
$\mathbb{C}\setminus\\{0\\}$ is surjective, with the locally defined
$\mu=\Psi(\lambda)$ satisfying $\Psi^{\prime}(\lambda)\not=0$ unless
$\cos(\omega)\sin(\omega)/\omega=0$.

###### Proof.

From (4.5),

${\rm
tr}T_{j}(\lambda)=\cos^{2}(\omega)(1+\frac{1}{\delta_{B}})(1+\frac{1}{\delta_{R}})-(\frac{1}{\delta_{R}}+\frac{1}{\delta_{B}}).$
(5.12)

One checks easily that the range of ${\rm tr}T_{j}(\lambda)$ is $\mathbb{C}$.

The comments above about the mapping $\phi(z)$ mean that all pairs
$\\{\mu^{-},\mu^{+}=1/(\delta_{R}\delta_{B}\mu^{-})\\}$ with $\mu^{-}\not=0$
occur for some values of $\lambda$. With
$|\mu^{-}|<1/\sqrt{\delta_{R}\delta_{B}}$ and
$|\mu^{+}|>1/\sqrt{\delta_{R}\delta_{B}}$ the individual values of
$\mu^{-}(\lambda)$ and $\mu^{+}(\lambda)$ are well-defined and analytic. The
values of $\mu^{-}(\lambda)$ and $\mu^{+}(\lambda)$ respectively cover the
sets $\\{0<|z|<1/\sqrt{\delta_{R}\delta_{B}}\\}$ and
$\\{|z|>1/\sqrt{\delta_{R}\delta_{B}}\\}$, showing that the range of $\Psi$
includes $\mathbb{C}\setminus\\{0,|z|=1/\sqrt{\delta_{R}\delta_{B}}\\}$.

It remains to consider $|\mu^{\pm}(\lambda)|=1/\sqrt{\delta_{R}\delta_{B}}$,
in which case $\lambda\in[0,\infty)$ by Lemma 4.2. As $\cos^{2}(\omega)$
decreases from $1$ to $0$ in (5.12), ${\rm tr}T_{j}(\lambda)$ decreases from
$1+\frac{1}{\delta_{B}}\frac{1}{\delta_{R}}$ to
$-(\frac{1}{\delta_{R}}+\frac{1}{\delta_{B}})$. From
$(1/\sqrt{\delta_{R}}-1/\sqrt{\delta_{B}})^{2}\geq 0$ follows
$1/\delta_{R}+1/\delta_{B}\geq 2/\sqrt{\delta_{r}\delta_{B}}$ and from
$(1-1/\delta_{R})(1-1/\delta_{B})\geq 0$ follows
$1+\frac{1}{\delta_{B}}\frac{1}{\delta_{R}}\geq(\frac{1}{\delta_{R}}+\frac{1}{\delta_{B}})$.
Thus

$-(\frac{1}{\delta_{R}}+\frac{1}{\delta_{B}})\leq-2/\sqrt{\delta_{R}\delta_{B}}<2/\sqrt{\delta_{R}\delta_{B}}\leq
1+\frac{1}{\delta_{B}}\frac{1}{\delta_{R}}.$

The behavior is similar as $\cos^{2}(\omega)$ increases from $0$ to $1$. From
(4.6) and (4.8) the eigenvalues $\mu^{\pm}(\lambda)$ traverse the upper and
lower semicircles $|\mu^{\pm}(\lambda)|=1/\sqrt{\delta_{R}\delta_{B}}$ once in
each of these segments where $|{\rm tr}T_{j}(\lambda)|\leq
2/\sqrt{\delta_{R}\delta_{B}}$, finishing the surjectivity of $\mu$. By
Theorem 4.3 continuation of $\mu^{\pm}(\lambda)$ across an interval with
$|{\rm tr}T_{j}(\lambda)|<2/\sqrt{\delta_{R}\delta_{B}}$ is analytic as
$\mu^{\pm}(\lambda)$ switches to the $\mu^{\mp}(\lambda)$ sheet.

Computing the derivative of ${\rm tr}T_{j}(\lambda)$ in two ways gives

$\frac{d{\rm
tr}T_{j}(\lambda)}{d\lambda}=-\cos(\omega)\frac{\sin(\omega)}{\omega}(1+\frac{1}{\delta_{R}})(1+\frac{1}{\delta_{B}}),$

and

$\frac{d}{d\lambda}(\mu^{-}+\frac{1}{\delta_{R}\delta_{B}\mu^{-}})=(\mu^{-})^{\prime}(1-\frac{1}{\delta_{R}\delta_{B}(\mu^{-})^{2}})$

so zeros of the derivative of $\mu^{-}(\lambda)$ are constrained by

$\mu^{-}(\lambda)^{\prime}(1-\frac{1}{\delta_{R}\delta_{B}(\mu^{-}(\lambda))^{2}})=-\cos(\omega)\frac{\sin(\omega)}{\omega}(1+\frac{1}{\delta_{R}})(1+\frac{1}{\delta_{B}}).$
(5.13)

From $\mu^{+}(\lambda)\mu^{-}(\lambda)=1/(\delta_{R}\delta_{B})$,

$\mu^{+}(\lambda)^{\prime}=-\mu^{-}(\lambda)^{\prime}\mu^{+}(\lambda)/\mu^{-}(\lambda),$

so the derivatives of $\mu^{+}$ and $\mu^{-}$ vanish together.

∎

As noted, $\Psi(\lambda)=\mu$ is a locally defined analytic function on the
connected set $\\{\mu^{+}(\lambda)\not=\mu^{-}(\lambda)\\}$, so locally (5.8)
extends to

$\frac{P_{{\mathcal{G}}}(\Psi(\lambda))}{P_{CB}(\Psi(\lambda))}=\frac{{\rm
tr}R_{\cal G}(\lambda)}{{\rm tr}R_{CB}(\lambda)}.$ (5.14)

or globally

$\frac{P_{{\mathcal{G}}}(\mu)}{P_{CB}(\mu)}=\frac{{\rm tr}R_{\cal
G}(\lambda)}{{\rm tr}R_{CB}(\lambda)}.$ (5.15)

The left side of (5.14) depends on $\mu=\Psi(\lambda)$, so that is true of the
right side as well, implying that $P_{{\mathcal{G}}}(z)$ is well defined. The
right side of (5.14) depends on $\lambda$, so
$P_{{\mathcal{G}}}(\mu^{+}(\lambda))/P_{CB}(\mu^{+}(\lambda))=P_{{\mathcal{G}}}(\mu^{-}(\lambda))/P_{CB}(\mu^{-}(\lambda))$.

######  Theorem 5.4.

If ${\mathcal{G}}$ is a finite biregular graph then the generating function
$P_{{\mathcal{G}}}(z)$ extends analytically to

$\\{|z|<1/\sqrt{\delta_{R}\delta_{B}}\\}\setminus\\{z\in\mathbb{R}\ |\
1/(\delta_{R}\delta_{B})\leq|z|<1/\sqrt{\delta_{R}\delta_{B}}\\}$ (5.16)

and

$\\{|z|>1/\sqrt{\delta_{R}\delta_{B}}\\}\setminus\\{z\in\mathbb{R}\ |\
1/\sqrt{\delta_{R}\delta_{B}}<|z|\leq 1\\},$

except for poles at $z=\pm i$.

###### Proof.

The resolvent traces in (5.14) are meromorphic in $\mathbb{C}$, with poles in
$[0,\infty)$. As noted in Proposition 2.1, ${\rm tr}R_{CB}(\lambda)=0$ implies
$\lambda\geq 0$. Thus $Q(\lambda)={\rm tr}R_{\cal G}(\lambda)/{\rm
tr}R_{CB}(\lambda)$ is meromorphic in $\mathbb{C}$, with all poles in
$[0,\infty)$. By Theorem 4.3 $\mu^{-}(\lambda)$ and $\mu^{+}(\lambda)$ are
analytic in the complement of $\sigma_{1}\subset[0,\infty)$. Since $P_{CG}$ is
rational, $P_{{\mathcal{G}}}(\mu^{-}(\lambda))$ and
$P_{{\mathcal{G}}}(\mu^{+}(\lambda))$ are meromorphic in
$\mathbb{C}\setminus\sigma_{1}$.

By (5.13), $\mu^{-}(\lambda)^{\prime}$ is not zero unless
$\cos(\omega)\sin(\omega)/\omega=0$; these roots only occur for $\lambda\geq
0$. If $\mu^{-}(\lambda_{0})^{\prime}\not=0$, then
$\mu^{+}(\lambda_{0})^{\prime}\not=0$, in which case both $\mu^{+}(\lambda)$
and $\mu^{-}(\lambda)$ are conformal maps in a neighborhood of $\lambda_{0}$.
If $Q(\lambda)$ is analytic in a neighborhood of $\lambda_{0}$ and if
$P_{CB}(\Psi(\lambda))$ is also analytic in a neighborhood of
$\mu^{\pm}(\lambda_{0})$, then (5.14) provides a definition of
$P_{{\mathcal{G}}}(z)=P_{{\mathcal{G}}}(\Psi(\lambda))$ as an analytic
function in some neighborhood of $z_{0}=\mu^{\pm}(\lambda_{0})$.

$Q(\lambda)$ is analytic in $\mathbb{C}\setminus[0,\infty)$. As noted for
(4.8), ${\rm tr}(T_{j})(\lambda)$ is real when $\lambda$ is real. If
$\lambda\in\mathbb{R}$ and ${\rm tr}(T_{j})^{2}/4-\det(T_{j})\leq 0$ then
$|\mu^{\pm}(\lambda)|=1/\sqrt{\delta_{B}\delta_{R}}$. If $\lambda\geq 0$ and
${\rm tr}(T_{j})^{2}/4-\det(T_{j})\geq 0$ then
$\mu^{\pm}(\lambda)\in\mathbb{R}$ and $|{\rm tr}(T_{j})(\lambda)|\leq
1+\frac{1}{\delta_{R}}\frac{1}{\delta_{B}}$ by (5.12). By (4.6)

$\mu^{+}\leq\frac{1}{2}(1+\frac{1}{\delta_{R}}\frac{1}{\delta_{B}})+\sqrt{(1-\frac{1}{\delta_{R}}\frac{1}{\delta_{B}})^{2}/4}=1,$

so $\mu^{-}(\lambda)\geq 1/(\delta_{R}\delta_{B})$ for $\lambda\geq 0$.
Finally, the rational function $P_{CB}(z)$ has poles at $z=\pm i,\pm
1/(\delta_{R}\delta_{B})$. Thus $P_{{\mathcal{G}}}(z)$ is analytic in the sets
in (5.16). ∎

By (5.12) the functions ${\rm tr}T_{j}(\lambda)$, and so the (unordered pair
of) eigenvalues $\mu^{\pm}(\lambda)$, are periodic in $\omega$ with period
$\pi$. Thus any singularities in $P_{{\mathcal{G}}}(\mu)$ must already appear
in the strip $0\leq\Re(\omega)\leq\pi$. The function $Q(\lambda)={\rm
tr}R_{\cal G}(\lambda)/{\rm tr}R_{CB}(\lambda)$ only has singularities in
$[0,\infty)$, meaning that singular points for $P_{{\mathcal{G}}}(z)$ coming
from $Q(\lambda)$ will appear for $0\leq\lambda\leq\pi^{2}$, where
$Q(\lambda)$ has a finite set of poles.

By (2.5) the pole locations for ${\rm tr}R_{\cal G}(\lambda)$ with
$0\leq\lambda\leq\pi^{2}$ are $0$, $\pi^{2}$ and the points with
$\cos(\sqrt{\lambda})=1-\nu_{k}$ for $k=1,\dots,N_{\mathcal{V}}-2$. For the
complete bipartite graph ${\mathcal{L}}$ has eigenvalues at
$0,(\pi/2)^{2},\pi^{2}$ in the interval $[0,\pi^{2}]$. By Proposition 2.1 the
function ${\rm tr}R_{CG}(\lambda)$ has two roots $\xi_{i}$ lying between the
consecutive eigenvalue pairs. Thus in the strip $0\leq\Re(\lambda)\leq\pi^{2}$
the function $Q(\lambda)$ has at most $N_{\mathcal{V}}+2$ poles, all lying in
$[0,\pi^{2}]$.

######  Theorem 5.5.

If ${\mathcal{G}}$ is a finite biregular graph then the generating function
$P_{{\mathcal{G}}}(z)$ extends to a rational function. The poles are all
located in the set

$\\{z=\pm
i\\}\cup\\{|z|=1/\sqrt{\delta_{R}\delta_{B}}\\}\cup\\{z\in\mathbb{R}\ |\
1/(\delta_{R}\delta_{B})\leq|z|<1\\}.$

###### Proof.

The function $P_{{\mathcal{G}}}(z)$ is analytic except possibly at a finite
collection of points for which:

(i) $\lambda$ is a pole of $Q(\lambda)$,

(ii) $\mu^{\pm}(\lambda)^{\prime}=0$,

(iii) $\mu^{-}(\lambda)=\mu^{+}(\lambda)$,

(iv) $z$ is a pole of $P_{CG}(z)$.

By (5.14) the isolated singular points for $z\in\mathbb{C}$ are not essential
singularities, so [11, p. 105-109] $P_{{\mathcal{G}}}(z)$ is meromorphic in
$\mathbb{C}$ with a finite set of poles, which are limited to the sets (i) and
(iv). In the strip $0\leq\Re(\omega)\leq\pi$, note that $|{\rm
tr}T_{j}(\lambda)|\to\infty$, and so $|\mu^{+}(\lambda)|\to\infty$ as
$|\Im(\omega)|\to\infty$. From (2.5) the resolvent traces have limit zero as
$|\Im(\lambda)|\to\infty$ in this strip. Moreover $P_{CB}(z)$ has a pole at
$\infty$. Thus $P_{{\mathcal{G}}}(z)$ is a meromorphic function with finitely
many poles in $\mathbb{C}\cup\infty$, so is rational [11, p. 141].

∎

## References

  * [1] G. Brito, I. Dumitiu, and K. Harris.  Spectral gap in random bipartite biregular graphs and its applications,  Combinatorics Probability and Computing, 31(2) 2018.
  * [2] J. von Below.  A characteristic equation associated to an eigenvalue problem on $c^{2}$ \- networks,  Linear Algebra and Its Applications, 71(23): 309–3325, 1985.
  * [3] G. Berkolaiko and P Kuchment.  Introduction to Quantum Graphs.  American Mathematical Society, Providence, 2013.
  * [4] G. Birkhoff and G Rota.  Ordinary Differential Equations.  Blaisdell, Waltham, 1969.
  * [5] B. Bollobas. Modern Graph Theory. Springer, 1998.
  * [6] R. Brooks.  The spectral geometry of k-regular graphs.  J. d’Analyse Mathematique, 57:120–151, 1991.
  * [7] R. Carlson.  Hill’s equation for a homogeneous tree.  Electronic Journal of Differential Equations, 1997(23):1–30, 1997.
  * [8] R. Carlson  Harmonic Analysis for Graph Refinements and the Continuous Graph FFT  Linear Algebra Appl. 430 no. 11-12: 2859–2876, 2009.
  * [9] C. Cattaneo.  The spectrum of the continuous Laplacian on a graph,  Monatsh. Math., 124(3): 215–235, 1997.
  * [10] F. Chung.  Spectral Graph Theory.  American Mathematical Society, Providence, 1997.
  * [11] R. Greene and S. Krantz.  Function Theory of One Complex Variable.  American Mathematical Society, 2006.
  * [12] A. Hatcher.  Algebraic Topology.  Cambridge University Press, 2001.  Online edition
  * [13] T. Kato.  Perturbation Theory for Linear Operators.  Springer-Verlag, New York, 1995.
  * [14] D. Marshall.  Complex Analysis.  Cambridge, 2019.
  * [15] W. Massey.  Algebraic Topology: An Introduction.  Harcourt, Brace and World, New York, 1967.
  * [16] M. Reed and B. Simon  Methods of Modern Mathematical Physics, 1.  Academic Press, New York, 1972.
  * [17] M. Reed and B. Simon  Methods of Modern Mathematical Physics, 2.  Academic Press, New York, 1975.
  * [18] A. Terras.  Zeta Functions of Graphs.  Cambridge University Press, Cambridge, 2011.


* Verma & Donzis (2007) Verma, M. K. & Donzis, D. A. 2007 Energy transfer and bottleneck effect in turbulence. J. Phys. A: Math. Theor. 40 (16), 4401–4412.
  * Verma et al. (2020) Verma, M. K., Kumar, A. & Gupta, A. 2020 Hydrodynamic Turbulence: Sweeping Effect and Taylor’s Hypothesis via Correlation Function. Trans Indian Natl. Acad. Eng. 5, 649.
  * Waleffe (1992) Waleffe, F. 1992 The nature of triad interactions in homogeneous turbulence. Phys. Fluids A 4 (2), 350–363.
  * Wilson & Kogut (1974) Wilson, K. G. & Kogut, J. 1974 The renormalization group and the $\varepsilon$ expansion. Phys. Rep. 12 (2), 75–199.
  * Wyld (1961) Wyld, H. W. J. 1961 Formulation of the theory of turbulence in an incompressible fluid. Ann. Phys. 14, 143–165.
  * Yakhot & Orszag (1986) Yakhot, V. & Orszag, S. A. 1986 Renormalization group analysis of turbulence. I. Basic theory. J. Sci. Comput. 1 (1), 3–51.
  * Zhou (1993) Zhou, Y. 1993 Degrees of locality of energy transfer in the inertial range. Phys. Fluids 5, 1092–1094.
  * Zhou (2010) Zhou, Y. 2010 Renormalization group theory for fluid and plasma turbulence. Phys. Rep. 488 (1), 1–49.
  * Zhou (2021) Zhou, Y. 2021 Turbulence theories and statistical closure approaches. Phys. Rep. 935, 1–117.
  * Zhou et al. (1988) Zhou, Y., Vahala, G. & Hossain, M. 1988 Renormalization-group theory for the eddy viscosity in subgrid modeling. Phys. Rev. A 37 (7), 2590–2598.
  * Zhou et al. (1989) Zhou, Y., Vahala, G. & Hossain, M. 1989 Renormalized eddy viscosity and Kolmogorov’s constant in forced Navier-Stokes turbulence. Phys. Rev. A 40 (10), 5865–5874.
  * Zhou et al. (1997) Zhou, Y., Vahala, G. & McComb, W. D. 1997 Renormalization Group (RG) in Turbulence: Historical and Comparative Perspective. Tech. Rep. ICAS-97-36.