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

This is a multi-part message in MIME format.

---------------0205270423219
Content-Type: text/plain; name="02-242.keywords"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="02-242.keywords"

supersymmetry; discrete Laplacian; infinite graph; line graph; subdivsion graph
---------------0205270423219
Content-Type: application/x-tex; name="submit2mparc.tex"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline; filename="submit2mparc.tex"

\listfiles
% \documentclass[jfan]{apjrnl}
%\documentclass[jfan,draft]{apjrnl}      %%% for submission
\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amsthm}
\def\eqnref#1{(\ref{#1})}

%%%%% Define theorem environments %%%%%%%%%%%%
{\theoremstyle{plain}%
  \newtheorem{Theorem}{Theorem}%
  \newtheorem{Proposition}[Theorem]{Proposition}%
  \newtheorem{Lemma}[Theorem]{Lemma}%
  \newtheorem{Corollary}[Theorem]{Corollary}%
}
{\theoremstyle{remark}
  \newtheorem{remark}[Theorem]{Remark}%
}
{\theoremstyle{definition}
  \newtheorem{Assumption}[Theorem]{Assumption}%
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

%%%%%% Custom macro definitions %%%%%%%%%%%%%%
\newcommand{\N}{{\bf N}}   % natural numbers
\newcommand{\HS}{{\cal H}} % Hilbert Space
\newcommand{\lap}[1]{\Delta_{#1}}               % laplacian on #1
\newcommand{\spec}[1]{\sigma\left(#1\right)}    % spectra of #1
\newcommand{\cv}[1]{\left(\begin{array}{c}#1\end{array}\right)} % column vector
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{Supersymmetric analysis of the spectral theory on infinite graphs}

\author{Osamu Ogurisu\\
  Department of Computational Science, Kanazawa University,\\
  Kakumamachi, Kanazawa, 920-1192, Japan\\
  E-mail: ogurisu@lagendra.s.kanazawa-u.ac.jp}

\date{27 May 2002} %please do not use \today, use actual date of version

\maketitle



\begin{abstract}  
  We present a new approach to the spectral theory on infinite graphs.
  We first show that Laplacians on infinite graphs can be treated in a
  framework of operator theory with supersymmetry.
  %
  Using this supersymmetric structure, we rederive in a simple way
  known results as in Ref.~[T.\ Shirai, Trans.\ Amer.\ Math.\ Soc.,
  \textbf{32} (1999), 115--132] and to obtain new results.
\end{abstract}



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

It is well known that Laplacians on graphs are related to various
topics in mathematics
(\cite{HS99:Spectrum,Tep98:Spectral,MW88:Survey,Exn97:duality} and
references therein).  Recently, many mathematicians are intensively
interested in the spectra of Laplacian on infinite graphs.  In 1999,
T.~Shirai~\cite{Shi99:Spectrum} obtained some exact relations between
the spectra of the Laplacians on infinite regular graphs and their
line graphs and similar relations for some other graphs, such as
semiregular graphs, subdivision graphs and para-line graphs.

In this paper, we present a new approach to the spectral theory on
infinite graphs.  We first show that Laplacians on infinite graphs can
be treated in a framework of operator theory with supersymmetry.
Using this supersymmetric structures, we rederive in a simple way
known results as in Ref.~\cite{Shi99:Spectrum} and to obtain new
results; we obtain an exact relation between the spectra of a graph
\(G\) and it's subdivision graph \(S(G)\).  Here, \(G\) is not
necessarily regular or semiregular.  Our approach can be applied to
finite graphs.

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

We start to summarize a framework of operator theory with
super\-symmetry\cite{Tha92:Dirac,Shi91:Spectral,CFKS87:Schroedinger,Ara87:remarks}.
Roughly speaking, supersymmetry is a powerful tool to investigate
spectral properties of Dirac operators.

Let \(\HS_1\) and \(\HS_2\) be a Hilbert spaces and \(m\) be a real
constant.  This constant \(m\) denotes the mass of a particle in a
context of physics.  We define an \emph{abstract Dirac operator} \(Q\)
on \(\HS_1\oplus \HS_2\) by
\begin{displaymath}
  Q = Q_0 + m\sigma^3,
\end{displaymath}
where 
\begin{displaymath}
  Q_0 = 
  \left(\begin{array}{cc}
    0 & A^* \\
    A & 0
  \end{array}\right)
\end{displaymath}
is a massless Dirac operator  with a densely defined closed linear
operator \(A\) from \(\HS_1\) to \(\HS_2\) and
\begin{displaymath}
  \sigma^3=
  \left(\begin{array}{cc}
    1 & 0\\
    0 & -1
  \end{array}\right).
\end{displaymath}

The quadruple \(\langle H,Q,\Gamma,\HS\rangle\) is referred as
\emph{supersymmetric} (\emph{SUSY}) structure.  Here, \(\HS\) is a
Hilbert space, \(H\), \(Q\) and \(\Gamma\) are selfadjoint operators
on \(\HS\) such that \(H=Q^2\), \(\Gamma^2=1\), \(\Gamma\ne 1\) and
\(\Gamma{Q}+Q\Gamma=0\).  This \(H\) is called a \emph{SUSY
  Hamiltonian} and \(Q\) is called a \emph{supercharge}.  Note that
for a massless Dirac operator \(Q_0\) the quadruple
\begin{math}
  \langle Q_0^2, Q_0, \sigma^3, \HS_1\oplus{}\HS_2\rangle
\end{math}
is SUSY.

The following lemma is an important conclusion of supersymmetry.
\begin{Lemma}[Proposition~2.5 in \cite{Shi91:Spectral}]
  \label{lem:shigekawa}
  We have that
  \begin{displaymath}
    \spec{Q^2}\setminus\{m^2\} 
    = \spec{A^*A+m^2}\setminus\{m^2\}
    = \spec{AA^*+m^2}\setminus\{m^2\},
  \end{displaymath}
  \begin{displaymath}
    \spec{Q}\setminus\{\pm m\}
    = \sqrt{\spec{A^*A+m^2}\setminus\{m^2\}}\cup -\sqrt{\spec{AA^*+m^2}\setminus\{m^2\}}.
  \end{displaymath}
  Moreover, \(m\in\spec{Q}\) if and only if \(0\in\spec{A}\) and
  \(-m\in\spec{Q}\) if and only if \(0\in\spec{A^*}\) taking account of
  multiplicity.
\end{Lemma}

We remark that 
\begin{displaymath}
  \spec{Q}\setminus\{\pm m\} = \spec{-Q}\setminus\{\pm m\}.
\end{displaymath}

For later use we prepare a corollary of Lemma~\ref{lem:shigekawa}.
\begin{Corollary}
  \label{cor:shigekawa}
  We have that
  \begin{displaymath}
    \spec{Q}\setminus\{\pm m\}
    = 
    \sqrt{\spec{Q_0}\setminus\{0\})^2+m^2}
    \cup-\sqrt{\spec{Q_0}\setminus\{0\})^2+m^2}.
  \end{displaymath}
\end{Corollary}

\begin{proof}
  By Lemma~\ref{lem:shigekawa}, we have
  \begin{displaymath}
    \spec{Q_0}\setminus\{0\}
    = \sqrt{\spec{A^*A}\setminus\{0\}}\cup -\sqrt{\spec{A^*A}\setminus\{0\}}.
  \end{displaymath}
  Thus,
  \begin{displaymath}
    \spec{A^*A}\setminus\{0\}
    = (\spec{Q_0}\setminus\{0\})^2
    = \spec{Q_0}^2\setminus\{0\}.
  \end{displaymath}
  Therefore,
  \begin{displaymath}
    \spec{A^*A+m^2}\setminus\{m^2\}
    = \spec{Q_0}^2\setminus\{0\}+m^2.
  \end{displaymath}
  Similarly,
  \begin{displaymath}
    \spec{AA^*+m^2}\setminus\{m^2\}
    = \spec{Q_0}^2\setminus\{0\}+m^2.
  \end{displaymath}
  Consequently, we obtain the desired result.
\end{proof}

In the rest of this section, we prepare some definitions and
notations.  A graph \(G\) is a pair \((V(G),E(G))\) of a set \(V(G)\)
and a set \(E(G)\) of unordered pairs \(xy\) of two distinct points
\(x\), \(y\) of \(V(G)\).  The sets \(V(G)\) and \(E(G)\) are called
the vertex set and the edge set of \(G\), respectively.  We define a
neighborhood set of a vertex \(x\) by
\begin{displaymath}
  N_x = \{y\in V(G); xy\in E(G)\}.
\end{displaymath}
The degree of a vertex \(x\) is the cardinality of \(N_x\) and is
denoted by \(m(x)\).  Through this paper, we assume that an infinite
graph \(G\) is simple, connected and locally finite, that is, \(G\)
has no loops and no multiple edges, \(G\) has a path from \(x\) to
\(y\) for arbitrary two distinct vertices \(x\), \(y\in V(G)\) and
\(m(x)<\infty\) for all \(x\in V(G)\).

Let \(G\) be a graph.  Inserting an additional vertex \((x,y)\) into
each edge \(xy\in E(G)\), we define the \emph{subdivision graph}
\(S(G)\) of a graph \(G\):
\begin{eqnarray*}
  && V(S(G)) = V(G)\cup\{(x,y);\, xy\in E(G)\},\\
  && E(S(G)) = \{x(x,y), (x,y)y;\, xy\in E(G)\}.
\end{eqnarray*}

The \emph{line graph} \(L(G)\) of \(G\) is defined as follows:
\begin{eqnarray*}
  && V(L(G)) = E(G),\\
  && E(L(G)) = \{(xy)(yz);\, xy, yz\in E(G), x\ne z\}.
\end{eqnarray*}

A graph \(G\) is called \emph{\(d\)-regular} if \(m(x)=d\) for all
\(x\in{}V(G)\).  A graph \(G\) is called a \emph{bipartite graph} if
\(G\) has no cycles of odd length; the vertex set \(V(G)\) can be
partitioned into two sets \(V_1\) and \(V_2\) in such a way that every
edge in \(E(G)\) connects a vertex in \(V_1\) and a vertex in \(V_2\).
A bipartite graph \(G\) with a bipartition \(\{V_i\}_{i=1,2}\) is
called a \emph{\((d_1,d_2)\)-semiregular graph} if the degree of each
vertex in \(V_i\) is the constant \(d_i\) for \(i=1,2\).  

We denote by \(l^2(G)\) an \(l^2\)-space of functions on \(V(G)\) with
the inner product defined by
\begin{displaymath}
  \langle f,g\rangle_G = \sum_{x\in V(G)}m(x)f(x)g(x).
\end{displaymath}
Now we define a discrete Laplacian which acts on \(l^2(G)\) as
follows:
\begin{displaymath}
  \lap{G}f(x) = \frac{1}{m(x)}\sum_{y\in N_x}f(y) - f(x).
\end{displaymath}
We denote the spectrum of \(-\lap{G}\) by \(\spec{-\lap{G}}\).  

Let \(p\) be a positive constant.  We denote by \(l^2(G)_p\) the
\(l^2\)-space of functions on \(V(G)\) with the inner product given by
\begin{displaymath}
  \langle f,g\rangle_p = p\sum_{x\in V(G)}f(x)g(x).
\end{displaymath}
This symbol \(l^2(G)_p\) is not used in Ref.~\cite{Shi99:Spectrum}.

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

The plan of this paper is as follows.  %
In Section~\ref{sec:subdivision}, we prove that the Laplacian
\(\lap{S(G)}\) is a Dirac operator (a supercharge) and there exists a
SUSY structure with the SUSY Hamiltonian,
\begin{math}
  H=(\lap{S(G)}+1)^2
\end{math}.
With the aid of Lemma~\ref{lem:shigekawa}, we obtain an exact relation
between the spectra of \(\lap{G}\) and \(\lap{S(G)}\).
%%%
In Sections~\ref{sec:regular} and~\ref{sec:semi}, we examine the
relation among \(\lap{G}\), \(\lap{L(G)}\) and \(\lap{S(G)}\).  In
Sections~\ref{sec:regular} we consider the case when \(G\) is a
regular graph and in Section~\ref{sec:semi} we do the case when \(G\)
is a semi-regular graph.  We prove the existence of SUSY structures
and we obtain an exact relation between the spectra of \(\lap{G}\) and
\(\lap{L(G)}\) with the aid of Lemma~\ref{lem:shigekawa}, again.

We remark that we do not treat a para-line graph~\cite{Shi99:Spectrum}
in this paper, since a para-line graph of a graph \(G\) can be regarded
as the line graph of the subdivision graph of \(G\).






\section{Subdivision graphs of infinite graphs}
\label{sec:subdivision}

In this section, we consider a subdivision graph \(S(G)\) of a graph
\(G\).  We do not assume that \(G\) is regular or semiregular.  We
prove that the Laplacian \(\lap{S(G)}\) is a Dirac operator (a
supercharge) and there exists a SUSY structure with the SUSY
Hamiltonian,
\begin{math}
  H=(\lap{S(G)}+1)^2
\end{math}.
Moreover, we prove that
\begin{math}
  H\lfloor_{l^2(G)}=(\lap{G}+1)/2
\end{math}.
As a corollary of the above results, we obtain an exact relation
between the spectra of \(\lap{G}\) and \(\lap{S(G)}\).

We note that since \(V(S(G))\) is a direct sum of \(V(G)\) and
\(V(L(G))\), we can regard
\begin{math}
  l^2(S(G))=l^2(G)\oplus{}l^2(L(G))_2
\end{math}.

We define a operator \(\phi\) from \(l^2(G)\) to \(l^2(L(G))_2\) by
\begin{displaymath}
  \phi f(xy)=\frac{1}{2}(f(x)+f(y))
\end{displaymath}
for \(xy\in V(L(G))\).  Then, the adjoint operator \(\phi^*\) of
\(\phi\) is 
\begin{displaymath}
  \phi^*F(x) = \frac{1}{m(x)}\sum_{r\in N_x}F(xr).
\end{displaymath}

\begin{Theorem}
  \label{thm:subdivision}
  We have the following matrix representation of \(\lap{S(G)}+1\)  on
  \(\HS = l^2(G)\oplus{}l^2(L(G))_2\):
  \begin{displaymath}
    Q := 
    \lap{S(G)}+1 =
    \left(\begin{array}{cc}
        0 & \phi^*\\
        \phi & 0
      \end{array}\right).
  \end{displaymath}
  Moreover, we have that
  \begin{displaymath}
    H :=
    (\lap{S(G)}+1)^2 =
    \left(\begin{array}{cc}
      \frac{1}{2}(\lap{G}+2) & 0\\
      0                      & \phi\phi^*
    \end{array}\right),
  \end{displaymath}
  and thus, the quadruple
  \begin{math}
    \langle H, Q, \Gamma, \HS\rangle
  \end{math}
  is SUSY, where
  \begin{math}
    \Gamma=
    \left(\begin{array}{cc}
      1 & 0\\
      0 & -1
    \end{array}\right).
  \end{math}
\end{Theorem}

\begin{proof}
  For \(f\in l^2(G)\subset\HS\), since \(m(xy)=2\) for all
  \(xy\in{}V(L(G))\), we have
  \begin{displaymath}
    \left(\lap{S(G)}+1\right)f(xy)
    = \frac{1}{2}(f(x)+f(y))
    = \phi f(xy).
  \end{displaymath}
  For \(F\in l^2(L(G))_2\), we have
  \begin{displaymath}
    \left(\lap{S(G)}+1\right)F(x)
    = \frac{1}{m(x)}\sum_{r\in N_x}F(xr)
    = \phi^*F(x).
  \end{displaymath}
  Thus, we obtain the first half of this theorem.  Since
  \begin{eqnarray*}
    \phi^*\phi f(x) 
    & = & \frac{1}{m(x)}\sum_{r\in N_x}\phi f(xr)\\
    & = & \frac{1}{m(x)}\sum_{r\in N_x}\frac{1}{2}(f(x)+f(r))\\
    & = & \frac{1}{2}\left(f(x)+\frac{1}{m(x)}\sum_{r\in N_x}f(r)\right)\\
    & = & \frac{1}{2}(\lap{G}+2)f(x),
  \end{eqnarray*}
  we obtain the second half.
\end{proof}

Next, we examine the relation between the spectra of \(\lap{G}\) and
\(\lap{S(G)}\).  To prove the following corollary, we use
Assumption~\ref{as:assumption}, Propositions~\ref{prop:ker-phi}
and~\ref{prop:ker-adj}, which are stated later.  Here, we need this
assumption and these propositions to examine whether 1 is an
eigenvalue of \(-\lap{S(G)}\) or not.

\begin{Corollary}
  \label{cor:sub}
  Under Assumption~\ref{as:assumption}, we have that
  \begin{displaymath}
    \spec{-\lap{S(G)}}
    =
    f_+(\spec{-\lap{G}})\cup\{1\}\cup f_-(\spec{-\lap{G}}),
  \end{displaymath}
  where \(f_\pm(x)=1\pm\sqrt{1-x/2}\) and 1 is an eigenvalue of
  \(-\lap{S(G)}\) with infinite multiplicity.
\end{Corollary}

\begin{proof}
  By Lemma~\ref{lem:shigekawa} and the following remark, we have
  \begin{displaymath}
    \spec{-\lap{S(G)}-1}\setminus\{0\}
    =
    \sqrt{\spec{\phi^*\phi}\setminus\{0\}}
    \cup
    -\sqrt{\spec{\phi^*\phi}\setminus\{0\}}.
  \end{displaymath}
  By Theorem~\ref{thm:subdivision}, we have
  \begin{displaymath}
    -\phi^*\phi = -\frac{1}{2}(\lap{G}+2).    
  \end{displaymath}
  Consequently, using spectral mapping theorem, we can obtain the
  desired result up to \(\{1\}\).   By Lemma~\ref{lem:shigekawa},  the
  eigenvalue 1 of \(-\lap{S(G)}\) is corresponding to the eigenvalues
  0 of \(-\phi\phi^*\) and \(-\phi^*\phi\), and by
  Proposition~\ref{prop:ker-adj} we have \(\dim\ker\phi^*=\infty\).
  Thus, 1 is an eigenvalue of \(-\lap{S(G)}\) with infinite
  multiplicity.
\end{proof}

In the rest of this section we state Assumption~\ref{as:assumption}
and prove the Propositions~\ref{prop:ker-phi} and \ref{prop:ker-adj}.

\begin{Proposition}
  \label{prop:ker-phi}
  We have that \(\ker\phi=\{0\}\).
\end{Proposition}

\begin{proof}
  Since \(G\) is a infinite graph, for arbitrary \(x_1\in V(G)\),
  there exists at least one infinite path \(x_1x_2x_3\cdots\) in \(G\)
  such that \(x_i\ne x_j\) if \(i\ne{}j\).  Let \(f\in l^2(G)\).
  Assume that \(\phi f=0\).  Then, we have that
  \(f(x_i)+f(x_{i+1})=0\) for all \(i\).  Thus, if \(f(x_0)\ne 0\),
  \(f\) can not be in \(l^2(G)\).  Therefore, \(\ker\phi=\{0\}\).
\end{proof}

Let \(\gamma=x_0x_1\cdots x_{2n-1}\) be an even closed path in \(G\)
with \(x_{2n}=x_0\) and \(\delta_{xy}(zw)\) be the indicate function
on \(L(G)\).  We define a function \(F_\gamma\) on \(L(G)\) by
\begin{displaymath}
  F_\gamma(xy) = \sum_{k=0}^{2n-1}(-1)^k\delta_{x_kx_{k+1}}(xy).
\end{displaymath}
Then, we have that \(F_\gamma\in l^2(L(G))_2\) and
\(\phi^*F_\gamma=0\).  We call \(F_\gamma\) by a \emph{even closed
  walk} if \(F_\gamma\ne 0\).  We call a path \(\gamma\) by a
\emph{proper cycle} if the path \(\gamma=x_0x_1\cdots{}x_{n-1}\)
satisfies that \(x_n=x_0\) and \(x_i\ne{}x_j\) if \(i\ne j\).  We
denote by \(|\gamma|\) the length of a path \(\gamma\).

\begin{Assumption}
  \label{as:assumption}
  We assume that a graph \(G\) satisfies one of the followings:
  \begin{enumerate}
  \item  The graph \(G\) has infinitely many proper cycles.
  \item  There exists a subtree \(H\) of \(G\) such that
    \begin{math}
      2\le m(x)\le 3
    \end{math}
    holds for all \(x\in V(H)\) and the lengths of paths in \(H\)
    consisting vertices with the degree \(2\) are bounded.
  \end{enumerate}
\end{Assumption}

We prove the following proposition in a similar way as in the proof of
Proposition~2.7 in Ref.~\cite{Shi99:Spectrum}.
\begin{Proposition}
  \label{prop:ker-adj}
  Under Assumption~\ref{as:assumption}, we have that
  \(\dim\ker\phi^*=\infty\).
\end{Proposition}

\begin{proof}
  For simplicity, we first treat the case when \(m(x)\ge 3\) for all
  \(x\in V(G)\).
  
  We consider the case when \(G\) is a tree and take a subtree \(H\)
  as the second part of Assumption~\ref{as:assumption}.  This \(H\) is
  a \(3\)-regular tree.
  %%
  Choose one vertex in \(H\) as \(x_0\).
  Write the two adjacency vertices of \(x_0\) as \(x_\pm\), %
  and then %
  do the two adjacency vertices of \(x_+\) except \(x_0\) as \(x_{+\pm}\), %
  and the two adjacency vertices of \(x_-\) except \(x_0\) as \(x_{-\pm}\). %
  Next we write two adjacency vertices  of \(x_{++}\) except \(x_+\)
  as \(x_{++\pm}\) and so on.
  %%
  We define a function \(F_0\) on \(L(G)\) inductively as follows:
  \begin{eqnarray*}
    F_0(xy) & = & 0 \quad \mbox{if \(x\not\in V(H)\) or \(y\not\in V(H)\)},\\
    F_0(x_0x_{\pm}) & = & 0,\\
    F_0(x_{\pm}x_{\pm +}) & = & +1,\\
    F_0(x_{\pm}x_{\pm -}) & = & -1,\\
    F_0(x_{\gamma\pm}x_{\gamma\pm\pm}) & = & -\frac{1}{2}F_0(x_{\gamma}x_{\gamma\pm}),
  \end{eqnarray*}
  where \(\gamma\) is an arbitrary finite sequence of some \(+\)'s and
  \(-\)'s.  Then, \(F_0\in l^2(L(G))_2\).  Indeed,
  \begin{eqnarray*}
    \|F_0\|_{l^2(L(G))_2}^2
    & = & 2\sum_{xy\in V(L(G))}F_0(xy)^2\\
    & = & 2\sum_{k=1}^\infty\sum_{|\gamma|=k}\{F_0(x_\gamma x_{\gamma+})^2+F_0(x_\gamma x_{\gamma-})^2\}\\
    & = & 4\sum_{k=1}^\infty\sum_{|\gamma|=k}\frac{1}{2^{2(k-1)}}\\
    & = & 4\sum_{k=1}^\infty\frac{2^k}{2^{2(k-1)}}\\
    &\le& \infty.
  \end{eqnarray*}
  Obviously,
  \begin{math}
    \sum_{r\in N_x}F_0(xr)=0
  \end{math},
  that is, \(\phi^*F_0=0\).  Similarly, by considering the vertex
  \(x_{+^n}\) in place \(x_0\),  we can define \(F_n\) for
  \(n\ge{}1\).  Here \(+^n\) is the sequence of \(n\) \(+\)'s.  By the
  definition of \(\{F_n;n\in\N\}\), they are linearly independent and
  \(\phi^*F_n=0\) for all \(n\in\N\). Thus \(\dim\ker\phi^*=\infty\).
  
  Finally, we consider the case when \(G\) has infinitely many proper
  cycles.  If \(G\) has infinitely many even proper cycles, \(G\) has
  trivially infinitely many even closed walks.  If \(G\) has a finite
  number of even proper cycles, \(G\) has infinitely many odd proper
  cycles. Then we can construct a even closed walk by connecting two
  odd proper cycles.  Thus \(G\) has infinitely many even closed
  walks, again.  In both cases, by the definition of walk, these walks
  are linearly independent. Therefore \(\dim\ker\phi^*=\infty\).
  
  In the case when there exist vertices with the degree \(2\).  We
  execute the same procedure to construct \(F_0\) as above, except the
  case when \(x_{\gamma+}\) (or \(x_{\gamma-}\)) is one of the
  vertices with the degree \(2\).  In this case, take  it's only one
  adjacency vertex  except \(x_\gamma\) as \(x_{\gamma+\alpha}\), and
  let
  \begin{displaymath}
    F_0(x_{\gamma+}x_{\gamma+\alpha}) = -F_0(x_{\gamma}x_{\gamma+}).
  \end{displaymath}
  Since the lengths of paths consisting vertices with the degree 2 are
  bounded, this \(F_0\) is in \(l^2(L(G))_2\), again.
\end{proof}

We remark that in the case when \(m(x)=2\) for all \(x\in V(G)\), we
can prove that \(\dim\ker\phi^*=0\) in a same way as in the proof of
Proposition~\ref{prop:ker-phi}. 





\section{Line graphs of regular graphs}
\label{sec:regular}

The rest of this paper, we examine the relation among the Laplacians
\(\lap{G}\), \(\lap{L(G)}\) and \(\lap{S(G)}\).  In this section we
consider the case when \(G\) is a regular graph and in the next
section we do the case when \(G\) is a semi-regular graph.

In this section, we prove that  there exists a SUSY structure with the
SUSY Hamiltonian,
\begin{math}
  H=(\lap{S(G)}+1)^2
\end{math} 
such that
\begin{math}
  H\lfloor_{l^2(G)}
\end{math} 
and
\begin{math}
  H\lfloor_{l^2(L(G))_2}
\end{math} 
are  functions of the first degree of \(\lap{G}\) and \(\lap{L(G)}\),
respectively.  As a corollary of the above results, we obtain an exact
relation between the spectra of \(\lap{G}\) and \(\lap{L(G)}\).

Through this section we assume that \(G\) is \(d\)-regular.   Then
\(L(G)\) is \((2d-2)\)-regular, and thus
\(l^2(L(G))=l^2(L(G))_{2d-2}\).   We define a unitary operator \(U\)
from \(l^2(L(G))\) to \(l^2(L(G))_2\) by
\begin{displaymath}
  Uf = \sqrt{d-1}\,f.
\end{displaymath}
Let \(\phi\) be a linear operator from \(l^2(G)\) to \(l^2(L(G))_2\)
defined by
\begin{displaymath}
  (\phi f)(xy) = \frac{1}{2}(f(x)+f(y)).
\end{displaymath}
Then, the adjoint operator \(\phi^*\) of \(\phi\) is
\begin{displaymath}
  (\phi^*F)(x) = \frac{1}{d}\sum_{r\in N_x}F(xr).
\end{displaymath}

\begin{remark}
  We remark on our notations.  In Ref.~\cite{Shi99:Spectrum}, the
  symbol \(\phi\) denotes both an operator from \(l^2(G)\) to
  \(l^2(L(G))\) and an operator from \(l^2(G)\) to \(l^2(L(G))_2\).
  In this paper, since we simultaneously need the both operators, we
  use the symbol \(\phi\) only as an operator from \(l^2(G)\) to
  \(l^2(L(G))_2\).  Similarly, we use the symbol \(\phi^*\) only as an
  operator from \(l^2(L(G))_2\) to \(l^2(G)\).
\end{remark}

The following is the main theorem in this section.

\begin{Theorem}
  \label{thm:SG}
  We have the following matrix representation of \(\lap{S(G)}+1\)  on
  \begin{math}
    \HS = l^2(S(G)) = l^2(G)\oplus{}l^2(L(G))_2
  \end{math}:
  \begin{equation}
    \label{eq:supercharge-SG}
    Q := \lap{S(G)} + 1 = 
    \left(\begin{array}{cc}
      0    & \phi^* \\
      \phi & 0
    \end{array}\right).
  \end{equation}
  Moreover, we have
  \begin{equation}
    \label{eq:susy-SG}
    H := (\lap{S(G)} + 1)^2 =
    \left(\begin{array}{cc}
      \frac{1}{2}(\lap{G}+2) & 0 \\
      0 & U\left[\frac{d-1}{d}\left(\lap{L(G)}+\frac{d}{d-1}\right)\right]U^*
    \end{array}\right).
  \end{equation}
  Thus, the quadruple
  \begin{math}
    \langle H, Q, \Gamma, \HS\rangle
  \end{math}
  is SUSY, where 
  \begin{math}
    \Gamma=
    \left(\begin{array}{cc}
      1 & 0\\
      0 & -1
    \end{array}\right).
  \end{math}
\end{Theorem}

\begin{proof}
  We obtain Eq.~\eqnref{eq:supercharge-SG}  and
  \begin{math}
    \phi^*\phi = \frac{1}{2}(\lap{G}+2)
  \end{math}
  in the same way as in the proof of Theorem~\ref{thm:subdivision}.
  By the same direct calculations as in the proof of Proposition~2.4
  in Ref.~\cite{Shi99:Spectrum}, we have
  \begin{equation}
    \label{eq:susy-reg-LGpart}
    U^*(\phi\phi^*)U = \frac{d-1}{d}\left(\lap{L(G)}+\frac{d}{d-1}\right).
  \end{equation}
  Therefore we obtain Eq.~\eqnref{eq:susy-SG}.
\end{proof}

We examine the relation between the spectra of \(\lap{G}\) and \(\lap{L(G)}\).

\begin{Proposition}
  \label{prop:ker-phi-reg}
  Let \(d\ge 3\).  Then, \(\dim\ker\phi=0\) and \(\dim\ker\phi^*=\infty\).
\end{Proposition}

\begin{proof}
  Since \(d\ge 3\), \(G\) satisfies Assumption~\ref{as:assumption}.
  Thus, we can prove this proposition in a same way as in the proofs
  of of Propositions~\ref{prop:ker-phi} and~\ref{prop:ker-adj} up to
  constant multiple factors of \(\phi\).
\end{proof}

\begin{Corollary}
  \label{Cor:SG}
  Let \(d\ge 3\).
  We have 
  \begin{equation}
    \label{eq:spec-G-LG-2}
    \spec{-\lap{L(G)}}
    =
    \frac{d}{2d-2}\spec{-\lap{G}}\cup\left\{\frac{d}{d-1}\right\}
  \end{equation}
  and \(d/(d-1)\) is an eigenvalue of \(-\lap{L(G)}\) with infinite
  multiplicity.  We have
  \begin{displaymath}
    \spec{-\lap{S(G)}}
    =
    f_{-}(\spec{-\lap{G}})
    \cup \{1\}
    \cup f_{+}(\spec{-\lap{G}}),
  \end{displaymath}
  where  \(f_{\pm}(x)=1\pm\sqrt{1-x/2}\).
\end{Corollary}

\begin{proof}
  By Lemma~\ref{lem:shigekawa} with Eq.~\eqnref{eq:susy-SG} of
  Theorem~\ref{thm:SG}, we can obtain
  \begin{displaymath}
    \spec{\frac{1}{2}(\lap{G}+2)}\setminus\{0\}
    =
    \spec{\frac{d-1}{d}\left(\lap{L(G)}+\frac{d}{d-1}\right)}\setminus\{0\}.
  \end{displaymath}
  Using spectral mapping theorem, we can obtain
  Eq.~\eqnref{eq:spec-G-LG-2} up to \(\{\frac{d}{d-1}\}\).  By
  Proposition~\ref{prop:ker-phi-reg},  Eq.~\eqnref{eq:susy-reg-LGpart}
  of Theorem~\ref{thm:SG} and spectral mapping theorem,
  \(\frac{d}{d-1}\) is an eigenvalue of \(-\lap{L(G)}\) with infinite
  multiplicity.  Therefore we obtain Eq.~\eqnref{eq:spec-G-LG-2}.  The
  second half of this theorem is an application of
  Corollary~\ref{cor:sub}.
\end{proof}



\section{Line graphs of semiregular graphs}
\label{sec:semi}

In this section, we examine the relation among the Laplacians
\(\lap{G}\), \(\lap{L(G)}\) and \(\lap{S(G)}\) in the case when \(G\)
is a semi-regular graph.  We prove that  \(\lap{G}\) is a Dirac
operator and there exists a SUSY structure with the SUSY Hamiltonian,
\begin{math}
  H=(\lap{S(G)}+1)^2
\end{math}.
Moreover, we prove that
\begin{math}
  H\lfloor_{l^2(G)}
\end{math}
and
\begin{math}
  H\lfloor_{l^2(L(G))_2}
\end{math} are 
functions of the first degree of \(\lap{G}\) and \(\lap{L(G)}\),
respectively.  As a corollary of the above results, we obtain an exact
relation between the spectra of \(\lap{G}\) and \(\lap{L(G)}\).

Through this section, we assume that \(G\) is a
\((d_1,d_2)\)-semiregular graph.  Then, \(L(G)\) is
\((d_1+d_2-2)\)-regular, and we denote
\begin{displaymath}
  D=d_1+d_2-2.   
\end{displaymath}
We remark that when \(d_1\ge d_2\ge 3\) or \(d_1>d_2\ge 2\), a
semi-regular graph satisfies Assumption~\ref{as:assumption}.

We regard \(l^2(G)\) as the direct sum \(l^2(V_1)\oplus{}l^2(V_2)\),
where \(l^2(V_i)\) is a \(l^2\)-space of functions on \(V_i\) with
inner product
\begin{displaymath}
  \langle f,g\rangle_i = d_i\sum_{x\in V_i}f(x)g(x).
\end{displaymath}

Let \(\psi\) be an operator from \(l^2(V_1)\) to \(l^2(V_2)\) defined by
\begin{displaymath}
  (\psi f)(y)  = \frac{1}{d_2}\sum_{x\in N_y}f(x)
\end{displaymath}
for all \(f\in l^2(V_1)\) and \(y\in V_2\).  Then, the adjoint
operator \(\psi^*\) of \(\psi\) is
\begin{displaymath}
  (\psi^*g)(x) = \frac{1}{d_1}\sum_{y\in N_x}g(y)
\end{displaymath}
for all \(g\in l^2(V_2)\) and \(x\in V_1\).  Since
\begin{math}
  \lap{G}f(x) = \frac{1}{m(x)}\sum_{y\in N_x}f(y)-f(x),
\end{math}
we can obtain the following lemma.
\begin{Lemma}
  \label{lem:lap-G-on-semireg}
  The Laplacian \(\lap{G}\) is a Dirac operator, \emph{i.e.}, we have
  the following matrix representation of \(\lap{G}+1\) on
  \(l^2(V_1)\oplus{}l^2(V_2)\):
  \begin{displaymath}
    \lap{G} + 1 = 
    \left(\begin{array}{cc}
      0 & \psi^* \\
      \psi & 0
    \end{array}\right).
  \end{displaymath}
\end{Lemma}

Using Lemma~\ref{lem:shigekawa} and spectral mapping theorem, we can
obtain Lemma~3.5 in Ref.~\cite{Shi99:Spectrum}, that is,
\(\spec{-\lap{G}}\) is symmetric with respect to 1.

Let \(\Psi\) be an operator from \(l^2(V_1)\oplus l^2(V_2)\) to
\(l^2(L(G))\) defined by
\begin{displaymath}
  \Psi\cv{f\\g}(xy) = \frac{1}{D}(\sqrt{d_1}\,f(x) + \sqrt{d_2}\,g(y))
\end{displaymath}
for \(x\in V_1\) and \(y\in V_2\).  
Then, the adjoint operator \(\Psi^*\) of \(\Psi\) is
\begin{displaymath}
  \Psi^*F = 
  \left(\begin{array}{cc}
      \frac{1}{\sqrt{d_1}} \sum_{r\in N_x} F(xr) \\
      \frac{1}{\sqrt{d_2}} \sum_{s\in N_y} F(sy) 
  \end{array}\right).
\end{displaymath}
For simplicity, for \(F\in l^2(V_1)\oplus l^2(V_2)\), we denote by
\(F(x)\) with \(x\in V_i\) the \(l^2(V_i)\)-component of \(F\) for
each \(i=1,2\).

The following is the main theorem in this section.
\begin{Theorem}
  \label{thm:susy-semiregular}
  Let 
  \begin{displaymath}
    Q =
    \left(\begin{array}{cc}
      0      & \Psi^*\\
      \Psi & 0
    \end{array}\right)
  \end{displaymath}
  on
  \begin{math}
    \HS = l^2(G)\oplus{}l^2(L(G)) = (l^2(V_1)\oplus{}l^2(V_2))\oplus{}l^2(L(G))
  \end{math}.
  Then, we have
  \begin{displaymath}
    H = Q^2=
    \left(\begin{array}{cc}
      \frac{\sqrt{d_1d_2}}{D}(\lap{G}+1+\mu\Gamma+\nu) & 0 \\
      0 & \lap{L(G)}+\frac{d_1+d_2}{D} 
    \end{array}\right),
  \end{displaymath}
  where 
  \begin{displaymath}
    \mu = \frac{d_1-d_2}{2\sqrt{d_1d_2}},
    \quad
    \nu = \frac{d_1+d_2}{2\sqrt{d_1d_2}},
    \quad
    \Gamma=
    \left(\begin{array}{cc}
      I_{l^2(V_1)} &  0\\
      0 & -I_{l^2(V_2)}
    \end{array}\right).
  \end{displaymath}
  Thus, the quadruple
  \begin{math}
    \langle H, Q, \Gamma_\HS, \HS\rangle
  \end{math}
  is SUSY, where 
  \begin{displaymath}
    \Gamma_\HS=
    \left(\begin{array}{cc}
      I_{l^2(G)} & 0\\
      0 & -I_{l^2(L(G))} 
    \end{array}\right).
  \end{displaymath}
\end{Theorem}

\begin{proof}
  Let \(x\in V_1\) and \(y\in V_2\). We have
  \begin{eqnarray*}
    (\Psi\Psi^*F)(xy) 
    & = & \frac{1}{D}\left(\sqrt{d_1}\Psi^*F(x)+\sqrt{d_1}\Psi^*F(y)\right) \\
    & = & \frac{1}{D}\left(\sum_{r\in N_x}F(xr)+\sum_{s\in N_y}F(sy)\right)\\
    & = & \frac{1}{D}\left(\sum_{sr\in N_{xy}}F(sr)+2F(xy)\right)\\
    & = & \left(\lap{L(G)}+\frac{d_1+d_2}{D}\right)F(xy).
  \end{eqnarray*}
  Thus, we obtain the element of the right-down corner of \(Q^2\).

  Let \(x\in V_1\).  We have
  \begin{eqnarray*}
    \Psi^*\Psi\cv{f\\g}(x) 
    & = & \frac{1}{\sqrt{d_1}}\sum_{r\in N_x}\Psi\cv{f\\g}(xr)\\
    & = & \frac{1}{\sqrt{d_1}}\sum_{r\in N_x}\frac{1}{D}\left(\sqrt{d_1}\,f(x)+\sqrt{d_2}\,g(r)\right)\\
    & = & \frac{1}{D}\left(d_1f(x)+\sqrt{d_1d_2}\,\frac{1}{d_1}\sum_{r\in N_x}g(r)\right)\\
    & = & \frac{1}{D}\left(d_1f(x)+\sqrt{d_1d_2}(\psi^*g)(x)\right)\\
    & = & \frac{\sqrt{d_1d_2}}{D}\left((\mu+\nu)f(x)+(\psi^*g)(x)\right).
  \end{eqnarray*}
  Let \(y\in V_2\).  Similarly, we have
  \begin{displaymath}
    \Psi^*\Psi\cv{f\\g}(y) 
    = \frac{\sqrt{d_1d_2}}{D}\left((\psi f)(y)+(-\mu+\nu)g(y)\right).
  \end{displaymath}
  Thus, with the aid of  Lemma~\ref{lem:lap-G-on-semireg},  we have
  \begin{displaymath}
    \Psi^*\Psi
    =
    \frac{\sqrt{d_1d_2}}{D}
    \left(\begin{array}{cc}
      \mu+\nu  & \psi^*\\
      \psi     & -\mu+\nu 
    \end{array}\right)
    =
    \frac{\sqrt{d_1d_2}}{D}
    \left(\lap{G}+1+\mu\Gamma+\nu\right).
  \end{displaymath}
  Consequently, we obtain the desired result.
\end{proof}

In the rest of this paper, we examine the relation between the spectra
of \(\lap{G}\) and \(\lap{L(G)}\).  We can prove the following
proposition in a similar way as in the proofs of
Propositions~\ref{prop:ker-phi} and \ref{prop:ker-adj}.
\begin{Proposition}
  \label{prop:ker-Psi}
  (1) We have that \(\ker\Psi=\{0\}\).  (2) Let \(d_1\ge d_2\ge 3\) or
  \(d_1>d_2=2\).  We have that \(\dim\ker\Psi^*=\infty\).
\end{Proposition}

\begin{Corollary}
  Let \(d_1\ge d_2\ge 3\) or \(d_1>d_2=2\).  We define
  \begin{displaymath}
    f_{\pm}(x)=\frac{d_1+d_2\pm\sqrt{(d_1-d_2)^2+4d_1d_2(1-x)^2}}{2D}
  \end{displaymath}
  and
  \begin{math}
    \spec{-\lap{G}}^* = \overline{\spec{-\lap{G}}^*\setminus\{1\}}
  \end{math}.
  Then
  \begin{displaymath}
    \spec{-\lap{L(G)}}
    = 
    f_-(\spec{-\lap{G}}^*)
    \cup S 
    \cup f_+(\spec{-\lap{G}}^*)
    \cup \left\{\frac{d_1+d_2}{D}\right\},
  \end{displaymath}
  where 
  \begin{math}
    S\subset \{f_\pm(1)\} = \{d_1/D, d_2/D\}
  \end{math}
  and \((d_1+d_2)/D\) is an eigenvalue with infinite multiplicity.
  Furthermore, when \(d_1\ne d_2\), \(d_1/D\in S\) (resp.\ \(d_2/D\in
  S\)) if and only if \(1\in\spec{-\lap{G}\lfloor_{l^2(V_2)}}\)
  (resp.\ \(1\in\spec{-\lap{G}\lfloor_{l^2(V_1)}}\)).  When
  \(d_1=d_2=d\), \(S=\{d/D\}\) if and only if \(1\in\spec{-\lap{G}}\).
\end{Corollary}

\begin{proof}
  By Theorem~\ref{thm:susy-semiregular} and Lemma~\ref{lem:shigekawa},
  we have
  \begin{displaymath}
    \spec{\lap{L(G)}+\frac{d_1+d_2}{D}}\setminus\{0\}
    =
    \spec{\frac{\sqrt{d_1d_2}}{D}(\lap{G}+1+\mu\Gamma+\nu)}\setminus\{0\}.
  \end{displaymath}
  By Proposition~\ref{prop:ker-Psi}, 0 is an eigenvalue of
  \begin{math}
    -\Psi\Psi^* = -\lap{L(G)}-(d_1+d_2)/D
  \end{math}
  with infinite multiplicity, thus,
  \((d_1+d_2)/D\) is an eigenvalue of \(-\lap{L(G)}\) with infinite
  multiplicity.
  
  On the other hand, since
  \begin{displaymath}
    \lap{G}+1+\mu\Gamma
    =
    \left(\begin{array}{cc}
      \mu  & \psi^*\\
      \psi & -\mu
    \end{array}\right),
  \end{displaymath}
  using Corollary~\ref{cor:shigekawa}, we obtain that
  \begin{eqnarray*}
    &&\spec{-\lap{G}-1-\mu\Gamma}\setminus\{\pm\mu\}\\
    &&
    \quad=
    \sqrt{(1-\spec{-\lap{G}}\setminus\{1\})^2+\mu^2}
    \cup
    -\sqrt{(1-\spec{-\lap{G}}\setminus\{1\})^2+\mu^2}.
  \end{eqnarray*}
  Moreover, we have that
  \begin{math}
    \mu\mbox{ (resp. \(-\mu\)) }\in\spec{-\lap{G}-1-\mu\Gamma}
  \end{math}
  if and only if \(0\in\spec{\psi}\) (resp.\ \(1\in\spec{\psi^*}\)),
  \emph{i.e.}, if and only if
  \(1\in\spec{-\lap{G}\lfloor_{l^2(V_2)}}\) (resp.\
  \(1\in\spec{-\lap{G}\lfloor_{l^2(V_1)}}\)).  Consequently, with the
  aid of spectral mapping theorem, we obtain the desired results.
\end{proof}


\section*{Acknowledgements}
  The author would like to thank Professor Asao Arai for helpful
  discussions and encouragements. %
  This work was supported by the Grant-In-Aid 12740103 for
  Encouragement of Young Scientists from Japan Society for the
  Promotion of Science (JSPS).


\begin{thebibliography}{1}

\bibitem{HS99:Spectrum}
Yousuke Higuchi and Tomoyuki Shirai.
\newblock The spectrum of magnetic schr{\"o}dinger operators on a graph with
  periodic structure.
\newblock {\em J. Funct. Anal.}, 169:456--480, 1999.

\bibitem{Tep98:Spectral}
Alexander Teplyaev.
\newblock Spectral analysis on infinite {S}ierpi{\'n}ski gaskets.
\newblock {\em J. Funct. Anal.}, 159:537--567, 1998.

\bibitem{MW88:Survey}
Bojan Mohar and Wolfgang Woess.
\newblock A survey on spectra of infinite graphs.
\newblock {\em Bull. London Math. Soc.}, 21:209--234, 1989.

\bibitem{Exn97:duality}
Pavel Exner.
\newblock A duality between schr{\"o}dinger operators on graphs and certain
  jacobi matrices.
\newblock {\em Ann. Inst. H. Poincar{\'e}}, 66(4):359--371, 1997.

\bibitem{Shi99:Spectrum}
Tomoyuki Shirai.
\newblock The spectrum of infinite regular line graphs.
\newblock {\em Trans. Amer. Math. Soc.}, 32(1):115--132, 1999.

\bibitem{Tha92:Dirac}
Bernd Thaller.
\newblock {\em The {D}irac {E}quation}.
\newblock Texts and Monographs in Physics. Springer, Berlin, 1992.

\bibitem{Shi91:Spectral}
Ichiro Shigekawa.
\newblock Spectral properties of {S}chr{\"o}dinger operators with magnetic
  fields for a spin 1/2 particle.
\newblock {\em J. Funct. Anal.}, 101:255--285, 1991.

\bibitem{CFKS87:Schroedinger}
H.~L. Cycon, R.~G. Froese, W.~Kirsch, and B.~Simon.
\newblock {\em Schr{\"o}dinger operators with {A}pplication to {Q}uantum
  {M}echanics and {G}lobal {G}eometry}.
\newblock Texts and Monographs in Physics. Springer-Verlag, 1987.

\bibitem{Ara87:remarks}
Asao Arai.
\newblock Some remarks on scattering theory in supersymmetric quantum systems.
\newblock {\em J. Math. Phys.}, 28(2):472--476, 1987.

\end{thebibliography}
\end{document}
---------------0205270423219--
