Content-Type: multipart/mixed; boundary="-------------0701041319454"

This is a multi-part message in MIME format.

---------------0701041319454
Content-Type: text/plain; name="07-3.comments"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="07-3.comments"

AMS-Code: 34B45; 81U40; 47D06
---------------0701041319454
Content-Type: text/plain; name="07-3.keywords"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="07-3.keywords"

Metric graphs, heat semigroups, trace formulas, inverse problems
---------------0701041319454
Content-Type: application/x-tex; name="heatkernel-preprint.tex"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline; filename="heatkernel-preprint.tex"

\documentclass[final]{amsart}
\usepackage{times}
\usepackage{amsfonts,amscd,amsmath,amssymb,amsthm}


%\usepackage[notref,notcite]{showkeys}

\def\volinfo{Volume \textbf{000}, 0000}

\numberwithin{equation}{section}
\renewcommand{\figurename}{Fig.}

\renewcommand{\Im}{{\ensuremath{\mathrm{Im\,}}}}
\renewcommand{\Re}{{\ensuremath{\mathrm{Re\,}}}}

\DeclareSymbolFont{SY}{U}{psy}{m}{n}
\DeclareMathSymbol{\emptyset}{\mathord}{SY}{'306}
\DeclareMathSymbol{\newtimes}{\mathbin}{SY}{'264}
\DeclareMathOperator*{\Bigtimes}{\newtimes}

\newcommand{\erfc}{\mathrm{erfc}}
\newcommand{\erf}{\mathrm{erf}}

\renewcommand{\kappa}{\varkappa}

\numberwithin{equation}{section}


\DeclareMathOperator*{\slim}{s-lim} \DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\End}{End} \DeclareMathOperator{\Ret}{Re}
\DeclareMathOperator{\Imt}{Im} \DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\Ran}{Ran} \DeclareMathOperator{\Ker}{Ker}
\DeclareMathOperator{\Rank}{Rank} \DeclareMathOperator{\spec}{spec}
\DeclareMathOperator{\Dom}{Dom} \DeclareMathOperator{\sign}{sign}
\DeclareMathOperator{\dist}{dist}

\newcommand{\E}{\mathbb{E}}
\newcommand{\HH}{\mathbb{H}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\T}{\mathbb{T}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\bP}{\mathbb{P}}
\newcommand{\1}{\mathbb{I}}
\newcommand{\CC}{{\delta S}}

\newcommand{\bS}{\mathbb{S}}

\newcommand{\fH}{\mathfrak{H}}
\newcommand{\fR}{\mathfrak{R}}
\newcommand{\fF}{\mathfrak{F}}
\newcommand{\fB}{\mathfrak{B}}
\newcommand{\fS}{\mathfrak{S}}
\newcommand{\fD}{\mathfrak{D}}
\newcommand{\fE}{\mathfrak{E}}
\newcommand{\fP}{\mathfrak{P}}
\newcommand{\fT}{\mathfrak{T}}
\newcommand{\fC}{\mathfrak{C}}
\newcommand{\fM}{\mathfrak{M}}
\newcommand{\fI}{\mathfrak{I}}
\newcommand{\fL}{\mathfrak{L}}
\newcommand{\fW}{\mathfrak{W}}
\newcommand{\fK}{\mathfrak{K}}
\newcommand{\fA}{\mathfrak{A}}
\newcommand{\fV}{\mathfrak{V}}

\newcommand{\fc}{\mathfrak{c}}
\newcommand{\fs}{\mathfrak{s}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Kaliegraphie
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\cA}{{\mathcal A}}
\newcommand{\cB}{{\mathcal B}}
\newcommand{\cC}{{\mathcal C}}
\newcommand{\cD}{{\mathcal D}}
\newcommand{\cE}{{\mathcal E}}
\newcommand{\cF}{{\mathcal F}}
\newcommand{\cG}{{\mathcal G}}
\newcommand{\cH}{{\mathcal H}}
\newcommand{\cI}{{\mathcal I}}
\newcommand{\cJ}{{\mathcal J}}
\newcommand{\cK}{{\mathcal K}}
\newcommand{\cL}{{\mathcal L}}
\newcommand{\cM}{{\mathcal M}}
\newcommand{\cN}{{\mathcal N}}
\newcommand{\cO}{{\mathcal O}}
\newcommand{\cP}{{\mathcal P}}
\newcommand{\cQ}{{\mathcal Q}}
\newcommand{\cR}{{\mathcal R}}
\newcommand{\cS}{{\mathcal S}}
\newcommand{\cT}{{\mathcal T}}
\newcommand{\cU}{{\mathcal U}}
\newcommand{\cV}{{\mathcal V}}
\newcommand{\cX}{{\mathcal X}}
\newcommand{\cW}{{\mathcal W}}
\newcommand{\cZ}{{\mathcal Z}}

\newcommand{\D}{\mathsf{D}}
\newcommand{\K}{\mathsf{K}}
\newcommand{\sfL}{\mathsf{L}}
\newcommand{\U}{\mathsf{U}}
\newcommand{\SL}{\mathsf{SL}}

\newcommand{\diag}{\mathrm{diag}}

\newcommand{\sk}{\mathsf{k}}
\newcommand{\ii}{\mathrm{i}}
\newcommand{\e}{\mathrm{e}}
\newcommand{\Res}{\mathrm{Res}}
\newcommand{\sm}{\mathsf{m}}
\newcommand{\bw}{\mathbf{w}}

\renewcommand{\epsilon}{\varepsilon}

\renewcommand{\det}{\mathrm{det}}


\newtheorem{introtheorem}{Theorem}{\bf}{\it}
\newtheorem{introproposition}{Proposition}{\bf}{\it}
\newtheorem{introdefinition}{Definition}{\bf}{\it}
\newtheorem{introassumption}{Assumption}{\bf}{\it}

\newtheorem{theorem}{Theorem}[section]{\bf}{\it}
\newtheorem{proposition}[theorem]{Proposition}{\bf}{\it}
\newtheorem{corollary}[theorem]{Corollary}{\bf}{\it}
\newtheorem{example}[theorem]{Example}{\it}{\rm}
\newtheorem{lemma}[theorem]{Lemma}{\bf}{\it}
\newtheorem{remark}[theorem]{Remark}{\it}{\rm}
\newtheorem{definition}[theorem]{Definition}{\bf}{\it}


\title[Heat Kernels on Metric Graphs]{Heat Kernels on Metric Graphs and a Trace Formula}

\author[V. Kostrykin]{Vadim Kostrykin}
\address{Vadim Kostrykin\\ Institut f\"{u}r Mathematik, Technische Universit\"{a}t Clausthal,
Erz\-stra{\ss}e 1, D-38678 Clausthal-Zellerfeld, Germany}
\email{kostrykin@math.tu-clausthal.de, kostrykin@t-online.de}

\author[J. Potthoff]{J\"{u}rgen Potthoff}
\address{J\"{u}rgen Potthoff\\ Institut f\"{u}r Mathematik, Universit\"{a}t Mannheim, D-68131 Mannheim, Germany}
\email{potthoff@math.uni-mannheim.de}

\author[R. Schrader]{Robert Schrader}
\address{Robert Schrader\\ Institut f\"{u}r Theoretische Physik\\
Freie Universit\"{a}t Berlin, Arnim\-allee 14\\ D-14195 Berlin, Germany}
\email{schrader@physik.fu-berlin.de}

\dedicatory{Dedicated to Jean-Michel Combes on the occasion of his 65-th
birthday}

\copyrightinfo{2007}{V.~Kostrykin, J.~Potthoff, R.~Schrader}

\keywords{Metric graphs, heat semigroups, trace formulas, inverse problems}

\subjclass[2000]{Primary 34B45, 81U40; Secondary 47D06}

\begin{document}


\begin{abstract}
We study heat semigroups generated by self-adjoint Laplace operators on
metric graphs characterized by the property that the local scattering
matrices associated with each vertex of the graph are independent from the
spectral parameter. For such operators we prove a representation for the
heat kernel as a sum over all walks with given initial and terminal edges.
Using this representation a trace formula for heat semigroups is proven.
Applications of the trace formula to inverse spectral and scattering
problems are also discussed.
\end{abstract}

\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}\label{sec:intro}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Metric graphs or networks are one-dimensional piecewise linear spaces with
singularities at the vertices. Alternatively, a metric graph is a metric
space which can be written as a union of finitely many intervals, which are
either compact or $[0,\infty)$; any two of these intervals are either
disjoint or intersect only in one or both of their endpoints. It is natural
to call the metric graph compact if all its edges have finite length.

The increasing interest in the theory of differential operators on metric
graphs is motivated mainly by two reasons. The first reason is that such
operators arise in a variety of applications. We refer the reader to the
review \cite{Kuchment:0}, where a number of models arising in physics,
chemistry, and engineering is discussed. The second reason is purely
mathematical: It is intriguing to study the interrelation between the
spectra of these operators and topological or combinatorial properties of
the underlying graph. Similar interrelations are studied in spectral
geometry for differential operators on Riemannian manifolds (see,
e.g.~\cite{Chavel}, \cite{Gilkey}) and in spectral graph theory for
difference operators on combinatorial graphs (see, e.g.~\cite{Verdiere}).
Metric graphs take an intermediate position between manifolds and
combinatorial graphs.

In the present work we continue the study of heat semigroups on metric
graphs initiated in \cite{KS3}. There we provided sufficient conditions for
a self-adjoint Laplace operator to generate a contractive semigroup.
Moreover, we proved a criterion guaranteeing that this semigroup is
positivity preserving. For earlier work on heat semigroups generated by
Laplace operators on metric graphs and their application to spectral
analysis we refer to \cite{Angad-Guar}, \cite{Gaveau:1}, \cite{Gaveau:2},
\cite{Nicaise}, \cite{Nicaise:2}, \cite{Roth:1}, \cite{Roth:2}.

In this article we study heat semigroups generated by self-adjoint Laplace
operators which are characterized by the property that the local scattering
matrices associated with each vertex of the graph are independent of the
spectral parameter. All boundary conditions leading to such operators are
described in Proposition \ref{k-independent} below. In particular, Neumann,
Dirichlet, and the so called standard boundary conditions are in this class.

Our main technical tool to study heat semigroups on metric graphs are
\emph{walks} on edges of the graph, a concept developed in \cite{KS3},
\cite{KS4}. We will revisit this concept in Section \ref{sec:walks} below.
Furthermore, we will provide a representation for the heat kernel as a sum
over all walks with given initial and terminal edges. This representation
relates the topology of the graph to analytic properties of the heat
semigroup.

In Section \ref{sec:trac:form} we prove a trace formula for heat semigroups
on arbitrary (compact as well as noncompact) metric graphs, an analog of the
celebrated Selberg formula for differential operators on Riemannian
manifolds (see \cite{McKean}, \cite{Selberg} for the case of compact
manifolds and \cite{Hejhal}, \cite{Levay} for the noncompact case). A
discrete analog of the Selberg trace formula on $k$-regular trees is
discussed in \cite{Terras}.

The trace formula expresses the trace of the semigroup difference as the
sum over all \emph{cycles} on the graph, that is, equivalence classes of
closed walks. In the particular case of compact graphs and standard boundary
conditions our result recovers the well-known trace formula obtained by Roth
\cite{Roth:1}, \cite{Roth:2}. Related results can be found in \cite{KuNo},
\cite{Nicaise}, \cite{Nicaise:2}, \cite{Winn}. In the physical literature
trace formulas for Laplace operators on metric graphs have been discussed
in \cite{ACDMT}, \cite{Kottos}, \cite{Kottos:2}, \cite{Kottos:3}. Their
applications to quantum chaos and spectral statistics are reviewed in the
recent article \cite{GnuS}.


As an application of the trace formula, in Section \ref{sec:inv:probl} we
discuss inverse spectral and scattering problems. The inverse problems
considered here consist of determining the graph and its metric structure
(i.e.\ the lengths of its edges) from the spectrum of the Laplace operator
and the scattering phase (that is, half the phase of the determinant of the
scattering matrix), under the condition that the boundary conditions at all
vertices of the graph are supposed to be known. Another kind of the inverse
scattering problem, the reconstruction of the graph and the boundary
conditions from the scattering matrix, has been solved recently in
\cite{KS4}.

The results of Section \ref{sec:inv:probl} provide a mathematically
rigorous solution of the inverse scattering problem as proposed by Gutkin
and Smilansky in \cite{GS}. Also these result extend
the solution of the inverse spectral problem on compact graphs given by
Kurasov and Nowaszyk in \cite{KuNo} to more general boundary conditions.


\subsection*{Acknowledgments} It is a pleasure to thank the organizers of the conference
``Transport and Spectral Problems in Quantum Mechanics'' held at the
University of Cergy-Pontoise in September 2006 for a very interesting and
enjoyable meeting, both scientifically and socially. The authors would like
to thank M.~Karowski for helpful discussions.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Background}\label{sec:back}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

A finite graph is a 4-tuple $\cG=(V,\cI,\cE,\partial)$, where $V$ is a
finite set of \emph{vertices}, $\cI$ is a finite set of \emph{internal
edges}, $\cE$ is a finite set of \emph{external edges}. Elements in
$\cI\cup\cE$ are called \emph{edges}. The map $\partial$ assigns to each
internal edge $i\in\cI$ an ordered pair of (possibly equal) vertices
$\partial(i):=\{v_1,v_2\}$ and to each external edge $e\in\cE$ a single
vertex $v$. The vertices $v_1=:\partial^-(i)$ and $v_2=:\partial^+(i)$ are
called the \emph{initial} and \emph{terminal} vertex of the internal edge
$i$, respectively. The vertex $v=\partial(e)$ is the initial vertex of the
external edge $e$. If $\partial(i)=\{v,v\}$, that is,
$\partial^-(i)=\partial^+(i)$ then $i$ is called a \emph{tadpole}. A graph
is called \emph{compact} if $\cE=\emptyset$, otherwise it is
\emph{noncompact}.

Two vertices $v$ and $v^\prime$ are called \emph{adjacent} if there is an
internal edge $i\in\cI$ such that $v\in\partial(i)$ and
$v^\prime\in\partial(i)$. A vertex $v$ and the (internal or external) edge
$j\in\cI\cup\cE$ are \emph{incident} if $v\in\partial(j)$.

We do not require the map $\partial$ to be injective. In particular, any two
vertices are allowed to be adjacent to more than one internal edge and two
different external edges may be incident with the same vertex. If
$\partial$ is injective and $\partial^-(i)\neq\partial^+(i)$ for all
$i\in\cI$, the graph $\cG$ is called \emph{simple}.

The \emph{degree} $\deg(v)$ of the vertex $v$ is defined as
\begin{equation*}
\deg(v)=|\{e\in\cE\mid\partial(e)=v\}|+|\{i\in\cI\mid\partial^-(i)=v\}|+|\{i\in\cI\mid\partial^+(i)=v\}|,
\end{equation*}
that is, it is the number of (internal or external) edges incident with the
given vertex $v$ by which every tadpole is counted twice.

It is easy to extend the First Theorem of Graph Theory (see, e.g.\,
\cite{Diestel}) to the case of noncompact graphs:
\begin{equation}\label{1:thm:gt}
\sum_{v\in V} \deg(v) = |\cE| + 2 |\cI|.
\end{equation}

A vertex is called a \emph{boundary vertex} if it is incident with some
external edge. The set of all boundary vertices will be denoted by $\partial
V$. The vertices not in $\partial V$, that is in $V\setminus\partial V$ are
called \emph{internal vertices}.

The compact graph $\cG_{\mathrm{int}}=(V,\cI,\emptyset,\partial|_{\cI})$
will be called the \emph{interior} of the graph $\cG=(V,\cI,$ $
\cE,\partial)$. It is obtained from $\cG$ by eliminating the external
edges.

The \emph{star} $\cS(v)\subseteq \cE\cup\cI$ of the vertex $v\in V$ is the
set of the edges adjacent to $v$.

Throughout the whole work we will assume that the graph $\cG$ is connected,
that is, for any $v,v^\prime\in V$ there is an ordered sequence of vertices
$\{v_1=v, v_2,\ldots, v_{n-1}, v_n=v^\prime\}$ such that any two successive
vertices in this sequence are adjacent. In particular, this assumption
implies that any vertex of the graph $\cG$ has nonzero degree, i.e., for
any vertex there is at least one edge with which it is incident.

We will endow the graph with the following metric structure. Any internal
edge $i\in\cI$ will be associated with an interval $[0,a_i]$ with $a_i>0$
such that the initial vertex of $i$ corresponds to $x=0$ and the terminal
one to $x=a_i$. Any external edge $e\in\cE$ will be associated with a
semiline $[0,+\infty)$. We call the number $a_i$ the length of the internal
edge $i$. The set of lengths $\{a_i\}_{i\in\cI}$, which will also be treated
as an element of $\R^{|\cI|}$, will be denoted by $\underline{a}$. A
compact or noncompact graph $\cG$ endowed with a metric structure is called
a \emph{metric graph} and is written as $(\cG,\underline{a})$.

Given a finite graph $\cG=(V,\cI,\cE,\partial)$ with a metric structure
$\underline{a}=\{a_i\}_{i\in\cI}$ consider the Hilbert space
\begin{equation}\label{hilbert}
\cH\equiv\cH(\cE,\cI,\underline{a})=\cH_{\cE}\oplus\cH_{\cI},\qquad
\cH_{\cE}=\bigoplus_{e\in\cE}\cH_{e},\qquad
\cH_{\cI}=\bigoplus_{i\in\cI}\cH_{i},
\end{equation}
where $\cH_j=L^2(I_j)$ with
\begin{equation*}
I_j=\begin{cases} [0,a_j] & \text{if}\quad j\in\cI,\\  [0,\infty) &
\text{if}\quad j\in\cE.\end{cases}
\end{equation*}
Let $\overset{o}{I_j}$ be the interior of $I_j$, that is,
$\overset{o}{I_j}=(0,a_j)$ if $j\in\cI$ and $\overset{o}{I_j}=(0,\infty)$
if $j\in\cE$.

In the sequel the letters $x$ and $y$ will denote arbitrary elements of the
product set $\displaystyle\Bigtimes_{j\in\cE\cup\cI} I_j$.

By $\cD_j$ with $j\in\cE\cup\cI$ denote the set of all $\psi_j\in\cH_j$
such that $\psi_j(x)$ and its derivative $\psi^\prime_j(x)$ are absolutely
continuous and $\psi^{\prime\prime}_j(x)$ is square integrable. Let
$\cD_j^0$ denote the set of those elements $\psi_j\in\cD_j$ which satisfy
\begin{equation*}
\begin{matrix}
\psi_j(0)=0\\ \psi^\prime_j(0)=0
\end{matrix} \quad \text{for}\quad j\in\cE\qquad\text{and}\qquad
\begin{matrix}
\psi_j(0)=\psi_j(a_j)=0\\
\psi^\prime_j(0)=\psi^\prime_j(a_j)=0
\end{matrix}
\quad\text{for}\quad j\in\cI.
\end{equation*}
Let $\Delta^0$ be the differential operator
\begin{equation}\label{Delta:0}
\left(\Delta^0\psi\right)_j (x) = \frac{d^2}{dx^2} \psi_j(x),\qquad
j\in\cI\cup\cE
\end{equation}
with domain
\begin{equation*}
\cD^0=\bigoplus_{j\in\cE\cup\cI} \cD_j^0 \subset\cH.
\end{equation*}
It is straightforward to verify that $\Delta^0$ is a closed symmetric
operator with deficiency indices equal to $|\cE|+2|\cI|$.

We introduce an auxiliary finite-dimensional Hilbert space
\begin{equation}\label{K:def}
\cK\equiv\cK(\cE,\cI)=\cK_{\cE}\oplus\cK_{\cI}^{(-)}\oplus\cK_{\cI}^{(+)}
\end{equation}
with $\cK_{\cE}\cong\C^{|\cE|}$ and $\cK_{\cI}^{(\pm)}\cong\C^{|\cI|}$. Let
${}^d\cK$ denote the ``double'' of $\cK$, that is, ${}^d\cK=\cK\oplus\cK$.

For any $\displaystyle\psi\in\cD:=\bigoplus_{j\in\cE\cup\cI} \cD_j$ we set
\begin{equation}\label{lin1}
[\psi]:=\underline{\psi}\oplus \underline{\psi}^\prime\in{}^d\cK,
\end{equation}
with $\underline{\psi}$ and $\underline{\psi}^\prime$ defined by
\begin{equation}\label{lin1:add}
\underline{\psi} = \begin{pmatrix} \{\psi_e(0)\}_{e\in\cE} \\
                                   \{\psi_i(0)\}_{i\in\cI} \\
                                   \{\psi_i(a_i)\}_{i\in\cI} \\
                                     \end{pmatrix},\qquad
\underline{\psi}' = \begin{pmatrix} \{\psi_e'(0)\}_{e\in\cE} \\
                                   \{\psi_i'(0)\}_{i\in\cI} \\
                                   \{-\psi_i'(a_i)\}_{i\in\cI} \\
                                     \end{pmatrix}.
\end{equation}


Let $J$ be the canonical symplectic matrix on ${}^d\cK$,
\begin{equation}\label{J:canon}
J=\begin{pmatrix} 0& \1 \\ -\1 & 0
\end{pmatrix}
\end{equation}
with $\1$ being the identity operator on $\cK$. Consider the non-degenerate
Hermitian symplectic form
\begin{equation}\label{omega:canon}
\omega([\phi],[\psi]) := \langle[\phi], J[\psi]\rangle,
\end{equation}
where $\langle\cdot,\cdot\rangle$ denotes the scalar product in ${}^d
\cK\cong\C^{2(|\cE|+2|\cI|)}$.

A linear subspace $\cM$ of ${}^d\cK$ is called \emph{isotropic} if the form
$\omega$ vanishes identically on $\cM$. An isotropic subspace is called
\emph{maximal} if it is not a proper subspace of a larger isotropic
subspace. Every maximal isotropic subspace has complex dimension equal to
$|\cE|+2|\cI|$.

Let $A$ and $B$ be linear maps of $\cK$ onto itself. By $(A,B)$ we denote
the linear map from ${}^d\cK=\cK\oplus\cK$ to $\cK$ defined by the relation
\begin{equation*}
(A,B)\; (\chi_1\oplus \chi_2) := A\, \chi_1 + B\, \chi_2,
\end{equation*}
where $\chi_1,\chi_2\in\cK$. Set
\begin{equation}\label{M:def}
\cM(A,B) := \Ker\, (A,B).
\end{equation}


\begin{theorem}[\cite{KS1}]\label{thm:3.1}
A subspace $\cM\subset{}^d\cK$ is maximal isotropic if and only if there
exist linear maps $A,\,B:\; \cK\rightarrow\cK$ such that $\cM=\cM(A,B)$ and
\begin{equation}\label{abcond}
\begin{split}
\mathrm{(i)}\; & \;\text{the map $(A,B):\;{}^d\cK\rightarrow\cK$ has maximal
rank equal to
$|\cE|+2|\cI|$,}\qquad\\
\mathrm{(ii)}\; &\;\text{$AB^{\dagger}$ is self-adjoint,
    $AB^{\dagger}=BA^{\dagger}$.}
\end{split}
\end{equation}
\end{theorem}

Under the conditions \eqref{abcond} both $A\pm \ii\sk B$ are invertible for
all $\sk>0$.


\begin{definition}\label{def:equiv}
Two boundary conditions $(A,B)$ and $(A',B')$ satisfying \eqref{abcond} are
equivalent if the corresponding maximal isotropic subspaces coincide, that
is, $\cM(A,B)=\cM(A',B')$.
\end{definition}

The boundary conditions $(A,B)$ and $(A',B')$ satisfying \eqref{abcond} are
equivalent if and only if there is an invertible map $C:\,
\cK\rightarrow\cK$ such that $A'= CA$ and $B'=CB$ (see Proposition 3.6 in
\cite{KS4}).

By Lemma 3.3 in \cite{KS4}, a subspace $\cM(A,B)\subset{}^d\cK$ is maximal
isotropic if and only if
\begin{equation}\label{perp}
\cM(A,B)^{\perp} = \cM(B,-A).
\end{equation}
We mention also the equalities
\begin{equation*}
\begin{split}
\cM(A,B)^\perp & = \bigl[\Ker\,(A,B)\bigr]^\perp  = \Ran\, (A,B)^\dagger,\\
\cM(A,B) & = \Ran(-B,A)^\dagger.
\end{split}
\end{equation*}


There is an alternative parametrization of maximal isotropic subspaces of
${}^d\cK$ by unitary transformations in $\cK$ (see \cite{KS3} and
Proposition 3.6 in \cite{KS4}). A subspace $\cM(A,B)\subset {}^d\cK$ is
maximal isotropic if and only if for an arbitrary $\sk\in\R\setminus\{0\}$
the operator $A+\ii\sk B$ is invertible and
\begin{equation}\label{uuu:def}
\fS(\sk;A,B):=-(A+\ii\sk B)^{-1} (A-\ii\sk B)
\end{equation}
is unitary. Moreover, given any $\sk\in\R\setminus\{0\}$ the correspondence
between maximal isotropic subspaces $\cM\subset {}^d\cK$ and unitary
operators $\fS(\sk;A,B)\in\mathsf{U}(|\cE|+2|\cI|)$ on $\cK$ is one-to-one,
a result dating back to Bott \cite{Bott} and rediscovered in \cite{Arnold},
\cite{H}, and \cite{KS2}. Therefore, we will use the notation
$\mathfrak{S}(\sk;\cM)$ for $\fS(\sk;A,B)$ with $\cM(A,B)=\cM$.

Under the duality transformation $\cM\mapsto\cM^\perp$, as a direct
consequence of \eqref{perp} and \eqref{uuu:def}, the operators
\eqref{uuu:def} transform as follows (see Corollary 2.2 in \cite{KS1}):
\begin{equation}\label{sigma:perp}
\fS(\sk;\cM^\perp) = - \fS(\sk^{-1};\cM).
\end{equation}


There is a one-to-one correspondence between all self-adjoint extensions of
$\Delta^0$ and maximal isotropic subspaces of ${}^d\cK$ (see \cite{KS1},
\cite{KS4}). In explicit terms, any self-adjoint extension of $\Delta^0$ is
the differential operator defined by \eqref{Delta:0} with domain
\begin{equation}\label{thru}
\Dom(\Delta)=\{\psi\in\cD|\; [\psi]\in\cM\},
\end{equation}
where $\cM$ is a maximal isotropic subspace of ${}^d\cK$. Conversely, any
maximal isotropic subspace $\cM$ of ${}^d\cK$ defines through \eqref{thru}
a self-adjoint operator $\Delta(\cM, \underline{a})$. If $\cI=\emptyset$,
we will simply write $\Delta(\cM)$. In the sequel we will call the operator
$\Delta(\cM, \underline{a})$ a Laplace operator on the metric graph $(\cG,
\underline{a})$. {}From the discussion above it follows immediately that
any self-adjoint Laplace operator on $\cH$ equals
$\Delta(\cM,\underline{a})$ for some maximal isotropic subspace $\cM$.
Moreover, $\Delta(\cM,\underline{a})=\Delta(\cM^\prime,\underline{a})$ if
and only if $\cM=\cM^\prime$.

{}From Theorem \ref{thm:3.1} it follows that the domain of the Laplace
operator $\Delta(\cM,\underline{a})$ consists of functions $\psi\in\cD$
satisfying the boundary conditions
\begin{equation}\label{lin2}
 A\underline{\psi}+B\underline{\psi}^{\prime}=0,
\end{equation}
with $(A,B)$ subject to \eqref{M:def} and \eqref{abcond}. Here
$\underline{\psi}$ and $\underline{\psi}^{\prime}$ are defined by
\eqref{lin1:add}.

With respect to the orthogonal decomposition $\cK = \cK_{\cE}\oplus\cK_{\cI}^{(-)}\oplus\cK_{\cI}^{(+)}$
any element $\chi$ of
$\cK$ can be represented as a vector
\begin{equation}\label{elements}
\chi=\begin{pmatrix}\{\chi_e\}_{e\in\cE}\\ \{\chi^{(-)}_i\}_{i\in\cI}\\
\{\chi^{(+)}_i\}_{i\in\cI}\end{pmatrix}.
\end{equation}
Consider the orthogonal decomposition
\begin{equation}\label{K:ortho}
\cK = \bigoplus_{v\in V} \cL_{v}
\end{equation}
with $\cL_{v}$ the linear subspace of dimension $\deg(v)$ spanned by those
elements \eqref{elements} of $\cK$ which satisfy
\begin{equation}
\label{decomp}
\begin{split}
\chi_e=0 &\quad \text{if}\quad e\in \cE\quad\text{is not incident with the vertex}\quad v,\\
\chi^{(-)}_i=0 &\quad \text{if}\quad v\quad\text{is not an initial vertex of}\quad i\in \cI,\\
\chi^{(+)}_i=0 &\quad \text{if}\quad v\quad\text{is not a terminal vertex
of}\quad i\in \cI.
\end{split}
\end{equation}
Obviously, the subspaces $\cL_{v_1}$ and $\cL_{v_2}$ are orthogonal if
$v_1\neq v_2$.

Set ${^d}\cL_v:=\cL_v\oplus\cL_v\cong\C^{2\deg(v)}$. Obviously, each
$^d\cL_v$ inherits a symplectic structure from ${}^d\cK$ in a canonical way,
such that the orthogonal decomposition
\begin{equation*}
\bigoplus_{v\in V} {^d}\cL_v = {}^d\cK
\end{equation*}
holds.

\begin{definition}\label{propo}
Given the graph $\cG=\cG(V,\cI,\cE,\partial)$, boundary conditions $(A,B)$
satisfying \eqref{abcond} are called \emph{local on} $\cG$ if the maximal
isotropic subspace $\cM(A,B)$ of ${}^d\cK$ has an orthogonal symplectic
decomposition
\begin{equation}\label{propo:ortho}
\cM(A,B)=\bigoplus_{v\in V}\;\cM_v,
\end{equation}
with $\cM_v$ maximal isotropic subspaces of ${^d}\cL_v$. Otherwise the
boundary conditions are called \emph{non-local}.
\end{definition}

By Proposition 4.2 in \cite{KS4}, given the graph
$\cG=\cG(V,\cI,\cE,\partial)$, the boundary conditions $(A,B)$ satisfying
\eqref{abcond} are local on $\cG$ if and only if there is an invertible map
$C:\, \cK\rightarrow\cK$ and linear transformations $A(v)$ and $B(v)$ in
$\cL_{v}$ such that the simultaneous orthogonal decompositions
\begin{equation}\label{permut}
CA= \bigoplus_{v\in V} A(v)\quad \text{and}\quad CB= \bigoplus_{v\in V} B(v)
\end{equation}
are valid. {}From the equality $\cM(A,B)=\cM(CA, CB)$ it follows that the
subspaces $\cM_v$ in \eqref{propo:ortho} are equal to $\cM(A(v),B(v))$.


Boundary conditions $(A(v), B(v))$ induce local boundary conditions $(A,B)$
on the graph $\cG$ with
\begin{equation}\label{ab:decomp}
A= \bigoplus_{v\in V} A(v)\quad \text{and}\quad B= \bigoplus_{v\in V} B(v).
\end{equation}
{}From \eqref{permut} we get that
\begin{equation}\label{sdecomp}
\mathfrak{S}(\sk;A,B)=\mathfrak{S}(\sk;CA,CB)
 =\bigoplus_{v\in V}\mathfrak{S}(\sk;A(v),B(v))
\end{equation}
holds with respect to the orthogonal decomposition \eqref{K:ortho}.

The following proposition is taken from \cite{KS4}.

\begin{proposition}\label{k-independent}
Let $\cM=\cM(A,B)$ be a maximal isotropic subspace.
The following conditions are equivalent:
\begin{itemize}
\item[(i)]{$\mathfrak{S}(\sk;\cM)$ is $\sk$-independent,}
\item[(ii)]{$\mathfrak{S}(\sk;\cM)$ is self-adjoint for some $\sk>0$,}
\item[(iii)]{for some $\sk>0$ there is an orthogonal projection $P$ such that
$\mathfrak{S}(\sk;\cM)=\1-2P$,}
\item[(iv)]{$A B^\dagger =0$.}
\end{itemize}
\end{proposition}

Since this proposition will be crucial in what follows, we recall the

\begin{proof}
\textbf{(i) $\Leftrightarrow$ (ii).} Assume that $\mathfrak{S}(\sk;\cM)$ is
$\sk$-independent. Then, by \eqref{uuu:def}, for any eigenvector
$\chi\in\cK$ with eigenvalue $\lambda$ the equality
\begin{equation*}
(\lambda+1)A\chi + \ii\sk (\lambda-1) B\chi =0
\end{equation*}
holds for all $\sk>0$. Under the conditions \eqref{abcond} we have $\Ker A
\perp\Ker B$ (see Lemma 3.4 in \cite{KS4}). Hence, $\lambda\in\{-1,1\}$.
Thus, $\mathfrak{S}(\sk;\cM)$ is self-adjoint for all $\sk>0$.

Conversely, assume that $\mathfrak{S}(\sk;\cM)$ is self-adjoint for some
$\sk_0>0$. Due to the obvious equality
\begin{equation}\label{sinv}
\mathfrak{S}(\sk;\cM)=\bigl((\sk-\sk_{0})\mathfrak{S}(\sk_{0};\cM)+(\sk+\sk_{0})\bigr)^{-1}
\bigl((\sk+\sk_{0})\mathfrak{S}(\sk_{0};\cM)+(\sk-\sk_{0})\bigr),
\end{equation}
it is self-adjoint for all $\sk>0$. Let $\chi\in\cK$ be an arbitrary
eigenvector of $\mathfrak{S}(\sk_0;\cM)$ corresponding to the eigenvalue
$\lambda\in\{-1,1\}$. Observing that
\begin{equation*}
\frac{(\sk+\sk_0)\lambda+\sk-\sk_0}{(\sk-\sk_0)\lambda+\sk+\sk_0} = \lambda,
\end{equation*}
again by \eqref{sinv}, we conclude that  $\chi$ is an eigenvector of
$\mathfrak{S}(\sk;\cM)$ corresponding to the same eigenvalue $\lambda$ for all $\sk>0$.
Thus, $\mathfrak{S}(\sk;\cM)$ does not depend on $\sk>0$.

The equivalence \textbf{(ii) $\Leftrightarrow$ (iii)} is obvious.

The equivalence \textbf{(iv) $\Leftrightarrow$ (ii)} follows directly from
the identity
\begin{equation*}
\begin{split}
& \fS(\sk;\cM)-\fS(\sk;\cM)^\dagger\\ &\qquad = 2\ii\sk (A+\ii\sk
B)^{-1}\big[B(A^\dagger -\ii\sk B^\dagger) +(A+\ii\sk B)B^\dagger
\big](A^\dagger-\ii\sk B^\dagger)^{-1}\\ &\qquad = 4\ii\sk (A+\ii\sk
B)^{-1}A B^\dagger(A^\dagger-\ii\sk B^\dagger)^{-1}.
\end{split}
\end{equation*}
\end{proof}

We will write $\fS(\cM)$ instead of $\fS(\sk;\cM)$, whenever any of the
equivalent conditions of Proposition \ref{k-independent} is met.
Analogously we will drop the $\sk$-dependence in \eqref{sdecomp}:
\begin{equation*}
\mathfrak{S}({\cM})=\bigoplus_{v\in V}\mathfrak{S}(A(v),B(v))
=\bigoplus_{v\in V}\mathfrak{S}({\cM_v}).
\end{equation*}

{}From Proposition 3.5 in \cite{KS3} it follows that for any maximal
isotropic subspace $\cM$ satisfying any of the conditions of Proposition
\ref{k-independent}, the Laplace operator $-\Delta(\cM,\underline{a})$ is
nonnegative.

\begin{remark}
Assume that the maximal isotropic subspace $\cM\subset{}^d\cK$ satisfies any
of the conditions of Pro\-po\-sition \ref{k-independent}. By \eqref{perp}
the orthogonal maximal isotropic subspace $\cM^\perp\subset{}^d\cK$ then
also satisfies the conditions of Proposition \ref{k-independent}. {}From
\eqref{sigma:perp} it follows that $\fS(\cM^\perp)=-\fS(\cM)$.
\end{remark}

Obviously, Dirichlet $A=\1$, $B=0$ and Neumann $A=0$, $B=\1$ boundary
conditions satisfy the conditions of Proposition \ref{k-independent} with
$\fS(\1,0)=-\1$ and $\fS(0,\1)=\1$, respectively. We now provide two
important examples of boundary conditions satisfying the conditions
referred to in Proposition \ref{k-independent}.

\begin{example}[Standard boundary conditions]\label{3:ex:3}
Given a graph $\cG=\cG(V,\cI,\cE,\partial)$ for each vertex $v\in V$ with
$\deg(v)\geq 2$ define the boundary conditions $(A(v),B(v))$ the
$\deg(v)\times\deg(v)$ matrices
\begin{equation*}
\begin{aligned}
A(v)= \begin{pmatrix}
    1&-1&0&\ldots&&0&0\\
    0&1&-1&\ldots&&0 &0\\
    0&0&1&\ldots &&0 &0\\
    \vdots&\vdots&\vdots&&&\vdots&\vdots\\
    0&0&0&\ldots&&1&-1\\
    0&0&0&\ldots&&0&0
     \end{pmatrix},\quad
B(v)= \begin{pmatrix}
    0&0&0&\ldots&&0&0\\
    0&0&0&\ldots&&0&0\\
    0&0&0&\ldots&&0&0\\
    \vdots&\vdots&\vdots&&&\vdots&\vdots\\
    0&0&0&\ldots&&0&0\\
    1&1&1&\ldots&&1&1
\end{pmatrix}.
\end{aligned}
\end{equation*}
Clearly, $A(v)B(v)^\dagger=0$ and $(A(v),B(v))$ has maximal rank. The
corresponding unitary matrices \eqref{uuu:def} are given by
\begin{equation}\label{standard:ee}
[\mathfrak{S}(A(v),B(v))]_{e,e^\prime}= \frac{2}{\deg(v)} -
\delta_{e,e^\prime}
\end{equation}
with $\delta_{e,e^\prime}$ Kronecker symbol. If $\deg(v)=1$, we set
$A(v)=0$, $B(v)=1$ (Neumann boundary conditions) such that
\eqref{standard:ee} remains valid.

The local boundary conditions $(A,B)$ on the graph $\cG$ defined by
\eqref{ab:decomp} will be called \emph{standard} boundary conditions. We
use the notation $\cM_{\mathrm{st}}$ for the corresponding maximal
isotropic subspace.
\end{example}

\begin{remark}\label{3:rem:7}
Consider a graph with no internal lines
$\cG=(\{v\},\emptyset,\cE,\partial)$ and $|\cE|\geq 2$. By Proposition 2.1
in \cite{Exner:Turek}, the set of all isotropic subspaces satisfying any of
the equivalent conditions of Proposition \ref{k-independent}, contains
precisely four spaces, which correspond to the boundary conditions
invariant with respect to permutations of edges: $\cM(\1,0)$ (Dirichlet),
$\cM(0,\1)$ (Neumann), standard $\cM_{\mathrm{st}}$, and co-standard
$\cM_{\mathrm{st}}^\perp$.

Furthermore, by a result in \cite{KPS}, in the set of all isotropic
subspaces satisfying any of the equivalent conditions of Proposition
\ref{k-independent}, $\cM_{\mathrm{st}}$ is the only one with the property
that every function in the domain of $\Delta(\cM)$ is continuous at the
vertex $v$.
\end{remark}

\begin{example}[Magnetic perturbations of standard boundary conditions]\label{3:ex:mag}
If the maximal isotropic subspace $\cM(A,B)$ satisfies any of the equivalent
conditions of Proposition \ref{k-independent}, then for any unitary $U$ we
have
\begin{equation*}
AU (BU)^\dagger = A B^\dagger = 0.
\end{equation*}
Thus, the maximal isotropic subspace $\cM^U := \cM(AU, BU)$ also satisfies
the conditions of Proposition \ref{k-independent}. In particular, since
\begin{equation*}
\fS(\cM^U)= U^\dagger \fS(\cM) U,
\end{equation*}
we have the relation
\begin{equation}\label{spur}
\tr_{\cK} \fS(\cM^U) = \tr_{\cK} \fS(\cM).
\end{equation}

A special choice of unitary matrices $U$ corresponds to magnetic
perturbations of the Laplace operator $\Delta(\cM,\underline{a})$. By a
result in \cite{KS5} any magnetic perturbation of the Laplace operator
$\Delta(\cM,\underline{a})$ is unitarily equivalent to
$\Delta(\cM^U,\underline{a})$ with some $\displaystyle U=\bigoplus_{v\in V}
U_v$, where every $U_v$ is unitary and diagonal with respect to the
canonical basis in $\cL_v$,
\begin{equation*}
U_v = \diag\left(\{\e^{\ii\varphi_j(v)}\}_{j\in\cS(v)}\right).
\end{equation*}
In particular, any magnetic perturbation of standard boundary conditions
(see Example \ref{3:ex:3}) satisfies the conditions of Proposition
\ref{k-independent}.
\end{example}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Heat Kernel and Walks on the Graph}\label{sec:walks}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The Resolvent}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The structure of the underlying Hilbert space $\cH$ \eqref{hilbert} gives
naturally rise to the following definition of integral operators.

\begin{definition}
The operator $K$ on the Hilbert space $\cH$ is called \emph{integral
operator} if for all $j,j^\prime\in\cE\cup\cI$ there are measurable
functions $K_{j,j^\prime}(\cdot,\cdot)\, :\, I_j\times
I_{j\prime}\rightarrow \C$ with the following properties
\begin{itemize}
\item[(i)]{$K_{j,j^\prime}(x_j,\cdot)\varphi_{j^\prime}(\cdot)\in L^1(I_{j^\prime})$
for almost all $x_j\in I_j$,}
\item[(ii)]{$\psi=K\varphi$ with
\begin{equation}\label{kern}
\psi_j(x_j) = \sum_{j^\prime\in\cE\cup\cI} \int_{I_{j^\prime}}
K_{j,j^\prime}(x_j,y_{j^\prime}) \varphi_{j^\prime}(y_{j^\prime})
dy_{j^\prime}.
\end{equation}}
\end{itemize}
The $(|\cI|+|\cE|)\times(|\cI|+|\cE|)$ matrix-valued function $(x,y)\mapsto
K(x,y)$ with
\begin{equation*}
[K(x,y)]_{j,j^\prime} = K_{j,j^\prime}(x_j,y_{j^\prime})
\end{equation*}
is called the \emph{integral kernel} of the operator $K$.
\end{definition}

Below we will use the following shorthand notation for \eqref{kern}:
\begin{equation*}
\psi(x) = \int^{\cG} K(x,y) \varphi(y) dy.
\end{equation*}


We denote
\begin{equation}\label{U:def:neu}
R(\sk;\underline{a}) := \begin{pmatrix} \1 & 0 & 0 \\ 0 & \1 & 0 \\
0 & 0 & \e^{-\ii\sk\underline{a}}
\end{pmatrix},
\end{equation}
and
\begin{equation}\label{T:def:neu}
T(\sk;\underline{a}) := \begin{pmatrix} 0 & 0 & 0 \\ 0 & 0 &
\e^{\ii\sk\underline{a}} \\ 0 & \e^{\ii\sk\underline{a}} & 0
\end{pmatrix}
\end{equation}
with respect to the orthogonal decomposition \eqref{K:def}. The diagonal
$|\cI|\times |\cI|$ matrices $\e^{\pm \ii\sk\underline{a}}$ are given by
\begin{equation}
\label{diag} [\e^{\pm \ii\sk\underline{a}}]_{jk}=\delta_{jk}\e^{\pm \ii\sk
a_{j}}\quad
                       \text{for}\quad j,k\in\;\cI.
\end{equation}

\begin{lemma}\label{lem:Green}
For any maximal isotropic subspace $\cM\subset{}^d\cK$ the resolvent
\begin{equation*}
(-\Delta(\cM;\underline{a})-\sk^2)^{-1}\quad\text{for} \quad
\sk^2\in\C\setminus\mathrm{spec}(-\Delta(\cM;\underline{a}))\quad\text{with}\quad
\det(A+\ii\sk B)\neq 0
\end{equation*}
is the integral operator with the $(|\cI|+|\cE|)\times(|\cI|+|\cE|)$
matrix-valued integral kernel $r_{\cM}(x,y;\sk,\underline{a})$, $\Im\sk>0$,
admitting the representation
\begin{equation}\label{r:M:alternativ}
\begin{split}
& r_{\cM}(x,y;\sk,\underline{a})  = r^{(0)}(x,y,\sk)\\ & + \frac{\ii}{2\sk}
\Phi(x,\sk) R(\sk;\underline{a})^{-1}[\1-\mathfrak{S}(\sk;\cM)
T(\sk;\underline{a})]^{-1}\mathfrak{S}(\sk;\cM)R(\sk;\underline{a})^{-1}
\Phi(y,\sk)^T,
\end{split}
\end{equation}
where $R(\sk;\underline{a})$ is defined in \eqref{U:def:neu}, the matrix
$\Phi(x,\sk)$ is given by
\begin{equation*}
\Phi(x,\sk) := \begin{pmatrix}\phi(x,\sk) & 0 & 0 \\ 0 & \phi_+(x,\sk) &
\phi_-(x,\sk)
\end{pmatrix}
\end{equation*}
with diagonal matrices $\phi(x,\sk)=\diag\{\e^{\ii\sk x_j}\}_{j\in\cE}$,
$\phi_\pm(x,\sk)=\diag\{\e^{\pm\ii\sk x_j}\}_{j\in\cI}$, and
\begin{equation*}
[r^{(0)}(x,y,\sk)]_{j,j^\prime} = \ii\delta_{j,j^\prime}
\frac{\e^{\ii\sk|x_j-y_j|}}{2\sk},\quad x_j,y_j\in I_j.
\end{equation*}
If $\cI=\emptyset$, this representation simplifies to
\begin{equation*}
r_{\cM}(x,y,\sk) = r^{(0)}(x,y,\sk) + \frac{\ii}{2\sk} \phi(x,\sk)
\mathfrak{S}(\sk;\cM) \phi(y,\sk).
\end{equation*}
\end{lemma}

The integral kernel $r_{\cM}(x,y;\sk,\underline{a})$ is called
\emph{Green's function} or \emph{Green's matrix}.

The proof of Lemma \ref{lem:Green} is given in \cite{KS3}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Walks on Graphs and Cycles}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We recall the following definitions from \cite{KS3}. A nontrivial walk $\bw$
on the graph $\cG$ from $j\in\cE\cup\cI$ to $j^\prime\in\cE\cup\cI$ is an
ordered sequence formed out of edges and vertices
\begin{equation}\label{walk:def}
\{j,v_0,j_1,v_1,\ldots,j_n,v_n,j^\prime\}
\end{equation}
such that
\begin{itemize}
\item[(i)]{$j_1,\ldots,j_n\in\cI$;}
\item[(ii)]{the vertices $v_0\in V$ and $v_n\in V$ satisfy $v_0\in\partial(j)$,
$v_0\in\partial(j_1)$, $v_n\in\partial(j^\prime)$, and
$v_n\in\partial(j_n)$;}
\item[(iii)]{for any $k\in\{1,\ldots,n-1\}$ the vertex $v_k\in V$ satisfies $v_k\in\partial(j_k)$ and
$v_k\in\partial(j_{k+1})$;}
\item[(iv)]{$v_k=v_{k+1}$ for some $k\in\{0,\ldots,n-1\}$ if and only if $j_k$ is a tadpole.}
\end{itemize}
If $j,j^\prime\in\cE$ this definition is equivalent to that given in
\cite{KS4}.

The number $n$ is the \emph{combinatorial length} $|\bw|_{\mathrm{comb}}$
and the number
\begin{equation*}
|\bw|=\sum_{k=1}^n a_{j_k} >0
\end{equation*}
is the \emph{metric length} of the walk $\bw$.

A \emph{trivial} walk on the graph $\cG$ from $j\in\cE\cup\cI$ to
$j^\prime\in\cE\cup\cI$ is a triple $\{j,v,j^\prime\}$ such that
$v\in\partial(j)$ and $v\in\partial(j^\prime)$. Otherwise the walk is
called nontrivial. In particular, if $\partial(j)=\{v_0,v_1\}$, then
$\{j,v_0,j\}$ and $\{j,v_1,j\}$ are trivial walks, whereas
$\{j,v_0,j,v_1,j\}$ and $\{j,v_1,j,v_0,j\}$ are nontrivial walks of
combinatorial length $1$ and of metric length $a_j$. Both the combinatorial
and metric length of a trivial walk are zero.

We will say that the walk \eqref{walk:def} leaves the edge $j$ through the
vertex $v_0$ and enters the edge $j^\prime$ through the vertex $v_n$. A
trivial walk $\{j,v,j^\prime\}$ leaves $j$ and enters $j^\prime$ through
the same vertex $v$.

For any given walk $\bw$ from $j\in\cE\cup\cI$ to $j^\prime\in\cE\cup\cI$
we denote by $v_-(\bw)$ the vertex through which the walk leaves the edge
$j$ and by $v_+(\bw)$ the vertex through which the walk enters the edge
$j^\prime$. For trivial walks one has $v_-(\bw) = v_+(\bw)$.

Assume that the edges $j,j^\prime\in\cE\cup\cI$ are not tadpoles.
For a walk $\bw$ from $j$ to $j^\prime$ we set
\begin{equation*}
\dist(x_j, v_-(\bw)) := \begin{cases} x_j & \text{if}\quad
v_-(\bw)=\partial^-(j),\\ a_j - x_j & \text{if}\quad v_-(\bw)=\partial^+(j),
\end{cases}
\end{equation*}
and
\begin{equation*}
\dist(x_{j^\prime}, v_+(\bw)) := \begin{cases} x_{j^\prime} & \text{if}\quad
v_+(\bw)=\partial^-(j),\\ a_j - x_j & \text{if}\quad v_+(\bw)=\partial^+(j).
\end{cases}
\end{equation*}

A walk $\bw=\{j,v_0,j_1,v_1,\ldots,j_n,v_n,j^\prime\}$ \emph{traverses} an
internal edge $i\in\cI$ if $j_k=i$ for some $1\leq k \leq n$. It
\emph{visits} the vertex $v$ if $v_k=v$ for some $0\leq k \leq n$. The
\emph{score} $\underline{n}(\bw)$ of a walk $\bw$ is the set
$\{n_i(\bw)\}_{i\in\cI}$ with $n_i(\bw)\geq 0$ being the number of times
the walk $\bw$ traverses the internal edge $i\in\cI$. In particular,
\begin{equation*}
|\bw| = \sum_{i\in\cI} a_i n_i(\bw).
\end{equation*}

We say that the walk is \emph{transmitted} at the vertex $v_k$ if either
$v_k=\partial(e)$ or $v_k=\partial(e^\prime)$ or $v_k\in\partial(i_k)$,
$v_k\in\partial(i_{k+1})$, and $i_k\neq i_{k+1}$. We say that a trivial
walk from $e^\prime$ to $e$ is transmitted at the vertex
$v=\partial(e)=\partial(e^\prime)$ if $e\neq e^\prime$. Otherwise the walk
is said to be \emph{reflected}.

Let $\cW_{j,j^\prime}$, $j,j^\prime\in\cE\cup\cI$ be the (infinite if $\cI
\neq \emptyset$) set of all walks $\bw$ on $\cG$ from $j$ to $j^\prime$. By
$\cW_{j,j^\prime}(\underline{n})$, $\underline{n}\in(\N_0)^{|\cI|}$ we
denote set of all walks $\bw$ on $\cG$ from $j$ to $j^\prime$ with score
$\underline{n}$.

A walk
\begin{equation}\label{walk:ref}
\bw = \{j,v_0,j_1,v_1,\ldots,j_n,v_n,j^\prime\}
\end{equation}
is called \emph{closed} if $j=j^\prime$. It is called \emph{properly
closed} if it is closed and $v_-(\bw) \equiv v_0 \neq v_n \equiv v_+(\bw)$.
For any closed walk $\bw$ we denote by $j(\bw)$ its initial edge, that is,
$j(\bw)=j=j^\prime$.

For instance, let $j$ be an arbitrary internal edge with
$\partial(j)=\{v_0, v_1\}$, $v_0\neq v_1$. Then, the walk $\{j,v_0,j\}$ is
not properly closed, whereas $\{j,v_0,j,v_1,j\}$ is. Any closed walk from
an external edge is not properly closed.

We will say that two properly closed walks $\bw$ and $\bw^\prime$ are
equivalent, if they can be obtained from each other by successive
application of the transformation of the form
\begin{equation*}
\{j,v_0,j_1,v_1,\ldots,j_n,v_n,j\} \rightarrow
\{j_1,v_1,\ldots,j_n,v_n,j,v_0,j_1\}.
\end{equation*}

A \emph{cycle} is an equivalence class of properly closed walks.
We will say that the cycle $\fc$ is associated with a walk $\bw$ and write $\fc(\bw)$,
if $\bw$ is in the equivalence class $\fc$.

The number
\begin{equation}\label{def:length:cycle}
|\fc| := |\bw| + a_j,
\end{equation}
where $\bw$ is an arbitrary walk in the equivalence class $\fc$ and
$j=j(\bw)$, will be called the \emph{metric length} of the cycle $\fc$.
Obviously, this definition does not depend on the particular choice of the
walk $\bw$ in $\fc$. The set of all cycles on the graph $\cG$ will be
denoted by $\fC$.

We call a cycle $\fc$ \emph{primitive} if for any $\bw$ in $\fc$ there is no
integer $p\geq 2$ such that $\{p^{-1} n_i(\bw)\}_{i\in\cI}$ is a score of a
properly closed walk. For instance, if $j\in\cI$,
$\partial(j)=\{v_0,v_1\}$, $v_0\neq v_1$, the cycle associated with the
properly closed walk $\{j,v_0,j,v_1,j\}$ is primitive, whereas the cycle
associated with the properly closed walk $\{j,v_0,j,v_1,j,v_0,j,$ $v_1,
j\}$ is not.

For an arbitrary cycle $\fc$ and any $p\in\N$ we denote by $p\fc$ the unique
cycle with the following property: For any walk $\bw$ in $p\fc$ there is a
walk $\bw^\prime$ in $\fc$ with the score $\{p^{-1} n_i(\bw)\}_{i\in\cI}$.
The set of all primitive cycles on the graph $\cG$ will be denoted by
$\fC_{\mathrm{prim}}$.

The reverse of the walk $\bw$ is the walk $\bw_{\mathrm{rev}}$ is
$\{j^\prime,v_n, j_n,\ldots,v_1,j_1,v_0,j\}$. It may happen that
$\bw_{\mathrm{rev}}=\bw$. If $\bw$ is a properly closed walk, then its
reverse $\bw_{\mathrm{rev}}$ is also properly closed. We will write
$\fc_{\mathrm{rev}}$ for the equivalence class associated with
$\bw_{\mathrm{rev}}$ for $\bw$ in $\fc$. Obviously, the map
$\fc\mapsto\fc_{\mathrm{rev}}$ satisfies $(p\fc)_{\mathrm{rev}}=p
\fc_{\mathrm{rev}}$ for any $p\in\N$. From what has been just said, it
follows that the case $\fc = \fc_{\mathrm{rev}}$ may occur.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Combinatorial Expansion of the Resolvent}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

For any $\sk\in\C$ with $\Im \sk >0$, the operator $T(\sk;\underline{a})$ defined in \eqref{T:def:neu}
is a uniform contraction. Therefore,
\begin{equation}\label{series}
[\1-\mathfrak{S}(\sk;\cM)
T(\sk;\underline{a})]^{-1}\mathfrak{S}(\sk;\cM)=\sum_{n=0}^\infty
\mathfrak{S}(\sk;\cM)\left(T(\sk;\underline{a})\mathfrak{S}(\sk;\cM)\right)^n
\end{equation}
converges uniformly in $\sk$ for
$\sk$ in any of the sets $\{\sk\in\C|\Im\sk >\epsilon>0\}$. Inserting
\eqref{series} into \eqref{r:M:alternativ}, we get
\begin{equation*}
\begin{split}
& r_{\cM}(x,y;\sk,\underline{a}) = r^{(0)}(x,y,\sk)\\
& +\frac{\ii}{2\sk} \sum_{n=0}^\infty \Phi(x,\sk) R(\sk;\underline{a})^{-1}
\mathfrak{S}(\sk;\cM)\left(T(\sk;\underline{a})\mathfrak{S}(\sk;\cM)\right)^n
R(\sk;\underline{a})^{-1}\Phi(y,\sk)^T.
\end{split}
\end{equation*}
For maximal isotropic subspaces satisfying any of the equivalent conditions
of Proposition \ref{k-independent}, $\mathfrak{S}(\sk;\cM)$ is independent
of $\sk$. Thus, using \eqref{series} we get

\begin{proposition}\label{propo:res:comb}
Assume that the graph $\cG$ has no tadpoles. For any
maximal iso\-tropic subspace $\cM$ satisfying any of the equivalent
conditions of Proposition \ref{k-independent}, the Green function of the
Laplace operator $\Delta(\cM,\underline{a})$ has the absolutely converging
expansion
\begin{equation}\label{res:comb}
\begin{split}
& [r_{\cM}(x,y;\sk,\underline{a})]_{j,j^\prime} = \frac{\ii}{2\sk}
\delta_{j,j^\prime} \e^{\ii\sk|x_j-y_j|}\\
& +\frac{\ii}{2\sk} \sum_{\bw\in\cW_{j,j^\prime}} \e^{\ii\sk \dist(x_j,
v_-(\bw))} W_{\cM}(\bw) \e^{\ii\sk|\bw|} \e^{\ii\sk \dist(y_{j^\prime},
v_+(\bw))},\qquad \Im\sk>0,
\end{split}
\end{equation}
where $W_{\cM}(\bw)$ is a (complex-valued) weight of the walk
$\bw=\{j,v_0,j_1,v_1,\ldots,j_n,v_n,j^\prime\}$,
\begin{equation}\label{weight:2}
W_{\cM}(\bw) = \prod_{l=0}^{|\bw|_{\mathrm{comb}}} [\fS(A(v_l),
B(v_l))]_{i_{l+1}, i_{l}}.
\end{equation}
\end{proposition}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Heat Kernel}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The semigroup generated by the positive operator $-\Delta(\cM,
\underline{a})$ is related to its resolvent by the Dunford-Taylor integral
(see \cite[Section IX.1.6]{Kato})
\begin{equation*}
\e^{t\Delta(\cM, \underline{a})} = -\frac{1}{2\pi\ii} \int_\gamma
\e^{-t\lambda} (-\Delta(\cM, \underline{a})-\lambda)^{-1} d\lambda,
\end{equation*}
where $\gamma$ is any contour encircling a positive semiline
counterclockwise. The integral converges in the sense of Bochner.
Using the well-known identity
\begin{equation*}
\frac{1}{2\pi}\int_{-\infty+\ii\epsilon}^{+\infty+\ii\epsilon} \e^{-\sk^2
t} \e^{\ii\sk u} d\sk = g_t(u):=\frac{1}{\sqrt{4\pi t}}
\exp\left\{-u^2/4t\right\},\qquad \epsilon>0,
\end{equation*}
we immediately get the following corollary of Proposition \ref{propo:res:comb}.

\begin{corollary}\label{6:cor:1}
Assume that the maximal isotropic subspace $\cM$ satisfies any of the
equivalent conditions of Proposition \ref{k-independent} and defines local
boundary conditions on the graph $\cG$. Assume, in addition, that the graph
$\cG$ has no tadpoles. Then the heat kernel of
$-\Delta(\cM,\underline{a})$ has the absolutely convergent expansion
\begin{equation}\label{heatseries}
\begin{split}
& [p_t(x,y;\cM,\underline{a})]_{j,j^\prime} = \delta_{j,j^\prime}
g_t(x_j-y_{j})\\ &\quad + \sum_{\bw \in \cW_{j,j^\prime}} W_{\cM}(\bw)\,
g_t\big(\dist(x_j, v_-(\bw))+|\bw|+\dist(y_{j^\prime}, v_+(\bw))\big),
\end{split}
\end{equation}
The series converges uniformly in $\displaystyle x,y\in\Bigtimes_{j\in\cE\cup\cI} I_j$.
\end{corollary}

\begin{proof}
It remains to prove that the series in \eqref{heatseries} converges uniformly.
This follows from the estimate
\begin{equation*}
\begin{aligned}
& \left|\sum_{\bw \in \cW_{j,j^\prime}} W_{\cM}(\bw)\, g_t\big(\dist(x_j,
v_-(\bw))+|\bw|+\dist(x_{j^\prime}, v_+(\bw))\big)\right|\\
&\qquad\leq \frac{1}{\sqrt{4\pi t}}
\sum_{\bw \in \cW_{j,j^\prime}} \exp\{-|\bw|^2/4t\}\\
&\qquad\leq\frac{1}{\sqrt{4\pi t}}
\sum_{\underline{n}\in(\N_0)^{|\cI|}}\sum_{\bw \in
\cW_{j,j^\prime}(\underline{n})}
\exp\{-|\bw|^2/4t\}\\
&\qquad\leq \frac{1}{\sqrt{4\pi t}}\sum_{\underline{n}\in(\N_0)^{|\cI|}}
\frac{|\underline{n}|!}{\prod_{i\in\cI}n_i!}
\exp\{-|\underline{n}|^2 a_{\min}^2/4t\}\\
&\qquad\leq \frac{1}{\sqrt{4\pi t}}\sum_{n=0}^\infty |\cI|^n
\exp\{-n^2\,a_{\min}^2/4t\} < \infty,
\end{aligned}
\end{equation*}
where $\displaystyle a_{\min}=\min_{i\in\cI}\{a_j\}$.
\end{proof}

In the particular case of a connected graph with $\cI=\emptyset$ and
standard boundary conditions, we observe that $\cW_{j,j^\prime}$ consists of
precisely one walk. Hence, from \eqref{heatseries} we get the representation
(7.1) in \cite{KS3}, which has first been derived in \cite{Gaveau:2} by
different methods. In the particular case $\cM=\cM_{\mathrm{st}}$ for
compact graphs $\cG$ a representation similar to \eqref{heatseries} has been
obtained by Roth in \cite{Roth:2}.


We will now look at the situation with standard boundary conditions at all
vertices in more detail. For a given walk $\bw$ we set
\begin{equation*}
\begin{aligned}
N_{\mathrm{refl}}(\bw)&=\text{number of times the walk $\bw$ is reflected},\\
N_{\mathrm{trans}}(\bw)&=\text{number of times the walk $\bw$ is
transmitted},
\end{aligned}
\end{equation*}
such that
\begin{equation*}
N_{\mathrm{refl}}(\bw)+N_{\mathrm{trans}}(\bw)= |\bw|_{\mathrm{comb}}+1.
\end{equation*}
{}From Corollary \ref{6:cor:1} we obtain

\begin{corollary}\label{6:cor:2}
Assume that the graph $\cG$ is $k$-regular, that is, $\deg(v)=k$ for all
$v\in V$, and has no tadpoles.  Then for standard
boundary conditions at each of the vertices the heat kernel of
$-\Delta(\cM_{\mathrm{st}},\underline{a})$ has the absolutely convergent
expansion
\begin{equation}\label{reftrans2}
\begin{split}
[p_t(x,y;\cM_{\mathrm{st}},\underline{a})]_{j,j^\prime} &
=\delta_{j,j^\prime} g_t(x_j-y_j)\\  & + \sum_{\bw \in \cW_{j,j^\prime}}
\left(\frac{2-k}{k}\right)^{N_{\mathrm{refl}}(\bw)}
\left(\frac{2}{k}\right)^{N_{\mathrm{trans}}(\bw)} \\ & \cdot g_t(\dist(x_j,
v_-(\bw))+|\bw|+\dist(y_{j^\prime}, v_+(\bw))).
\end{split}
\end{equation}
\end{corollary}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The Trace Formula}\label{sec:trac:form}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

On the exterior $\cG_{\mathrm{ext}}=(\partial
V,\emptyset,\cE,\partial|_{\cE})$ of the graph $\cG=(V,\cI,\cE,\partial)$ we
consider the Laplace operators $\Delta_+:=\Delta(A_{\cE}=0, B_{\cE}=\1)$
corresponding to Neumann boundary conditions and
$\Delta_-:=\Delta(A_{\cE}=\1, B_{\cE}=0)$ corresponding to Dirichlet
boundary conditions.

Let $\cJ:\; \cH_{\cE}\rightarrow \cH$ be the embedding operator defined for
any $\chi\in\cH_{\cE}$ by $\cJ\chi=\chi\oplus 0$, where the orthogonal sum
is taken with respect to the decomposition $\cH=\cH_{\cE}\oplus\cH_{\cI}$, such that $\cJ^\dagger \cJ$ is the identity on $\cH_{\cE}$ and $\cJ\cJ^\dagger$ the orthogonal projection in $\cH$ onto $\cH_{\cE}$.
If $\cE=\emptyset$, we set $\cJ=0$.


\begin{theorem}\label{thm:4:1}
Assume that the graph $\cG$ has no tadpoles. Let the maximal isotropic
subspace $\cM$ satisfy any of the equivalent conditions of Proposition
\ref{k-independent} and assume that it defines local boundary conditions on
$\cG$. Then
\begin{equation*}
\begin{split}
\tr_{\cH}\left(\e^{t\Delta(\cM,\underline{a})} - \cJ \e^{t\Delta_\pm}
\cJ^\dagger \right) & = \frac{L}{2\sqrt{\pi t}} + \frac{1}{4} \tr_{\cK}
\fS(\cM) \mp \frac{|\cE|}{4} \\ & + \frac{1}{2\sqrt{\pi t}}
\sum_{\fc\in\fC_{\mathrm{prim}}} \sum_{p\in\N} W_{\cM}(\fc)^p
|\fc|\exp\left\{-\frac{p^2 |\fc|^2}{4t}\right\},\quad t>0,
\end{split}
\end{equation*}
where $L:=\sum_{j\in\cI} a_j$ is the total metric length of the interior of
the graph $\cG$, and $W_{\cM}(\fc)$ is the weight $W_{\cM}(\bw)$ associated
with any walk in the cycle $\fc$. In particular, if the maximal isotropic
subspace $\cM$ corresponds to a magnetic perturbation of the standard
boundary conditions (see Example \ref{3:ex:mag}), then
\begin{equation}\label{gutzw}
\begin{split}
& \tr_{\cH}\left(\e^{t\Delta(\cM,\underline{a})} - \cJ \e^{t\Delta_\pm} \cJ^\dagger
\right) = \frac{L}{2\sqrt{\pi t}} + \begin{cases}\frac{|V|-|\cI|-|\cE|}{2} & \text{for ``$+$''} \\
\frac{|V|-|\cI|}{2} & \text{for ``$-$''} \end{cases} \\ & +
\frac{1}{2\sqrt{\pi t}} \sum_{\fc\in\fC_{\mathrm{prim}}} \sum_{p\in\N}
W_{\cM_{\mathrm{st}}}(\fc)^p |\fc|\exp\left\{-\frac{p^2 |\fc|^2}{4t}\right\}
\e^{\ii p\Phi(\fc)},\quad t>0,
\end{split}
\end{equation}
where $\Phi(\fc)$ is the magnetic flux through the cycle $\fc$ defined in
\eqref{def:flux} below.
\end{theorem}

\begin{remark}
Since $\Phi(\fc_{\mathrm{rev}})=-\Phi(\fc)$ and
$W_{\cM_{\mathrm{st}}}(\fc_{\mathrm{rev}})=W_{\cM_{\mathrm{st}}}(\fc)$ (see \eqref{flux:rev} below),
the factor $\e^{\ii p\Phi(\fc)}$ in \eqref{gutzw} can be
replaced by $\cos(p\Phi(\fc))$.
\end{remark}

Before we turn to the proof of Theorem \ref{thm:4:1} we will briefly
discuss the trace formula \eqref{gutzw}. The first term on its r.h.s.\ is a
familiar Weyl term. In complete analogy with small $t$ expansion of the
trace of heat semigroups on smooth two-dimensional Riemannian manifolds
\cite{McKean:Singer}, the second term depends solely on the topology of the
graph: The number $|\cI|-|V|$ is the Euler characteristic of the graph
viewed as a simplicial complex. In the context of metric graphs the Euler
characteristics has been discussed in \cite{KS5} and \cite{KuKu}. If we
interpret the quantity $\frac{1}{2}\deg(v)-1$ as the local curvature at the
vertex $v\in V$, then \eqref{1:thm:gt} gives a discrete version of the
Gau{\ss}-Bonnet theorem for compact graphs:
\begin{equation*}
\sum_{v\in V} \left(\frac{1}{2}\deg(v)-1\right) = |\cI|-|V|.
\end{equation*}
We emphasize that the local curvature at the vertices of the graph is not a
curvature in the sense of Regge calculus \cite{Regge}. Regge calculus,
however, can be used to define local curvatures on piecewise flat (or
piecewise linear) spaces including Lipschitz-Killing curvatures and
boundary curvatures \cite{CMS}. In particular, these curvatures have been
used in \cite{CMS} to give an alternative proof of the Chern-Gau{\ss}-Bonnet
theorem for compact closed Riemannian manifolds.

In a similar vein the term $|\cI|+|\cE|-|V|$ appearing in \eqref{gutzw} can
be interpreted as the relative Euler characteristic (cf.~\cite{RS}) of the
graph $\cG$ whenever $\cG$ is noncompact, that is, when $\cE\neq\emptyset$.
In the context of exterior domains in $\R^d$, the relation of Laplace
operators on forms with absolute and relative boundary conditions (analogs
of Dirichlet and Neumann boundary conditions) to absolute and relative
Euler characteristics, respectively, has been established in \cite{BMS} as
a relative index theorem in the spirit of \cite{GL}.


The sum over primitive cycles of the graph $\cG$ in the r.h.s.\ of
\eqref{gutzw} is an analog of the sum over primitive periodic geodesics on
the manifold in the celebrated Selberg trace formula \cite{Selberg} (see
also \cite{Comtet}, \cite{Gutzwiller}, \cite{Hejhal}, \cite{Levay},
\cite{McKean}).


The remainder of this section is devoted to the proof of Theorem
\ref{thm:4:1}.

The heat semigroups $\e^{t\Delta_\pm}$ are integral operators with kernels
\begin{equation*}
h^{\pm}_t(x_j,y_j) := g_t(x_j-y_j) \pm g_t(x_j+y_j),
\end{equation*}
respectively. That the difference $\e^{t\Delta(\cM,\underline{a})} - \cJ
\e^{t\Delta_\pm} \cJ^\dagger$ is trace class follows from the fact that
$\Delta(\cM,\underline{a})$ is a finite rank perturbation of $\Delta_\pm$.
For any trace class operator $K$ on $\cH$
\begin{equation*}
\tr_{\cH} K = \sum_{j\in\cI\cup\cE} \tr_{\cH_j} P_j K P_j,
\end{equation*}
where $P_j$ is the orthogonal projection in $\cH$ onto $\cH_j$. Observe that
$P_j\left(\e^{t\Delta(\cM,\underline{a})}-\e^{t\Delta_\pm}\right)P_j$ are
integral operators on $L^2(I_j)$ with kernels jointly continuous in
$x_j,y_j\in \overset{o}{I}_j$ (due to the uniform convergence of the series
in \eqref{heatseries}). Therefore, by Corollary III.10.2 in
\cite{Gohberg:Krein}, the trace of
$P_j\left(\e^{t\Delta(\cM,\underline{a})}-\e^{t\Delta_\pm}\right)P_j$
equals the integral of its kernel over the diagonal. Hence, from Corollary
\ref{6:cor:1}, we get
\begin{equation}\label{3:9:neu}
\begin{split}
& \tr_{\cH}\left(\e^{t\Delta(\cM)} - \cJ \e^{t\Delta_\pm} \cJ^\dagger\right)\\
&\quad = \sum_{j\in\cI} \int_{I_j} g_t(0) dx_j + \sum_{j\in\cE} \int_{I_j}
[g_t(0)-h_t^\pm(x_j,x_j)] dx_j\\ &\quad + \sum_{j\in\cI\cup\cE}
\sum_{\bw\in\cW_{j,j}} W(\bw) \int_{I_j} g_t(\dist(x_j,
v_-(\bw))+|\bw|+\dist(x_j, v_+(\bw))) dx_j,
\end{split}
\end{equation}
where the sum converges absolutely. We will evaluate the different
contributions to the r.h.s.\ of \eqref{3:9:neu} separately. Essentially we
will follow the original ideas of Roth developed in \cite{Roth:2}.

\textbf{1.} We start with the terms in \eqref{3:9:neu} not associated with
any walk on the graph $\cG$. Simple calculations yield
\begin{equation*}
\int_0^{a_j} g_t(0) dx_j = \frac{a_j}{\sqrt{4\pi t}}\qquad\text{if}\qquad
j\in\cI
\end{equation*}
and
\begin{equation*}
\int_0^{\infty} \left[g_t(0)-h_t^\pm(x_j,x_j)\right] dx_j = \mp
\int_0^{\infty} g_t(2x_j) dx_j = \mp\frac{1}{4} \qquad\text{if}\qquad
j\in\cE.
\end{equation*}
Summing over all edges $j\in\cI\cup\cE$ we get the following contribution
to \eqref{3:9:neu}
\begin{equation*}
\frac{1}{\sqrt{4\pi t}} \sum_{j\in\cI} a_j \mp \frac{|\cE|}{4}.
\end{equation*}


\textbf{2.} Next we study the contributions from properly closed walks. Let
$\bw$ be a (nontrivial) properly closed walk from $j\in\cI$ to $j\in\cI$. In
this case $v_-(\bw) \neq v_+(\bw)$ and, therefore, we have
\begin{equation*}
\dist(x_j, v_-(\bw)) + \dist(x_j, v_+(\bw)) = a_j.
\end{equation*}
Therefore,
\begin{equation*}
\sum_{\text{properly closed}\, \bw\in\cW_{j,j}} W_{\cM}(\bw) \int_{I_j}
g_t(|\bw|+a_j) dx_j = a_j W_{\cM}(\bw) g_t(|\bw|+a_j)
\end{equation*}
Summing over all walks in the cycle $\fc=\fc(\bw)$ and using
\eqref{def:length:cycle} we get
\begin{equation*}
W_{\cM}(\fc) g_t(|\fc|) \sum_{\bw\in\fc} a_{j(\bw)}.
\end{equation*}
Obviously, $\displaystyle\sum_{\bw\in\fc} a_{j(\bw)}=|\fc^\prime|$ if
$\fc=p\fc^\prime$ for some $p\in\N$ and some primitive cycle $\fc^\prime$.
Thus, the sum of the contributions in \eqref{3:9:neu} from all properly
closed walks equals
\begin{equation*}
\frac{1}{2\sqrt{\pi t}} \sum_{\fc\in\fC_{\mathrm{prim}}} \sum_{p\in\N}
W_{\cM}(p\fc) |\fc|\exp\left\{-\frac{p^2 |\fc|^2}{4t}\right\},\quad t>0.
\end{equation*}
Obviously, the relation $W_{\cM}(p\fc)=W_{\cM}(\fc)^p$ holds for all
$p\in\N$.


\textbf{3.} We turn to the contributions which are not coming from properly
closed walks. In this case $v_-(\bw) = v_+(\bw)$ and, therefore, we have
\begin{equation*}
\dist(x_j, v_-(\bw)) + \dist(x_j, v_+(\bw)) = \begin{cases} 2x_j &
\text{if}\quad v_-(\bw)\in\partial^-(j),\\ 2(a_j-x_j) & \text{if}\quad v_-(\bw)\in\partial^+(j).
\end{cases}
\end{equation*}

We will call a not properly closed walk $\bw$ a walk of type $A$ if it is of
the form
\begin{equation*}
\bw=\{j_p, v_p, j_{p-1},v_{p-1},\ldots, j_0,v_0,j_0,\ldots,v_{p-1}, j_{p-1}, v_p, j_p\}.
\end{equation*}
Otherwise a not properly closed walk $\bw$ is called a walk of type $B$. By
$\cW_{j,j}^A$ and $\cW_{j,j}^B$ we denote the set of all walks from $j$ to
$j$ of type $A$ and $B$, respectively.

Obviously, any not properly closed walk is either of type $A$ or $B$. Any
walk of type $A$ is invariant with respect to reversion, that is,
$\bw_{\mathrm{rev}}=\bw$, whereas walks of type $B$ are not.


The following two lemmas complete the proof of the first part of Theorem
\ref{thm:4:1}.


\begin{lemma}\label{lem:4:6}
\begin{equation*}
\sum_{j\in\cI\cup\cE} \sum_{\bw\in \cW_{j,j}^A} W_{\cM}(\bw) \int_{I_j}
g_t(2x_j + |\bw|) dx_j  = \frac{1}{4} \tr_{\cK}\fS(\cM).
\end{equation*}
\end{lemma}

\begin{lemma}\label{lem:4:5}
\begin{equation*}
\sum_{j\in\cI\cup\cE} \sum_{\bw\in \cW_{j,j}^B} W_{\cM}(\bw) \int_{I_j}
g_t(2x_j + |\bw|) dx_j = 0.
\end{equation*}
\end{lemma}


\begin{proof}[Proof of Lemma \ref{lem:4:6}]
For an arbitrary vertex $v_0\in V$ and arbitrary $p\in\N_0$ we set
\begin{equation*}
\begin{split}
\partial G_{v_0}^{\cI}(p) & := \{\text{walks of the form
$\{j_p,v_p,j_{p-1},\ldots,j_0,v_0,j_0,\ldots,j_{p-1},v_p,j_p\}$}\\ &
\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad
\text{with $j_p\in\cI$}\},\\
\partial G_{v_0}^{\cE}(p) & := \{\text{walks of the form
$\{j_p,v_p,j_{p-1},\ldots,j_0,v_0,j_0,\ldots,j_{p-1},v_p,j_p\}$}\\ &
\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad
\text{with $j_p\in\cE$}\},\\
\partial G_{v_0}(p) & := \partial G_{v_0}^{\cI}(p) \cup \partial
G_{v_0}^{\cE}(p),\qquad \text{and}\qquad G_{v_0}(p) := \bigcup_{q=0}^p \partial
G_{v_0}(q).
\end{split}
\end{equation*}
We claim that
\begin{equation}\label{xxx}
\begin{split}
& \sum_{\bw\in G_{v_0}(p)} W_{\cM}(\bw) \int_{I_{j(\bw)}} g_t(2 x_{j(\bw)}+|\bw|)
dx_{j(\bw)} =\frac{1}{4}\tr_{\cL_{v_0}}[\fS_{v_0}]\\ & \qquad -\frac{1}{4}
\sum_{\bw\in\partial G_{v_0}^{\cI}(p)} W_{\cM}(\bw) \erfc\left(\frac{|\bw|+2
a_{j(\bw)}}{2\sqrt{t}}\right)
\end{split}
\end{equation}
holds for all $p\in\N_0$. Here for brevity we set
$\fS_{v_{0}}:=\fS(\cM_{v_{0}})$, where $\cM_{v_{0}}\subset{}^d\cL_{v_0}$ is
the maximal isotropic subspace from the orthogonal decomposition
\eqref{propo:ortho}.
\begin{equation*}
\erfc(s):=\frac{2}{\sqrt{\pi}}\int_s^\infty \e^{-u^2}\;du
\end{equation*}
denotes the complementary error function \cite{AS}. The proof is by
induction. For $p=0$ we have
\begin{equation*}
\begin{split}
\sum_{\bw\in G_{v_0}(0)} W_{\cM}(\bw) \int_{I_{j(\bw)}} g_t(2
x_{j(\bw)}+|\bw|) dx_{j(\bw)} & =
\frac{1}{4}\tr_{\cL_{v_0}}[\fS_{v_0}]\\
-\frac{1}{4} \sum_{\bw\in\partial G_{v_0}^{\cI}(0)} W_{\cM}(\bw)
\erfc\left(\frac{a_{j(\bw)}}{\sqrt{t}}\right).
\end{split}
\end{equation*}
Now assume that \eqref{xxx} holds for some $p\in\N$ and consider
\begin{equation*}
\begin{split}
& \sum_{\bw\in G_{v_0}(p+1)} W_{\cM}(\bw) \int_{I_{j(\bw)}} g_t(2 x_{j(\bw)}+|\bw|) dx_{j(\bw)} \\
&= \sum_{\bw\in G_{v_0}(p)} W_{\cM}(\bw) \int_{I_{j(\bw)}} g_t(2 x_{j(\bw)}+|\bw|) dx_{j(\bw)} \\
& + \sum_{\bw\in \partial G_{v_0}(p+1)} W_{\cM}(\bw) \int_{I_{j(\bw)}} g_t(2 x_{j(\bw)}+|\bw|) dx_{j(\bw)}\\
& = \frac{1}{4}\tr_{\cL_{v_0}}[\fS_{v_0}] -\frac{1}{4} \sum_{\bw\in\partial G_{v_0}^{\cI}(p)} W_{\cM}(\bw) \erfc\left(\frac{|\bw|+2 a_{j(\bw)}}{2\sqrt{t}}\right)\\
& + \frac{1}{4} \sum_{\bw\in \partial G_{v_0}^{\cE}(p+1)} W_{\cM}(\bw) \erfc\left(\frac{|\bw|}{2\sqrt{t}}\right)\\
& +\frac{1}{4} \sum_{\bw\in\partial G_{v_0}^{\cI}(p+1)} W_{\cM}(\bw)
\left[\erfc\left(\frac{|\bw|}{2\sqrt{t}}\right)-\erfc\left(\frac{|\bw|+2 a_{j(\bw)}}{2\sqrt{t}}\right)\right]\\
&= \frac{1}{4}\tr_{\cL_{v_0}}[\fS_{v_0}] -\frac{1}{4} \sum_{\bw\in\partial G_{v_0}^{\cI}(p)} W_{\cM}(\bw) \erfc\left(\frac{|\bw| +2 a_{j(\bw)}}{2\sqrt{t}}\right)\\
& +\frac{1}{4} \sum_{\bw\in\partial G_{v_0}(p+1)} W_{\cM}(\bw)
\erfc\left(\frac{|\bw|}{2\sqrt{t}}\right)\\ & -\frac{1}{4} \sum_{\bw\in\partial
G_{v_0}^{\cI}(p+1)} W_{\cM}(\bw) \erfc\left(\frac{|\bw|+2 a_{j(\bw)}}{2\sqrt{t}}\right).
\end{split}
\end{equation*}
It remains to prove that the sum of the second and third terms on the r.h.s.\ is zero. Let
$\bw\in\partial G_{v_0}(p+1)$ be arbitrary. Write the walk $\bw$ as $\bw = \{j_{p+1}, v_{p+1},
j_p,\ldots, j_0, v_0, j_0, \ldots, j_p,$ $v_{p+1}, j_{p+1}\}$. Then
$\bw^\prime :=\{j_p,\ldots, j_0, v_0, j_0, \ldots, j_p\}\in\partial
G_{v_0}(p)$ with $j_p\in\cI$. Hence,
\begin{equation*}
W_{\cM}(\bw)=[\fS_{v_{p+1}}]_{j_p,j_{p+1}} [\fS_{v_{p+1}}]_{j_{p+1},j_p}
W_{\cM}(\bw^\prime)
\end{equation*}
and $|\bw|=|\bw^\prime|+2a_{j(\bw^\prime)}$. Thus,
\begin{equation*}
\begin{split}
& \sum_{\bw\in\partial G_{v_0}(p+1)} W_{\cM}(\bw)
\erfc\left(\frac{|\bw|}{2\sqrt{t}}\right) \\ & \quad =
\sum_{\bw^\prime\in\partial G_{v_0}^{\cI}(p)} W_{\cM}(\bw^\prime)
\erfc\left(\frac{|\bw^\prime|+2a_{j(\bw^\prime)}}{2\sqrt{t}}\right)\\
& \quad\quad\cdot\sum_{j_{p+1}\in\cS(v_{p+1})} [\fS_{v_{p+1}}]_{j_p,j_{p+1}}
[\fS_{v_{p+1}}]_{j_{p+1},j_p}.
\end{split}
\end{equation*}
By (iii) in Proposition \ref{k-independent}, we have $\fS_{v_{p+1}}^2=\1$
and, therefore,
\begin{equation*}
\sum_{j_{p+1}\in\cS(v_{p+1})} [\fS_{v_{p+1}}]_{j_p,j_{p+1}}
[\fS_{v_{p+1}}]_{j_{p+1},j_p} = [\fS_{v_{p+1}}^2]_{j_p,j_{p}} = 1,
\end{equation*}
which completes the proof of \eqref{xxx}.

By the absolute convergence of the series \eqref{3:9:neu}, from \eqref{xxx}
it follows that
\begin{equation*}
\lim_{p\to\infty} \sum_{\bw\in G_{v_0}(p)} W_{\cM}(\bw) \int_{I_{j(\bw)}}
g_t(2x_{j(\bw)} + |\bw|) dx_{j(\bw)} = \frac{1}{4} \tr_{\cL_{v_0}}
\fS_{v_0}.
\end{equation*}
Observing that
\begin{equation*}
\begin{split}
& \sum_{j\in\cI\cup\cE} \sum_{\bw\in\cW_{j,j}^A} W_\cM(\bw) \int_{I_j} g_t(2x_j +|\bw|) dx_j\\
& =\lim_{p\to\infty}
\sum_{v_0\in V}\sum_{\bw\in G_{v_0}(p)} W_{\cM}(\bw) \int_{I_{j(\bw)}} g_t(2 x_{j(\bw)}+|\bw|)
dx_{j(\bw)},
\end{split}
\end{equation*}
we obtain the claim of the lemma.
\end{proof}

\begin{proof}[Proof of Lemma \ref{lem:4:5}]
Any not properly closed walk of type $B$ is obviously of the form
\begin{equation*}
\{j_p, v_p, j_{p-1},\ldots,j_0,v_0, \fs, v_0,j_0, \ldots, j_{p-1}, v_p,
j_p\}
\end{equation*}
for some $p\in\N_0$, where $\fs$ stands for the sequence of internal edges and vertices
$i_1^\prime, v_1^\prime,\ldots,$ $v_n^\prime,i_n^\prime$ with $i_1^\prime\neq
i_n^\prime$. For an arbitrary $p\in\N_0$ we set
\begin{equation*}
\begin{split}
\partial F_{\fs, v_0}^{\cI}(p) & :=\{\text{walks of the form}\,\{j_p, v_p, j_{p-1},\ldots,j_0,v_0, \fs, v_0,j_0, \ldots, j_{p-1}, v_p,
j_p\}\\  &
\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\text{with}\quad
j_p\in\cI\},\\
\partial F_{\fs, v_0}^{\cE}(p) & :=\{\text{walks of the form}\,\{j_p, v_p, j_{p-1},\ldots,j_0,v_0, \fs, v_0,j_0, \ldots, j_{p-1}, v_p,
j_p\}\\  &
\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\text{with}\quad
j_p\in\cE\},\\
\partial F_{\fs, v_0}(p) & :=\partial F_{\fs, v_0}^{\cI}(p)\cup \partial
F_{\fs, v_0}^{\cE}(p),\qquad \text{and} \qquad \displaystyle F_{\fs,
v_0}(p):=\bigcup_{q=0}^p
\partial F_{\fs, v_0}(q).
\end{split}
\end{equation*}
We claim that
\begin{equation}\label{xxx:2}
\begin{split}
& \sum_{\bw\in F_{\fs, v_0}(p)} W_{\cM}(\bw) \int_{I_j(\bw)}
g_t(2x_{j(\bw)}+|\bw|) dx_{j(\bw)}\\ & \qquad = - \frac{1}{4}
\sum_{\bw\in\partial F_{\fs, v_0}^{\cI}(p)} W_{\cM}(\bw)
\erfc\left(\frac{|\bw|+2a_{j(\bw)}}{2\sqrt{t}}\right).
\end{split}
\end{equation}
The proof is again by induction. For $p=0$ we have
\begin{equation}\label{claim:p=0}
\begin{split}
& \sum_{\bw\in F_{\fs, v_0}(0)} W_{\cM}(\bw) \int_{I_{j(\bw)}}
g_t(2x_{j(\bw)}+|\bw|) dx_{j(\bw)}\\ & = \sum_{\bw\in \partial F_{\fs,
v_0}^{\cE}(0)} W_{\cM}(\bw) \int_{I_{j(\bw)}} g_t(2x_{j(\bw)} + |\bw|) dx_{j(\bw)}\\
& + \sum_{\bw\in \partial F_{\fs, v_0}^{\cI}(0)} W_{\cM}(\bw)
\int_{I_{j(\bw)}} g_t(2x_{j(\bw)} + |\bw|) dx_{j(\bw)}.
\end{split}
\end{equation}
Obviously, for any $\bw\in F_{\fs, v_0}(0)$ we have
$W_{\cM}(\bw)=[\fS_{v_0}]_{j,i_1^\prime} [\fS_{v_0}]_{i_n^\prime,j}
W^\prime_{\cM}$, where $W^\prime_{\cM}$ is a weight associated with the
sequence $\fs$ and $j=j(\bw)$. Therefore, if $j\in\cE$, then
\begin{equation*}
W_{\cM}(\bw) \int_{I_j} g_t(2x_{j} + |\bw|) dx_{j} = \frac{1}{4}
[\fS_{v_0}]_{j,i_1^\prime} [\fS_{v_0}]_{i_n^\prime,j} W^\prime_{\cM}
\erfc\left(\frac{|\bw|}{2\sqrt{t}}\right),
\end{equation*}
and, if $j\in\cI$, then
\begin{equation*}
\begin{split}
& W_{\cM}(\bw) \int_{I_j} g_t(2x_{j} + |\bw|) dx_{j} \\ & = \frac{1}{4}
[\fS_{v_0}]_{j,i_1^\prime} [\fS_{v_0}]_{i_n^\prime,j} W^\prime_{\cM}
\left(\erfc\left(\frac{|\bw|}{2\sqrt{t}}\right)-\erfc\left(\frac{|\bw|+2a_j}{2\sqrt{t}}\right)\right).
\end{split}
\end{equation*}
Again we use $\fS_{v_0}^2 = \1$, which in combination with $i_1^\prime\neq i_n^\prime$ gives
\begin{equation*}
\begin{split}
& \frac{1}{4} W^\prime_{\cM} \erfc\left(\frac{|\bw|}{2\sqrt{t}}\right)
\sum_{j\in\cS(v_0)} [\fS_{v_0}]_{j,i^\prime_1} [\fS_{v_0}]_{i^\prime_n,j} \\
& =\frac{1}{4} W^\prime_{\cM} \erfc\left(\frac{|\bw|}{2\sqrt{t}}\right)
\sum_{j\in\cS(v_0)} [\fS_{v_0}^2]_{i^\prime_n,i^\prime_1} = 0.
\end{split}
\end{equation*}
Combining this with \eqref{claim:p=0}, we get the claim \eqref{xxx:2} for
$p=0$. The proof of the induction step follows the same line as in the proof of
Lemma \ref{lem:4:6} and will, therefore, be omitted.

By the absolute convergence of the series \eqref{3:9:neu}, from
\eqref{xxx:2} it follows that
\begin{equation*}
\lim_{p\rightarrow\infty} \sum_{\bw\in F_{\fs, v_0}(p)} W_{\cM}(\bw)
\int_{I_{j(\bw)}} g_t(2x_{j(\bw)}+|\bw|) dx_{j(\bw)}=0,
\end{equation*}
which completes the proof of the lemma.
\end{proof}

To complete the proof of Theorem \ref{thm:4:1} it remains to consider the
particular case of magnetic perturbations of standard boundary conditions
(see Examples \ref{3:ex:3} and \ref{3:ex:mag}). We assume that the maximal
isotropic subspace $\cM$ corresponds to the magnetic perturbation of the
Laplace operator $-\Delta(\cM_{\mathrm{st}},\underline{a})$ with standard
boundary conditions, that is,
\begin{equation*}
\cM=\cM_{\mathrm{st}}^U\quad\text{with}\quad U=\bigoplus_{v\in V} U_v,\quad
U_v=\diag\left(\{\e^{\ii\varphi_j(v)}\}_{j\in\cS(v)}\right).
\end{equation*}

First we calculate $\tr_\cK \fS(\cM)$. Using \eqref{1:thm:gt},
\eqref{standard:ee}, and \eqref{spur} we get
\begin{equation*}
\begin{split}
\tr_\cK \fS(\cM) & = \tr_\cK \fS(\cM_{\mathrm{st}}) = \sum_{v\in V}
\sum_{j\in\cS(v)} [\fS_v(\cM_{\mathrm{st}})]_{j,j}\\
&= \sum_{v\in V} (2-\deg(v)) = 2|V|-|\cE|-2|\cI|.
\end{split}
\end{equation*}

Let $H_1(\cG,\Z)$ be the first homology group of the interior
$\cG_{\mathrm{int}}$ of the graph $\cG$. There is a canonical map $\Gamma:
\mathfrak{C}\to H_1(\cG,\Z)$, which satisfies
\begin{equation*}
\Gamma(\mathfrak{c}_{rev})=-\Gamma(\mathfrak{c}),\qquad
\Gamma(p\mathfrak{c})=p\Gamma(\mathfrak{c}),\qquad p\in\N.
\end{equation*}
In particular, $\Gamma(\mathfrak{c})=0$ when
$\mathfrak{c}=\mathfrak{c}_{\mathrm{rev}}$. Therefore, the map $\Gamma$ is
not injective. In general it is also not surjective. For any cycle
$\fc\in\fC$ we set
\begin{equation*}
\Phi(\fc):=\widetilde{\Phi}(\Gamma(\fc)),
\end{equation*}
where $\widetilde{\Phi}(\Gamma(\fc))$ is the magnetic flux through the
homological cycle $\Gamma(\fc)$ as defined in \cite{KS5}. If
\begin{equation*}
\bw=\{j_0,v_0,j_1,\ldots,j_n,v_n,j_0\}
\end{equation*}
is an arbitrary walk in the equivalence class $\fc$, then by explicit calculations the magnetic flux
through the cycle $\fc$ (see \cite{KS5}) is given by
\begin{equation}\label{def:flux}
\Phi(\fc) = \sum_{k=0}^{n-1} \left(\varphi_{j_k}(v_k) -
\varphi_{j_{k+1}}(v_k)\right) + \left(\varphi_{j_n}(v_n)-\varphi_{j_0}(v_n)\right).
\end{equation}
Obviously,
\begin{equation*}
W_{\cM}(\fc) = W_{\cM_{\mathrm{st}}}(\fc) \e^{\ii\Phi(\fc)}
\end{equation*}
and
\begin{equation}\label{flux:rev}
\Phi(\fc_{\mathrm{rev}})=-\Phi(\fc).
\end{equation}
By Proposition \ref{k-independent}, we have
$W_{\cM}(\fc_{\mathrm{rev}})=\overline{W_{\cM}(\fc)}$. In particular, if
$\fc_{\mathrm{rev}}=\fc$, then $W_{\cM}(\fc)$ is real. Since
$\Phi(\fc_{\mathrm{rev}})=-\Phi(\fc)$ and
$W_{\cM_{\mathrm{st}}}(\fc_{\mathrm{rev}})=W_{\cM_{\mathrm{st}}}(\fc)$, the
factor $\e^{\ii p\Phi(\fc)}$ in \eqref{gutzw} can be replaced by
$\cos(p\Phi(\fc))$. This completes the proof of Theorem \ref{thm:4:1}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Applications to Inverse Problems}\label{sec:inv:probl}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In this section we present an application of the trace formula in Theorem
\ref{thm:4:1} to inverse spectral and scattering problems. Throughout the
whole section we will assume that the maximal isotropic subspace $\cM$
satisfies any of the equivalent assumption of Proposition
\ref{k-independent}.

For the noncompact graph $\cG$ let $S(\lambda;\cM,\underline{a}):
\cK_{\cE}\rightarrow\cK_{\cE}$, $\lambda>0$, be the scattering matrix for
the triple $(-\Delta(\cM;\underline{a}),$  $-\Delta_+, \cJ)$ defined in
\cite{KS} according to the scattering theory in two Hilbert spaces
\cite[Chapter 2]{Yafaev}. Here $\cJ$ is the identification operator defined
in Section \ref{sec:trac:form}. The scattering matrix is continuous with
respect to the spectral parameter $\lambda>0$ (see \cite{KS1} or
\cite[Theorem 3.12]{KS4}).

Let $\xi(\lambda;\cM,\underline{a})$ be the spectral shift function
associated with the triple $(-\Delta(\cM;\underline{a}),$  $-\Delta_+,
\cJ)$ (see \cite[Section 8.11]{Yafaev}). It satisfies the trace formula
\begin{equation}\label{trace}
\begin{split}
\tr_{\cH}\left[\e^{t\Delta(\cM;\underline{a})}-\cJ\e^{t\Delta_+}\cJ^\dagger
\right] & + \tr_{\cH_{\cE}}\left[(\cJ^\dagger\cJ-I_{\cH_{\cE}})\e^{t\Delta_+}\right] \\
& = -t\int_0^\infty
\xi(\lambda;\cM,\underline{a})\e^{-t\lambda}d\lambda,\quad t>0,
\end{split}
\end{equation}
and is fixed uniquely by the condition $\xi(-1;\cM,\underline{a})=0$. From
the definition of the operator $\cJ$ it follows that the second term on the
r.h.s.\ of \eqref{trace} vanishes. Thus,
\begin{equation*}
\tr_{\cH}\left(\e^{t\Delta(\cM,\underline{a})} - \cJ \e^{t\Delta_+}
\cJ^\dagger \right) =  -t \int_0^\infty \e^{-\lambda t} \xi(\lambda;\cM)
d\lambda ,\quad t>0.
\end{equation*}
By the Birman-Krein theorem the spectral shift function is related to the
scattering matrix,
\begin{equation}\label{Birman:Krein}
\det_{\cK_{\cE}} S(\lambda;\cM, \underline{a})=\exp\{-2\pi i\xi(\lambda;\cM,
\underline{a})\}\qquad\text{a.e.}\quad\lambda\in\R_+.
\end{equation}

By the continuity of the scattering matrix and due to \eqref{Birman:Krein}
one can choose the branch of the logarithm such that
\begin{equation}\label{scatt:phase}
s(\lambda; \cM,\underline{a}):= \frac{1}{2\ii}\log\det_{\cK_{\cE}}
S(\lambda;\cM,\underline{a})
\end{equation}
is continuous with respect to $\lambda\in(0,\infty)$ and satisfies
\begin{equation*}
s(0+; \cM,\underline{a}) =-\pi\left(\xi(0+; \cM,\underline{a})+N(0+; \cM,\underline{a}) \right),
\end{equation*}
where $N(\lambda; \cM,\underline{a})$ is the counting function for the eigenvalues of the
operator $-\Delta(\cM,\underline{a})$. The function \eqref{scatt:phase} is
called the \emph{scattering phase}. The scattering phase and the eigenvalue
counting function uniquely determine  the spectral shift function,
\begin{equation*}
\xi(\lambda;\cM,\underline{a}) = -\frac{1}{\pi}
s(\lambda;\cM,\underline{a}) - N(\lambda; \cM,\underline{a}), \quad\lambda\in\R_+.
\end{equation*}

For compact graphs the spectral shift function is determined by the eigenvalue counting function alone,
$\xi(\lambda;\cM,\underline{a}) = - N(\lambda; \cM,\underline{a})$, $\lambda\in\R_+$.


\begin{proposition}\label{propo:5:1}
Assume that the graph $\cG$ (compact or noncompact) has no tadpoles. Let
the maximal isotropic subspace $\cM$ satisfy any of the equivalent
conditions of Proposition \ref{k-independent} and define local boundary
conditions. Then the spectral shift function $\R_+\ni\lambda\mapsto
\xi(\lambda)$ uniquely determines the set
\begin{equation}\label{red:spectrum}
\Bigl\{\ell>0\,\Big|\, \sum_{\substack{\fc\in\fC\\ |\fc|=\ell}} W_{\cM}(\fc)\neq 0 \Bigr\}.
\end{equation}
\end{proposition}

In \cite{KuNo} the set \eqref{red:spectrum} is called  the ``reduced length
spectrum''.

\begin{proof}
Using standard formulas for the inverse Laplace transform and, in
particular, the fact that $t^{-3/2} \e^{-a/t}$, $a>0$, is the Laplace transform of
$(\pi a)^{-1/2}\sin(2\sqrt{a\lambda})$, from Theorem \ref{thm:4:1}
we get
\begin{equation}\label{xi:per}
\begin{split}
-\xi(\lambda;\cM,\underline{a}) & = \frac{L}{\pi}\sqrt{\lambda} +
\frac{1}{4}\tr_{\cK} \fS(\cM)-\frac{|\cE|}{4}\\ & + \frac{1}{\pi}
\sum_{\fc\in\fC_{\mathrm{prim}}} \sum_{p\in\N} \frac{1}{p} W_{\cM}(\fc)^p
\sin\left(p|\fc| \sqrt{\lambda}\right),\quad \lambda > 0,
\end{split}
\end{equation}
where the series converges in the sense of distributions on
$\R_+$. For $\sk\in\R$ define the function $u(\sk)$ via
\begin{equation*}
u(\sk) := \begin{cases} -\xi(\sk^2; \cM,\underline{a}) & \text{if}\quad
\sk>0,\\ \phantom{-}\xi(\sk^2; \cM,\underline{a}) & \text{if}\quad \sk<0.
\end{cases}
\end{equation*}
Using \eqref{xi:per} we can calculate the distributional derivative of $u$,
\begin{equation*}
\begin{split}
u'(\sk) & = \frac{L}{\pi} + \left(\frac{1}{2}\tr_{\cK}
\fS(\cM)-\frac{|\cE|}{2}\right) \delta(\sk)\\ & + \frac{1}{\pi}
\sum_{\fc\in\fC_{\mathrm{prim}}} \sum_{p\in\N} W_{\cM}(\fc)^p |\fc|
\cos\left(p|\fc| \sk\right),\quad \sk\in\R,
\end{split}
\end{equation*}
where $\delta$ stands for the Dirac $\delta$-distribution.
Its Fourier transform with respect to $\sk$ yields
\begin{equation*}
\begin{split}
\int_\R \e^{\ii\omega\sk} u'(\sk) d\sk & =2L \delta(\omega) +
\frac{1}{2}\tr_{\cK} \fS(\cM)-\frac{|\cE|}{2}\\ & +
\sum_{\fc\in\fC_{\mathrm{prim}}} \sum_{p\in\N} W_{\cM}(\fc)^p |\fc|
\left[\delta(\omega-p|\fc|) + \delta(\omega+p|\fc|)\right],
\end{split}
\end{equation*}
which implies the claim.
\end{proof}


\begin{theorem}\label{thm:inv:probl}
Assume that the graph $\cG$ (compact or noncompact) has no tadpoles. Let
the maximal isotropic subspace $\cM$ satisfy any of the equivalent
conditions of Proposition \ref{k-independent} and define local boundary
conditions on the graph $\cG$. Assume, in addition, that
\begin{itemize}
\item[(i)]{the lengths $a_{i}\,(i\in\cI)$ of the internal edges of the
graph $\cG$ are rationally independent, that is, the equation
\begin{equation*}
\sum_{i\in\cI}n_{i}\, a_{i} = 0
\end{equation*}
with \emph{integer} $n_{i}\in\Z$ has no non-trivial solution;}
\item[(ii)]{for any vertex $v\in V$, none of the matrix elements $[\fS_v]_{j,j^\prime}$,
$j,j^\prime\in\cS(v)$, vanishes.}
\end{itemize}
Then the spectral shift function $\R_+\ni\lambda\mapsto \xi(\lambda)$
uniquely determines the interior $\cG_{\mathrm{int}}$ of the graph $\cG$.
\end{theorem}

\begin{proof}
All arguments of Section 4 in \cite{KuNo} remain valid for boundary
conditions satisfying assumption (ii) of the theorem. Thus, the set
\eqref{red:spectrum} uniquely determines the interior $\cG_{\mathrm{int}}$
of the graph $\cG$. Combining this with Proposition \ref{propo:5:1} we
obtain the claim.
\end{proof}

Note that assumption (ii) of Theorem \ref{thm:inv:probl} implies that if
$\cM_v$ corresponds to the standard boundary conditions at the vertex $v$
or its magnetic perturbation, then necessarily $\deg(v)\neq 2$.


\begin{remark}
As in \cite{Novaszek} the assumption on the rational independence of the
edge lengths can be slightly relaxed.
\end{remark}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{thebibliography}{50}

\bibitem{AS} M.~Abramowitz and I.~A.~Stegun,
    \textit{Handbook of Mathematical Functions},
    Dover, New York, 1972.

\bibitem{ACDMT} E.~Akkermans, A.~Comtet, J.~Debois, G.~Montambaux, and
    C.~Texier, \textit{Spectral determinant on quantum graphs}, Ann. Phys.
    (N.Y.) \textbf{284} (2000), 10 -- 51.

\bibitem{Angad-Guar} H.~W.~K.~Angad-Gaur, B.~Gaveau, and M.~Okada, \textit{Explicit heat
    kernel on generalized cones}, SIAM J. Math. Anal. \textbf{25} (1994), 1562
    -- 1576.

\bibitem{Arnold} V.~I.~Arnold, \textit{The complex Lagrangian Grassmannian}, Funct. Anal. Appl.
    \textbf{34} (2000), 208 -- 210.

\bibitem{BMS} N.~V.~Borisov, W.~M\"{u}ller, and R.~Schrader, \textit{Relative index
    theorems ans supersymmetric scattering theory}, Comm. Math. Phys.
    \textbf{114} (1988), 475 --  513.

\bibitem{Bott} R.~Bott, \textit{Stable homotopy of the classical groups},
    Ann. Math. \textbf{70} (1959), 313 -- 373.

\bibitem{Chavel} I.~Chavel, \textit{Eigenvalues in Riemannian geometry},
    Pure and Applied Mathematics, Vol.~115. Academic Press, Orlando, 1984.

\bibitem{CMS} J.~Cheeger, W.~M\"{u}ller, and R.~Schrader,
    \textit{On the curvature of piecewise flat spaces}, Comm. Math. Phys. \textbf{92} (1984),
    405 -- 454.

\bibitem{Verdiere} Y.~Colin de Verdi\`{e}re,
    \textit{Spectres de graphes}, Cours Sp\'{e}cialis\'{e}s, Vol.~4. Soci\'{e}t\'{e}
    Math\'{e}matique de France, Paris, 1998.

\bibitem{Comtet} A.~Comtet, B.~Georgeot, and S.~Ouvry,
    \textit{Trace formula for Riemann surfaces with magnetic field}, Phys. Rev. Lett. \textbf{71} (1993), 3786 -- 3789.

\bibitem{Diestel} R.~Diestel, \textit{Graph Theory}, Springer, New
    York, 2000.

\bibitem{Exner:Turek} P.~Exner and O.~Turek, \textit{Approximations of
    permutation-symmetric vertex couplings in quantum graphs}, in G.~Berkolaiko, R.~Carlson,
    S.~A.~Fulling, and P.~Kuchment (Eds.),
    \textit{Quantum Graphs and Their Applications}, Contemp. Math. Vol. 415,
    Amer. Math. Soc., Providence, RI, 2006. p.~109 -- 120.

\bibitem{Gaveau:1} B.~Gaveau, M.~Okada, and T.~Okada,
    \textit{Explicit heat kernels on graphs and spectral analysis}, in
    J.~E.~Fornaess (Ed.), \textit{Several Complex Variables}, (Proceedings of
    the Mittag-Leffler Institute, Stockholm, 1987-88), Princeton Math. Notes
    Vol.~38, Princeton University Press, 1993. pp.~364 -- 388.

\bibitem{Gaveau:2} B.~Gaveau and M.~Okada,
    \textit{Differential forms and heat diffusion on one-dimensional singular
    varieties}, Bull. Sci. Math., II. S\'{e}r., \textbf{115} (1991), 61 -- 80.

\bibitem{Gilkey} P.~B.~Gilkey, \textit{Invariance Theory, the Heat Equation and the
    Atiyah-Singer Index Theorem}, Mathematics Lecture Series Vol.~11, Publish
    or Perish, Wilmington (1984).

\bibitem{GnuS} S.~Gnutzmann and U.~Smilansky, \textit{Quantum graphs: Applications to
    quantum chaos and universal spectral statistics}, Adv. Phys. \textbf{55}
    (2006), 527 -- 625.

\bibitem{Gohberg:Krein} I.~C.~Gohberg and M.~G.~Krein,
    \textit{Introduction to the Theory of Linear Nonselfadjoint Operators in
    Hilbert Space}, Amer. Math. Soc. Transl. of Math. Monographs 18,
    Providence, RI, 1969.

\bibitem{GL} M.~Gromov and H.~B.~Lawson, Jr., \textit{Positive scalar curvature and
    the Dirac operator on complete Riemannian manifolds},  Inst. Hautes \'{E}tudes Sci. Publ. Math.
    \textbf{58} (1983), 295 -- 408.

\bibitem{GS} B.~Gutkin and U.~Smilansky, \textit{Can one hear the
    shape of a graph?}, J. Phys. A: Math. Gen. \textbf{34} (2001), 6061 -- 6068.

\bibitem{Gutzwiller} M.~C.~Gutzwiller, \textit{Chaos in Classical and
   Quantum Mechanics}, Interdiscipinary Applied Mathematics, Vol.~1,
   Springer, New York, 1990.

\bibitem{H} M.~Harmer, \textit{Hermitian symplectic geometry and
    extension theory}, J. Phys. A: Math. Gen. \textbf{33} (2000), 9193 --
    9203.

\bibitem{Hejhal} D.~Hejhal, \textit{The Selberg Trace Formula for PSL(2, $\R$)}, Vol.~2,
    Lecture Notes in Math., Vol.~1001. Springer, Berlin, 1983.

%\bibitem{Jungnickel} D.~Jungnickel, \textit{Graphs, Networks and
%    Algorithms}, Algorithms and Computation in Mathematics, Vol.~5. Springer,
%    Berlin, 2005.

\bibitem{Kato} T.~Kato, \textit{Perturbation Theory for Linear
    Operators}, Springer-Verlag, Berlin, 1966.

\bibitem{KS1} V.~Kostrykin and R.~Schrader, \textit{Kirchhoff's rule
    for quantum wires}, J. Phys. A: Math. Gen. \textbf{32} (1999), 595 --
    630.

\bibitem{KS2} V.~Kostrykin and R.~Schrader, \textit{Kirchhoff's rule
    for quantum wires II: The inverse problem with possible
    applications to quantum computers}, Fortschr. Phys. \textbf{48} (2000),
    703 -- 716.

\bibitem{KS} V.~Kostrykin and R.~Schrader, \textit{The generalized
    star product and the factorization of scattering matrices on
    graphs}, J. Math. Phys. \textbf{42} (2001), 1563 -- 1598.

\bibitem{KS5} V.~Kostrykin and R.~Schrader,
    \textit{Quantum wires with magnetic fluxes},
    Comm. Math. Phys. \textbf{237} (2003), 161 -- 179.

\bibitem{KS3} V.~Kostrykin and R.~Schrader, \textit{Laplacians on metric graphs:
    Eigenvalues, resolvents and semigroups}, in G.~Berkolaiko, R.~Carlson,
    S.~A.~Fulling, and P.~Kuchment (Eds.), \textit{Quantum Graphs and Their
    Applications}, Contemp. Math. Vol. 415, Amer. Math. Soc., Providence, RI,
    2006. p.~201 -- 225.

\bibitem{KS4} V.~Kostrykin and R.~Schrader, \textit{The inverse scattering problem
    for metric graphs and the traveling salesman problem}, preprint
    \texttt{arXiv:math-ph/0603010} (2006).

\bibitem{KPS} V.~Kostrykin, J.~Potthoff, and R.~Schrader, in preparation.

\bibitem{Kottos} T.~Kottos and U.~Smilansky, \textit{Periodic orbit theory and spectral
    statistics for quantum graphs}, Ann. Phys. (N.Y.) \textbf{274} (1999), 76 --
    124.

\bibitem{Kottos:2} T.~Kottos and U.~Smilansky, \textit{Chaotic scattering on
    graphs}, Phys. Rev. Lett. \textbf{85} (2000), 968 -- 971.

\bibitem{Kottos:3} T.~Kottos and U.~Smilansky, \textit{Quantum graphs: A simple model for chaotic
    scattering}, J. Phys. A: Math. Gen. \textbf{36} (2003), 3501 -- 3524.

\bibitem{Kuchment:0} P.~Kuchment, \textit{Graph models for waves in thin
    structures}, Waves Random Media \textbf{12} (2002), R1 -- R24.

\bibitem{KuNo} P.~Kurasov and M.~Nowaszyk, \textit{Inverse
    spectral problem for quantum graphs}, J. Phys. A:
    Math. Gen. \textbf{38} (2005), 4901 -- 4915. Corrigendum:
    J. Phys. A: Math. Gen. \textbf{39} (2006), 993.

\bibitem{KuKu} P.~Kurasov, \textit{Graph Laplacians and topology}, preprint
(2006).

\bibitem{Levay} P.~L\'{e}vay,
    \textit{On Selberg's trace formula: Chaos, resonances and time delays}, J.
    Phys. A: Math. Gen. \textbf{33} (2000), 4357 -- 4376.

\bibitem{McKean} H.~P.~McKean,  \textit{Selberg's trace formula as applied to a compact Riemann surface},
    Comm. Pure Appl. Math. \textbf{25} (1972), 225 -- 246;  Correction:
    Comm. Pure Appl. Math. \textbf{27} (1974), 134.

\bibitem{McKean:Singer} H.~P.~McKean and I.~M.~Singer, \textit{Curvature and
the eigenvalues of the Laplacian}, J. Diff. Geom. \textbf{1} (1967), 43 --
69.

\bibitem{Nicaise} S.~Nicaise, \textit{Spectre des r\'{e}seaux topologiques finis},
    Bull. Sci. Math., II. S\'{e}r., \textbf{111} (1987), 401 -- 413.

\bibitem{Nicaise:2} S.~Nicaise, \textit{Le laplacien sur les r\'{e}saux
    deux-dimensionnels polygonaux topologiques}, J. Math. Pures Appl., IX. S\'{e}r.
    67 (1988), 93 -- 113.

\bibitem{Novaszek} M.~Nowaszyk, \textit{Inverse spectral problems for quantum graphs with rationally
    dependent edges}, in J.~Janas, P.~Kurasov, A.~Laptev, S.~Naboko, G.~Stolz
    (Eds.), \textit{Operator Theory, Analysis and Mathematical Physics}, Oper.
    Theory Adv. Appl. Vol.~174, Birkh\"{a}user, Basel, 2007.

\bibitem{Okada} T.~Okada, \textit{Asymptotic behavior of skew conditional
    heat kernels on graph networks}, Can. J. Math. \textbf{45} (1993), 863 --
    878.

\bibitem{RS} D.~B.~Ray and I.~M.~Singer, \textit{$R$-Torsion and the Laplacian on
    Riemannian manifolds}, Adv. Math. \textbf{7} (1971), 145 -- 210.

\bibitem{Regge} T.~Regge, \textit{General relativity without coordinates}, Nuovo
    Cimento \textbf{19} (1961), 558 -- 571.

\bibitem{Roth:1} J.-P.~Roth, \textit{Spectre du laplacien sur un graphe},
    C. R. Acad. Sci. Paris, S\'{e}r. I Math. \textbf{296} (1983), 793 -- 795.

\bibitem{Roth:2} J.-P.~Roth, \textit{Le spectre du laplacien sur un graphe},
    in G.~Mokobodzki and D.~Pinchon (Eds.), \textit{Th\'{e}orie du potentiel},
    (Proceedings of the Colloque Jacques Deny, Orsay, June 20-23, 1983), Lecture
    Notes in Math., Vol.~1096, Springer, Berlin, 1984. pp.~521 -- 539.

\bibitem{Selberg} A.~Selberg, \textit{Harmonic analysis and
    discontinuous groups in weakly symmetric spaces with applications
    to Dirichlet series}, J. Indian Math. Soc. \textbf{20} (1956), 47
    -- 87.

\bibitem{Terras} A.~Terras and D.~Wallace, \textit{Selberg's trace formula on the $k$-regular
    tree and applications}, Int. J. Math. Math. Sci. 2003, 501 -- 526 (2003).

\bibitem{Winn} B.~Winn, \textit{On the trace formula for quantum star graphs}, in G.~Berkolaiko, R.~Carlson,
    S.~A.~Fulling, and P.~Kuchment (Eds.), \textit{Quantum Graphs and Their
    Applications}, Contemp. Math. Vol. 415, Amer. Math. Soc., Providence, RI,
    2006. p.~293 -- 307.

\bibitem{Yafaev} D.~R.~Yafaev, \textit{Mathematical Scattering Theory}, Amer. Math. Soc.,
    Providence, RI, 1992.

\end{thebibliography}

\end{document}
---------------0701041319454--
