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--