\documentclass[reqno]{amsart}

\AtBeginDocument{{\noindent\small
{\em Electronic Journal of Differential Equations},
Vol. 2005(2005), No. 93, pp. 1--11.\newline
ISSN: 1072-6691. URL: http://ejde.math.txstate.edu or http://ejde.math.unt.edu
\newline ftp ejde.math.txstate.edu  (login: ftp)}
\thanks{\copyright 2005 Texas State University - San Marcos.}
\vspace{9mm}}

\begin{document}
\title[\hfilneg EJDE-2005/93\hfil Dirichlet-Neumann bracketing]
{Dirichlet-Neumann bracketing for  boundary-value problems on
graphs}
\author[S. Currie, B. A. Watson \hfil EJDE-2005/93\hfilneg]
{Sonja Currie, Bruce A. Watson}  % in alphabetical order

\address{Sonja Currie \hfill\break
School of Mathematics\\
University of the Witwatersrand\\
Private Bag 3\\
P O WITS 2050, South Africa}
\email{scurrie@ananzi.co.za}

\address{Bruce A. Watson \hfill\break
School of Mathematics\\
University of the Witwatersrand\\
Private Bag 3\\
P O WITS 2050, South Africa}
\email{bwatson@maths.wits.ac.za}

\date{}
\thanks{Submitted March 9, 2005. Published August 24, 2005.}
\thanks{S. Currie was  supported by the National Research Foundation.
B. A. Watson \hfill\break\indent
was supported by the Centre for Applicable Analysis and
 Number Theory.}
\subjclass[2000]{47E05, 34L20, 34B45}
\keywords{Differential operators; spectrum; graphs}

\begin{abstract}
 We consider the spectral structure of second order boundary-value
 problems on graphs. A variational formulation for boundary-value
 problems on graphs is given. As a consequence we can formulate an
 analogue of Dirichlet-Neumann bracketing for boundary-value
 problems on graphs. This in turn gives rise to eigenvalue and
 eigenfunction asymptotic approximations.
\end{abstract}

\maketitle
\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}

\section{Introduction}

Let $G$ be an oriented graph with finitely many edges, each of finite length.
We consider the second-order differential equation
\begin{equation}\label{diff}
ly:=-\frac{d^2y}{dx^2} + q(x)y = \lambda y, %\label{l}
\end{equation}
on $G$, where $q$ is real valued and essentially bounded on $G$.
At the vertices or nodes of $G$ we impose
formally self-adjoint boundary conditions, see \cite{carlson} for more
details regarding the self-adjointness of boundary conditions.

We give a variational formulation for a class of self-adjoint boundary-value problems on graphs, Lemma \ref{regu},
and hence a max-min principle for Sturm-Liouville boundary-value problems on directed graphs, Theorem \ref{mm}.
In turn, this enables us to develop one of our two main results, an analogue of
Dirchlet-Neumann bracketing for the eigenvalues of the boundary-value problem,
in Corollary \ref{bracket}.
Corollary \ref{bracket} forms a theoretical structure for our second main result, Theorem \ref{As},
in which spectral asymptotics are found.
In amongst the above noted results we show the differential operator associated with the boundary-value problem to
be lower semibounded, see Theorem \ref{semibdd}.

It should be noted that,
a self-adjoint boundary-value problem on a graph is not necessarily regular
in the sense of \cite{Locker} and \cite{Naimark}.
For the case of regular boundary conditions many of the results in this paper are well known.
In fact many of the more important
classes of boundary conditions for boundary-value problems on graphs fail to meet these regularity
conditions, for example ``Kirchhoff'' boundary conditions.

In parallel to the variational aspects of
boundary-value problems on graphs studied here and on trees
in \cite{solomyak}, the work of Pokornyi and Pryadiev, and
Pokornyi, Pryadiev and Al-Obeid, in \cite{p-p} and \cite{p-p-a}, should be
noted for the extension of Sturmian oscillation theory to
second order operators on graphs.
The idea of approximating the behaviour of eigenfunctions and
eigenvalues for a boundary-value problem
on a graph by the behaviour of associated problems on the individual edges, used here, appeared
previously in \cite{vB}.

An extensive survey of the physical systems giving rise to boundary-value problems on graphs
can be found in \cite{kuchment} and the bibliography thereof.
Second order boundary-value problems on finite graphs arise naturally in quantum
mechanics and circuit theory, \cite{Avron, Ger}.
Multi-point boundary-value problems and periodic boundary-value problems
can be considered as particular cases of boundary-value problems
on graphs, \cite{codding}.

In Section \ref{sec2} the boundary-value problem,
which forms the topic of this paper, is stated and
allowable boundary conditions discussed.
An operator formulation is given along with definitions of
the various function spaces used in the paper.
Following this, we show the operator associated with the boundary-value problem to be lower
semibounded.

A variational reformulation of the boundary-value problem
is given in Section \ref{minimax}.
This leads to a max-min characterization of the eigenvalues
of the boundary-value problem and hence to a type of
Dirichlet-Neumann bracketing of the eigenvalues.
For the analogue in the case of partial differential equations we refer the reader to \cite{Cour}.

\section{Preliminaries} \label{sec2}

Let $G$ denote a directed graph with a finite number of edges, say $K$,
each of finite length and
having the path-length metric.
Each edge, $e_i$, of length say $l_i$ can thus be considered as
the interval $[0,l_i]$, where $0$ is identified with the initial point of
$e_i$ and $l_i$ with the terminal point.

The following classes of function spaces will be used in this paper, the first three of which are Hilbert spaces
when given Sobolev norms:
\begin{gather*}
 \mathcal{L}^2(G):= \bigoplus_{i=1}^K  \mathcal{L}^2(0,l_i),\\
 \mathcal{H}^m(G):= \bigoplus_{i=1}^K  \mathcal{H}^m(0,l_i),\quad m=0,1,2,\dots ,\\
 \mathcal{H}^m_o(G):= \bigoplus_{i=1}^K  \mathcal{H}^m_o(0,l_i),\quad m=0,1,2,\dots ,\\
 \mathcal{C}^\omega(G):= \bigoplus_{i=1}^K  \mathcal{C}^\omega(0,l_i),\quad \omega=\infty,0,1,2,\dots ,\\
 \mathcal{C}^\omega_o(G):= \bigoplus_{i=1}^K  \mathcal{C}^\omega_o(0,l_i),\quad \omega=\infty,0,1,2,\dots \ .
\end{gather*}
The inner product on $\mathcal{H}^m(G)$, denoted $(\cdot,\cdot)_m$,
is defined by
\begin{equation}\label{inner}
(f,g)_m
:=\sum_{i=1}^K \sum_{j=0}^m \int_0^{l_i} f|_{e_i}^{(j)}\ \bar{g}|_{e_i}^{(j)}\ dt
=:\sum_{j=0}^m \int_G f^{(j)}\ \overline{g}^{(j)}\ dt.
\end{equation}
The inner products on $\mathcal{L}^2(G)$ and $\mathcal{H}^m_o(G)$ follow from noting that
$\mathcal{L}^2(G)=\mathcal{H}^0(G)$ and $\mathcal{H}^m_o(G)\subset \mathcal{H}^m(G)$.
For brevity we will write $(\cdot,\cdot)=(\cdot,\cdot)_0$, $\|f\|_m^2=(f,f)_m$ and $\|f\|=\|f\|_0$.
Reasoning componentwise we obtain immediate analogues
of both Rellich's Theorem, \cite[page 114]{Wloka},
and the Sobolev Embedding Theorem, \cite[page 107]{Wloka}.
In particular the embedding of $\mathcal{H}^m(G)$
in $\mathcal{H}^n(G)$ for $n<m$ is a compact map and for each
$f\in \mathcal{H}^m(G)$ there exists
$g\in \mathcal{C}^n(G)$ such that $f^{(k)}=g^{(k)}$ a.e. on $G$ for all $k=0,\dots ,n$.
Making this identification, we have
$$
\mathcal{H}^m(G)\subset \mathcal{C}^n(G),\quad n<m,
$$
and there exists a constant $C(G,m)>0$ such that
$$
\sup_G |f^{(k)}|\le C(G,m)\|f\|_m\quad\mbox{for all }
 f\in\mathcal{H}^m(G),\ k<m.
$$
Since Rellich's Theorem holds, the abstract Ehrling Lemma, \cite[page 114]{Wloka}
applies and yields a concrete
Ehrling Lemma, i.e. for each $\epsilon>0$ there exists a constant $C(G,m)>0$ such that
$$
\|f\|_{m-1}\le \epsilon\|f\|_m+C(G,m)\|f\|_0\quad\mbox{for all }
f \in \mathcal{H}^m(G).
$$
The differential equation (\ref{diff}) on the graph $G$ can now be
considered as the system of equations
\begin{equation}\label{diff-1}
-\frac{d^2y_i}{dx^2} + q_i(x)y_i = \lambda y_i,\quad x\in [0,l_i],\; i=1,\dots ,K,
\end{equation}
where $q_i$ and $y_i$ denote $q|_{e_i}$ and $y|_{e_i}$.

The boundary conditions at the node $\nu$ are specified in terms of
the values of $y$ and $y'$ at $\nu$ on each of the incident edges. In particular
if the edges which start at $\nu$ are $e_i, i\in \Lambda_s(\nu)$
and the edges which end at $\nu$ are $e_i, i\in \Lambda_e(\nu)$
then the boundary conditions at $\nu$ can be expressed as
\begin{equation}\label{bc-1}
\sum_{j\in\Lambda_s(\nu)} \left[ \alpha_{ij}y_j+\beta_{ij}{y'}_j\right](0)
+\sum_{j\in\Lambda_e(\nu)} \left[ \gamma_{ij}y_j+\delta_{ij}{y'}_j\right](l_j)=0,
\quad i=1,\dots ,N(\nu),
\end{equation}
where $N(\nu)$ is the number of linearly independent boundary conditions at node $\nu$.
For formally self-adjoint boundary conditions $N(\nu)=\sharp(\Lambda_s(\nu))+\sharp(\Lambda_e(\nu))$
and $\sum_\nu N(\nu)= 2K$, see \cite{carlson, Naimark} for more details.

Let $\alpha_{ij}=0=\beta_{ij}$ for $i=1,\dots ,N(\nu)$ and
$j\not\in \Lambda_s(\nu)$ and similarly let
$\gamma_{ij}=0=\delta_{ij}$ for $i=1,\dots ,N(\nu)$ and
$j\not\in \Lambda_e(\nu)$. The boundary conditions (\ref{bc-1}) considered over all nodes $\nu$, after possible relabelling,
may thus be written as
\begin{equation}\label{bc-2}
\sum_{j=1}^K \left[ \alpha_{ij}y_j+\beta_{ij}{y'}_j\right](0)
+\sum_{j=1}^K \left[ \gamma_{ij}y_j+\delta_{ij}{y'}_j\right](l_j)=0,
\quad i=1,\dots ,2K,
\end{equation}
where $2K$ is the total number of linearly independent boundary conditions.
It should be noted that the complete geometry of the graph $G$ (other than the number of and length of the edges)
is encapsulated in the boundary conditions.

The boundary-value problem (\ref{diff-1})-(\ref{bc-1}) on $G$ can be
formulated as an operator eigenvalue problem in $\mathcal{L}^2(G)$, \cite{agmon, carlson, sho},
for the closed densely defined operator
\begin{equation}
 Lf :=-f''+qf\label{the-operator}
\end{equation}
with domain
\begin{equation}
 \mathcal{D}(L) = \{ f\ |\ f,f' \in AC, Lf\in \mathcal{L}^2(G),
\ f \mbox{ obeying (\ref{bc-1})}\ \}.\label{the-domain}
\end{equation}
The formal self-adjointness of (\ref{diff-1})-(\ref{bc-1}) ensures that
$L$ is a closed densely defined self-adjoint operator in $\mathcal{L}^2(G)$, see \cite{H-P, Naimark, Weid}.

\begin{theorem}\label{semibdd}
The operator $L$ is lower semibounded.
\end{theorem}

\begin{proof}
 From \cite[page 247, Corollary 2]{Weid} as $L$ is self adjoint,
 we need only show that $L$ is lower semibounded on $\mathcal{C}_o^\infty(G)$.
 Let $f\in \mathcal{C}_o^\infty(G)$. Then
 \[
  (Lf,f) = \int_G (-f''\bar{f} +q|f|^2)\ dx
         = \int_G (|f'|^2 +q|f|^2)\ dx
         \ge  -\|f\|^2\mathop{\rm ess\,sup}|q|.
 \]
\end{proof}

\section{Variational Formulation}\label{minimax}

In this section we give an $\mathcal{H}^1(G)$,
variational formulation for the boundary-value problem (\ref{diff-1})-(\ref{bc-1}) or equivalently
for the eigenvalue problem associated with
the operator $L$ defined in (\ref{the-operator})-(\ref{the-domain}).
For details in the setting of partial differential
equations we refer the reader to \cite{Cour}. The
variational formulation gives rise to a max-min
characterization of the eigenvalues and eigenfunctions of the boundary-value problem, developed in the next section.
We conclude the section by proving that the $\mathcal{H}^1(G)$
eigenfunctions are in fact regular, i.e. are in  $\mathcal{H}^2(G)$.

Without loss of generality, we assume the boundary conditions (\ref{bc-2}) to be in the form
\begin{gather}
 \sum_{j=1}^K [\alpha _{ij}y_j(0) + \gamma _{ij}y_j(l_j)]
=0,\quad i=1,\dots,J,\label{gjbc1}\\
 \sum_{j=1}^K [\alpha _{ij}y_j(0)+\beta _{ij}y_j'(0)
+\gamma _{ij}y_j(l_j)+\delta _{ij}y_j'(l_j)]=0,\quad i=J+1,\dots,2K,
 \label{gjbc2}
\end{gather}
where we take $y_i:=y|_{e_i}$.
Here all possible Dirichlet-like terms are in (\ref{gjbc1}),
i.e. if (\ref{gjbc2}) is written in matrix form then Gauss-Jordan reduction
will not allow any pure Dirichlet conditions linearly independent of (\ref{gjbc1}) to be extracted.

Let $F(x,y)$ to be the sesquilinear form given  by
\begin{equation}\label{varform}
F(x,y):= \int_{\partial G} fx\overline{y}\,d\sigma  + \int_G (x'\overline{y}'
+ xq\overline{y})\,dt,
\end{equation}
with domain
$\mathcal{D}(F) = \{y\in \mathcal{H}^1(G)\ |\ y \text{ obeys \eqref{gjbc1}}\}$,
where
$$
\int_{\partial G} y \,d\sigma:= \sum_{i=1}^K [y_i(l_i)-y_i(0)]
= \int_G y'\,dt.
$$

\subsection*{Definition}
 We say that the boundary conditions on a graph are co-normal with respect
to $l$ if  there exists $f$ defined on $\partial G$, such that
$x\in\mathcal{D}(F)$ has
 \[
\int_{\partial G} fx\overline{y}\, d\sigma
= \int_{\partial G} x'\overline{y}\, d\sigma,\quad \mbox{for all}\quad
 y \in \mathcal{D}(F)
\]
if and only if $x$ obeys (\ref{gjbc2}).
\smallskip

We remark that co-normal boundary conditions on a graph correspond
in nature to co-normal (non-oblique) boundary conditions
 for elliptic partial differential operators.

Most physically interesting boundary conditions on graphs fall into the co-normal category. In particular,
`Kirchhoff', Dirichlet, Neumann and periodic boundary conditions are all co-normal, but this class does not
include all self-adjoint boundary-value problems on graphs. For example consider a single loop, i.e. the interval $[0,1]$
where the boundary conditions at $0$ and at $1$ are connected as follows $y(0)=y'(1)$ and $y(1)=-y'(0)$.
These boundary conditions give a self-adjoint boundary-value problem with non co-normal boundary conditions.

The following lemma shows that a function is a variational eigenfunction if and only if it is a
classical eigenfunction.

\begin{lemma} \label{regu}
Suppose that (\ref{gjbc1})-(\ref{gjbc2}) are co-normal boundary conditions
with respect to  $l$ of (\ref{diff}). Then  $u \in \mathcal{D}(F)$ satisfies
$F(u,v) = \lambda (u,v)$ for all $v \in \mathcal{D}(F)$ if and only if
 $u\in \mathcal{H}^2(G)$ and $u$ obeys (\ref{diff}), (\ref{gjbc1})-(\ref{gjbc2}).
\end{lemma}

\begin{proof}
 Assume that $u\in \mathcal{H}^2(G)$ and $u$ obeys (\ref{diff}), (\ref{gjbc1})-(\ref{gjbc2}).
 Then for each $v\in \mathcal{D}(F)$
 \begin{align*}
  F(u,v) &= \int_{\partial G} fu\overline{v}\, d\sigma + \int_G (u'\overline{v}' + qu\overline{v})\,dt\\
         &= \int_{\partial G} fu\overline{v}\, d\sigma
                   + \int_G ((u'\overline{v})' - u''\overline{v}+qu\overline{v})\,dt\\
         &= \int_{\partial G} fu\overline{v}\, d\sigma
                   + \int_G (u'\overline{v})'\,dt +\lambda (u,v)\\
         &= \int_{\partial G} (fu+u')\overline{v}\, d\sigma +\lambda (u,v).
 \end{align*}
 The assumption that (\ref{gjbc1})-(\ref{gjbc2}) are co-normal boundary
conditions with respect to
 $l$ gives that $u\in \mathcal{D}(F)$ and
 $$
\int_{\partial G} (fu+u')\overline{v}\, d\sigma =0,\quad\mbox{for all }
 v\in \mathcal{D}(F),
$$
 completing the proof this in case.

 Now assume $u \in \mathcal{D}(F)$ satisfies $F(u,v) = \lambda (u,v)$ for all $v \in \mathcal{D}(F)$.
 As $\mathcal{C}_o^\infty(G)\subset \mathcal{D}(F)$, it follows that
 $$
F(u,v) = \lambda (u,v),\quad \mbox{for all } v \in \mathcal{C}_0^{\infty}(G).
$$
 Hence $F(u,\cdot)$ can be extended to a continuous linear functional on
$\mathcal{L}^2(G)$.
 In particular this gives that
 $$
\partial u'\in\mathcal{L}^2(G)\subset \mathcal{L}^1_{\rm loc}(G)
$$
 where $\partial$ denotes the distributional derivative.
 Then, by \cite[Theorem 1.6, page 44]{sho},
 $u'\in AC$ and $u''\in \mathcal{L}^1_{\rm loc}(G)$ allowing integration by parts.
 Thus
$$
lu=-u''+qu \in \mathcal{L}^1_{\rm loc}(G)
$$
and consequently $lu=\lambda u\in\mathcal{L}^2(G)$.
 Now $q\in \mathcal{L}^\infty(G)$ and
 $\mathcal{D}(F)\subset \mathcal{L}^2(G)$, giving  $u, u''\in \mathcal{L}^2(G)$
 and hence $u\in \mathcal{H}^2(G)$.

 The definition of $\mathcal{D}(F)$ ensures that (\ref{gjbc1}) holds.
 Integration by parts gives
 $$
\int_{\partial G} (fu+u')\bar{y}\ d\sigma =0,\quad \mbox{for all }
 y\in\mathcal{D}(F),
$$
 which, from the definition of $f$ and the constraints on the class of
 boundary conditions allowed,
 is equivalent to $u$ obeying (\ref{gjbc2}).
\end{proof}

\section{Max-Min Property}

In this section we give a maximum-minimum characterization for the
eigenvalues of boundary-value problems on
graphs. We refer the reader to
\cite[page 406]{Cour} and  \cite{Wein} where boundary-value problems for
partial differential operators are
considered, and analogous results for such eigenvalues developed.

In the following theorem
$\{ v_0,\dots,v_{n-1}\}^\perp$ will denote the orthogonal complement in
$\mathcal{L}^2(G)$  of $\{v_0,\dots,v_{n-1}\}$.
In addition, as is customary, it will be assumed that the eigenvalues,
$\lambda_n$, are listed in increasing order and repeated according to
multiplicity, and that the eigenfunctions, $y_n$, are chosen
 so as to form a complete orthonormal family in $\mathcal{L}^2(G)$.
In this case it is easily verified that
 $F(y_i,y_j)=\lambda_i\delta_{i,j}$.

\begin{theorem}\label{mm}
 For $v_j \in \mathcal{L}^2(G), j=0,1,\dots$, let
 \begin{equation}\label{dmin}
  d_n(v_0, \dots, v_{n-1})
   =\inf\, \left\{\left.\frac{F(\varphi ,\varphi )}{||\varphi ||^2}\ \right|\
    \varphi \in \{ v_0,\dots,v_{n-1}\}^\perp \cap D(F)\setminus \{0\}\right\}.
 \end{equation}
 Then
 $$
\lambda_n = \sup\,\{d_n(v_0,\dots ,v_{n-1})\ |\ v_0,\dots ,v_{n-1} \in
\mathcal{L}^2(G)\},\quad\mbox{for } n=0,1,\dots,
$$
 and this maximum-minimum is attained for $\varphi=y_n$ and
$v_i = y_i$, $i=0,\dots ,n-1$.
\end{theorem}

\begin{proof}
 Let $v_0, \dots, v_{n-1} \in \mathcal{L}^2(G)$.
 As $\text{span}\{y_0, \dots, y_n\}$ is $n+1$ dimensional and
$\text{span}\{v_0,\dots, v_{n-1}\}$ is at most $n$
 dimensional there exists
 $\varphi$ in $\text{span}\{y_0, \dots, y_n\}\setminus \{0\}$
 having
 $$
(\varphi , v_i) = 0,\quad\mbox{for all}\quad i=0,\dots ,n-1.
$$
 In particular, this ensures that $\varphi\in\mathcal{D}(F)$ as each
$y_i$ is in $\mathcal{D}(F)$.

 Denote ${\varphi=\sum_{k=0}^n c_ky_k}$, then
  \[
    F(\varphi,\varphi)=\sum_{i,k=0}^n c_i\bar{c}_k F(y_i,y_k)
    =\sum_{i,k= 0}^n c_i\bar{c}_k \lambda_i\delta_{i,j}
    =\sum_{i=0}^n |c_i|^2 \lambda_i
    \le\lambda_n \sum_{i=0}^n |c_i|^2
    =\lambda_n \|\varphi\|^2,
 \]
 thus showing that
 $$
d_n(v_0, \dots, v_{n-1}) \leq \lambda_n \quad\mbox{for all }
 v_0,\dots,v_{n-1}\in\mathcal{L}^2(G).
$$
For brevity denote
 $$
m:= \sup\,\{d_n(v_0,\dots ,v_{n-1})\,|\,v_0,\dots ,v_{n-1} \in
\mathcal{L}^2(G)\}.
$$
 The above reasoning has shown that $m\le\lambda_n$.

 In order to complete the proof we require that there exists
$\varphi\in \mathcal{D}(F)$ with
 $\|\varphi\|=1$ and $(\varphi,v_i)=0$ for all $i=0,\dots,n-1$ such
that $F(\varphi,\varphi)=d_n(v_0,\dots,v_{n-1})$.
 From the definition of $d_n(v_0,\dots,v_{n-1})$, there exists a sequence
$(u_k)\subset \mathcal{D}(F)$ with
 $\| u_k\|=1$ and $(u_k,v_i)=0$ for all $i=0,\dots,n-1$ and $k\in\mathbb{N}$
such that
 $$
\lim_{k\to\infty} F(u_k,u_k)=d_n(v_0,\dots,v_{n-1}).
$$
 As $\mathcal{H}^1(G)$ is compactly embedded in $\mathcal{L}^2(G)$,
see \cite[page 64]{sho},
 there exists a subsequence of $(u_k)$, which
 we again denote by $(u_k)$ which converges in
$\mathcal{L}^2(G)$ to say $u$ with $\|u\|=1$.

 To show that $u\in \mathcal{H}^1(G)$ we need
 only show that the distribution $\partial u$ is in $\mathcal{L}^2(G)$.
 For each $\psi\in \mathcal{C}_o^\infty(G)\subset \mathcal{D}(F)$,
 $$
\partial u (\psi) = -\int_G u\psi'\ dt=-\lim_{k\to\infty}\int_G u_k\psi'\ dt
 =\lim_{k\to\infty}\int_G u_k'\psi\ dt.
$$
 Thus
 $$
|\partial u(\psi)|\le \limsup \|u_k'\| \|\psi\|\le [d_n(v_0,\dots,v_{n-1})
+\mathop{\rm ess\, sup} |q|]^{1/2}\|\psi\|
$$
 and $\partial u$ can be extended to a continuous linear functional on $\mathcal{L}^2(G)$.
 By the Riesz-Fischer Theorem this gives
 $\partial u\in\mathcal{L}^2(G)$
 and then by \cite[Theorem 1.6, page 44]{sho}, $u\in AC$ with
 $$
\|u'\|^2\le d_n(v_0,\dots,v_{n-1})+\mathop{\rm ess\,sup} |q|.
$$
 Thus $u\in \mathcal{H}^1(G)$ and as
 $$
(u_k',\psi)=-(u_k,\psi')\to -(u,\psi')=(u',\psi), \quad \mbox{for all }
 \psi\in \mathcal{C}^\infty_o(G),
$$
 it follows, by \cite{agmon} applied componentwise, that $u_k\to u$
in $\mathcal{H}^1(G)$.

 Hence there exists $u\in \mathcal{D}(F)\cap \{v_0,\dots,v_{n-1}\}^\perp\backslash\{0\}$
 with $F(u,u)=d_n(v_0,\dots,v_{n-1})$ and
 $\|u\|=1$.
 We now show that such a $u$ is an eigenfunction of (\ref{diff}), (\ref{gjbc1})-(\ref{gjbc2}) with
 eigenvalue $\lambda=d_n(v_0,\dots,v_{n-1})$.

 Let
 $$
J(\varphi,\epsilon)=\frac{F(u+\epsilon\varphi)}{\|u+\epsilon\varphi\|^2}
\quad\mbox{for all }   \varphi \in \mathcal{C}_0^{\infty}(G),
\epsilon \in \mathbb{R}.
$$
 Differentiation with respect to $\epsilon$ of $J(\varphi,\epsilon)$ gives
 $$
0=\frac{\partial}{\partial\epsilon}J(\varphi,\epsilon)|_{\epsilon=0}
   =2\Re[F(\varphi,u)-d_n(v_0,\dots,v_{n-1})(\varphi,u)],
$$
 for all $\varphi \in \mathcal{C}_0^{\infty}(G)$.
 Thus $u$ is a variational eigenfunction with eigenvalue
$\lambda=d_n(v_0,\dots,v_{n-1})$.
 Lemma \ref{regu} now gives that $u$ is in $\mathcal{H}^2(G)$,
 obeys boundary conditions (\ref{gjbc1})-(\ref{gjbc2})
 and equation (\ref{diff}) with  $\lambda=d_n(v_0,\dots,v_{n-1})$,
 making $u$ and eigenfunction of (\ref{diff}), (\ref{gjbc1})-(\ref{gjbc2}) with
 eigenvalue $\lambda$.

 In the case of $n=0$, $d_0$ does not depend on any $v_i$ and $d_0$ is an eigenvalue having
 $m=d_0\le \lambda_0$.
 Thus, in this case, $m=d_0=\lambda_0$.

 In general we have shown $d_n(v_0,\dots,v_{n-1})$ to be an eigenvalue
less than or equal to $\lambda_n$ and  $m\le \lambda_n$. But if
$v_i=y_i, i=0,\dots,n-1,$ then for $u$ to be orthogonal to
$v_0,\dots,v_{n-1}$ and  an eigenfunction to an eigenvalue, $\mu$,
less than or equal to $\lambda_n$ forces $\mu=\lambda_n$ and $u$
 to be in the eigenspace of $\lambda_n$ and orthogonal to $y_0,\dots,y_{n-1}$.
\end{proof}



\section{Eigenvalue Bracketing}

If the boundary conditions (\ref{bc-2}) are replaced by the Dirichlet condition $y=0$ at each node of $G$,
i.e.
\begin{equation}\label{dir}
 y_i(l_i)=0 \quad \text{and} \quad y_i(0)=0, \quad i=1,\dots, K,
\end{equation}
then the graph $G$ becomes disconnected with each edge $e_i$ becoming a component sub-graph, $G_i$, with Dirichlet
boundary conditions at its two nodes (ends). The boundary-value problem on each sub-graph $G_i$ is equivalent
to a Sturm-Liouville boundary-value problem on a compact interval with Dirichlet boundary conditions.

Denote by $A(\lambda)$ the number of eigenvalues less than $\lambda$,
counted according to multiplicity, of
(\ref{diff}), (\ref{gjbc1})-(\ref{gjbc2}).
Let $A^D(\lambda)$ be the number of eigenvalues less than $\lambda$ of
(\ref{diff}) but with (\ref{gjbc1})-(\ref{gjbc2}) replaced by Dirichlet boundary conditions as discussed above, and let
$A^D_j(\lambda)$ be the number of eigenvalues less than $\lambda$ of
(\ref{diff}) on $G_j$ with Dirichlet boundary conditions.
Then
$$
\sum_{j=1}^K A_j^D(\lambda)=A^D(\lambda),\quad \lambda\in\mathbb{R}.
$$
Denote by $\lambda_n^D$ the eigenvalues of (\ref{diff}) with Dirichlet
boundary conditions, as discussed above.

Consider the boundary-value problem
(\ref{diff}),  (\ref{gjbc1})-(\ref{gjbc2}) with the boundary conditions
(\ref{gjbc1})-(\ref{gjbc2}) replaced by the non-Dirichlet conditions
\begin{equation}\label{nond}
 y_i'(l_i)= f(l_i)y_i(l_i) \quad \text{and} \quad y_i'(0)= f(0)y_i(0),
\quad i=1,\dots, K
\end{equation}
where $f$ is given in (\ref{varform}), then, as in the Dirichlet case above,
$G$ decomposes into a union of disconnected graphs $G_1, \dots, G_K$.
Let $\lambda_n^N$ denote the eigenvalues of (\ref{diff}), (\ref{nond})
and $A^N(\lambda)$ the number of
eigenvalues less than $\lambda$ counted according to multiplicity.

Let $A_i^N(\lambda)$ denote the number of eigenvalues less than $\lambda $ of
(\ref{diff}) on $G_i$ with boundary conditions
$$
y_i'(l_i)= f(l_i)y_i(l_i) \quad \text{and} \quad y_i'(0)= f(0)y_i(0).
$$
Then
\[
\sum_{i=1}^K A^N_i(\lambda ) =  A^N(\lambda ).
\]

In the case of co-normal boundary conditions,
Theorem 4.1 has as a consequence that the spectral counting functions defined above are related by
\begin{equation}\label{counting-1}
 \sum_{i=1}^K A_i^D(\lambda)=A^D(\lambda) \leq A(\lambda)\le A^N(\lambda)
=\sum_{i=1}^K A_i^N(\lambda),\quad \lambda\in\mathbb{R},
\end{equation}
and hence the eigenvalues are ordered by
\begin{equation}\label{counting-2}
 \lambda_n^N\le\lambda_n\le\lambda_n^D,\quad n=0,1,\dots.
\end{equation}
These results are the content of the following corollary to Theorem
\ref{mm} which gives an analogue of
\cite[pages 407-410]{Cour} for graphs.

\begin{corollary}\label{bracket}
 If the boundary conditions  (\ref{gjbc1})-(\ref{gjbc2}) are co-normal
with respect to $l$, then the
 the spectral counting functions for (\ref{diff}),  (\ref{gjbc1})-(\ref{gjbc2})
and the related boundary-value problems with the Dirichlet and non-Dirichlet
 boundary conditions given in (\ref{dir}) and (\ref{nond}) are related by
 (\ref{counting-1}) and their spectra are related by (\ref{counting-2}).
\end{corollary}

\begin{proof}
 Denote by $F_D$ the restriction of $F$ to $\mathcal{H}^1_o(G)$ and by $F_N$ the continuous extension (with respect
 to the $\mathcal{H}^1(G)$ norm) of $F$ to $\mathcal{H}^1(G)$.
 As $\mathcal{H}_o^1(G) \subset \mathcal{D}(F) \subset \mathcal{H}^1(G)$ it follows that
 \begin{align*}
 &\left\{\left.\frac{F_D(\varphi,\varphi)}{\|\varphi\|^2}\,
        \right|\,\varphi\in \{v_0,\dots,v_{n-1}\}^\perp\cap\mathcal{H}_o^1(G)
\backslash\{0\}\right\}\\
  &\subset
   \left\{\left.\frac{F(\varphi,\varphi)}{\|\varphi\|^2}\,
        \right|\,\varphi\in \{v_0,\dots,v_{n-1}\}^\perp\cap\mathcal{D}(F)
 \backslash\{0\}\right\}\\
&\subset
   \left\{\left.\frac{F_N(\varphi,\varphi)}{\|\varphi\|^2}\,
        \right|\,\varphi\in \{v_0,\dots,v_{n-1}\}^\perp\cap\mathcal{H}^1(G)
 \backslash\{0\}\right\}.
\end{align*}
 Taking infima gives
 \begin{align*}
 &d_n^D(v_0,\dots,v_{n-1}):=\inf\left\{\left.\frac{F_D(\varphi,\varphi)}{\|\varphi\|^2}\,
        \right|\,\varphi\in \{v_0,\dots,v_{n-1}\}^\perp\cap\mathcal{H}_o^1(G)
\backslash\{0\}\right\}\\
  &\ge d_n(v_0,\dots,v_{n-1})\\
  &\ge
   \inf\left\{\left.\frac{F_N(\varphi,\varphi)}{\|\varphi\|^2}\,
        \right|\,\varphi\in \{v_0,\dots,v_{n-1}\}^\perp\cap\mathcal{H}^1(G)
\backslash\{0\}\right\}=:d_n^N(v_0,\dots,v_{n-1}).
 \end{align*}
 Theorem \ref{mm} now gives
 \begin{align*}
  \lambda_n^D &= \sup\{ d_n^D(v_0,\dots,v_{n-1}) \, |\, v_0,\dots,v_{n-1}
\in\mathcal{L}^2(G)\} \\
   &\ge \lambda_n = \sup\{ d_n(v_0,\dots,v_{n-1}) \, |\, v_0,\dots,v_{n-1}
\in\mathcal{L}^2(G)\}\\
   &\ge \sup\{ d_n^N(v_0,\dots,v_{n-1}) \, |\, v_0,\dots,v_{n-1}
\in\mathcal{L}^2(G)\}=\lambda_n^N
 \end{align*}
 from which the claims of the theorem follow directly.
\end{proof}

\section{Eigenvalue Asymptotics\label{evalasymp}}

The results of the previous section provide a means by which to approximate
the spectrum of a boundary-value problem (\ref{diff-1}) when
boundary conditions (\ref{bc-2}) are of co-normal type,
by considering the spectrum of a finite family of
Sturm-Liouville problems on bounded intervals with separated boundary conditions.
Sturm-Liouville problems on bounded intervals with separated boundary conditions
have been extensively studied, and
consequently eigenvalue approximations for such problems are well known, see \cite{Hoch}.
These eigenvalue approximations
in turn provide information about the spectral counting function for each Sturm-Liouville problem. Corollary 5.1
can now be applied, giving bounds on the spectral counting
function for the original boundary-value problem on the graph,
from which eigenvalue asymptotics can be deduced.

\begin{theorem}\label{As}
Let $G$ be a compact graph with finitely many nodes. If the boundary-value problem (\ref{diff-1}),
(\ref{bc-2}) has co-normal boundary conditions, then its eigenvalues obey the asymptotic development
\[
\lambda _n = \frac{n^2\pi^2}{L^2} + O(n),\quad \mbox{as}\ n\to\infty,
\]
and its spectral counting function has asymptotic approximation
 $$
A(\lambda)=\frac{L\sqrt{\lambda}}{\pi}+O(1),\quad\mbox{as }
 \lambda\to\infty,
$$
where ${L = \sum_{i=1}^K l_i}$ is the total length of the graph.
\end{theorem}

\begin{proof}
 In this proof we use the notation of Section 4.
 If we denote by $\lambda_n^{D,i}, n=0,1,\dots$ the eigenvalues
 of $l$ operating on the graph $G_i$ with Dirichlet conditions at both ends,
then  \cite[Theorem A4]{Hoch} gives that
 \begin{eqnarray*}
  \lambda_n^{D,i}=\frac{(n+1)^2\pi^2}{l_i^2}+O(1),\quad n=0,1,\dots,
 \end{eqnarray*}
 and consequently as $\lambda\to\infty$ we obtain
 \begin{equation}\label{count-D-1}
  A_i^D(\lambda)
  \ge \frac{l_i\sqrt{\lambda-c_i^D}}{\pi} -1,
 \end{equation}
 for some constant $c_i^D>0$.

 Similarly, if we denote by $\lambda_n^{N,i}, n=0,1,\dots$ the eigenvalues
 of $l$ operating on the graph $G_i$ with the separated boundary conditions given in 
 (\ref{nond}), then
 \cite[Theorem A4]{Hoch} gives that
 \begin{eqnarray*}
  \lambda_n^{N,i}=\frac{n^2\pi^2}{l_i^2}+O(1),\quad n=0,1,\dots,
 \end{eqnarray*}
 and consequently for large $\lambda$
 \begin{equation}\label{count-N-1}
  A_i^N(\lambda)
  \le \frac{l_i\sqrt{\lambda+c_i^N}}{\pi}+1,
 \end{equation}
 for some constant $c_i^N>0$.

 Taking ${c=\max_{i=1,\dots,K}\{c_i^D,c_i^N\}}$, equations (\ref{count-D-1}) and (\ref{count-N-1})
 remain valid with $c_i^D$ and $c_i^N$ replaced by $c$. Thus (\ref{count-D-1}) and (\ref{count-N-1}) yield
 \begin{equation}\label{count-DN-1}
  \frac{l_i\sqrt{\lambda-c}}{\pi}-1\le A_i^D(\lambda)\le A_i^N(\lambda)\le \frac{l_i\sqrt{\lambda+c}}{\pi}+1,
  \quad\mbox{as}\quad\lambda\to\infty.
 \end{equation}
 Corollary \ref{bracket}, equation (\ref{counting-1}), can now be combined with (\ref{count-DN-1}) to give
 \begin{eqnarray*}
  \frac{L\sqrt{\lambda-c}}{\pi}-K\le \sum_{i=1}^K A_i^D(\lambda)\le
   A(\lambda)\le \sum_{i=1}^K A_i^N(\lambda)\le \frac{L\sqrt{\lambda+c}}{\pi}+K.
 \end{eqnarray*}
 This can be rewritten as
 $$
A(\lambda)=\frac{L\sqrt{\lambda}}{\pi}+O(1),\quad\mbox{as }
 \lambda\to\infty.
$$
 Solving the asymptotic equation $A(\lambda)=n$ as both $\lambda$ and $n$ tend to infinity gives
 $$
\sqrt{\lambda_n}=\frac{n\pi}{L}+\delta_n
$$
 where $\delta_n=O(1)$, from which the stated eigenvalue asymptotic
approximation follows directly.
\end{proof}

\subsection*{Acknowledgments}
The authors want to thank the referee for the attention given to our paper
and the useful suggestions made.

\begin{thebibliography}{00}
\bibitem{agmon}  S. Agmon;
       {\em Lectures on elliptic boundary-value problems},
       {Princeton}, 1965.
\bibitem{Avron}  J. Avron;
       {{Adiabatic quantum transport in multiply connected systems},
       {\em Reviews of Modern Physics.}, {\bf 60} (1988), 873-915.}
\bibitem{carlson}  R. Carlson;
       {{Adjoint and self-adjoint differential operators on graphs},
       {\em Electronic J. Differential Equations}, {\bf 1998} (1998), No. 06, 1-10.}
\bibitem{codding}  E. A. Coddington, N. Levinson;
       {{\em Theory of ordinary differential equations },
       {McGraw-Hill, New York}, 1955.}
\bibitem{Cour}  R. Courant, D. Hilbert;
       {{\em Methods of Mathematical Physics Volume I},
       {Wiley-Interscience, New York}, 1989.}
\bibitem{Ger}  N. Gerasimenko, B. Pavlov;
       {{Scattering problems on non-compact graphs},
       {\em Theoretical and Mathematical Physics}, {\bf 74} (1988), 230-240.}
\bibitem{Hoch}  H. Hochstadt;
       {{On Inverse Problems Associated with Sturm-Liouville Operators},
       {\em J. Differential Equations}, {\bf 17} (1975), 220-235.}
\bibitem{H-P}  V. Hutson, J.S. Pym;
       {{\em Applications of Functional Analysis and Operator Theory},
       {Academic Press}, 1980.}
\bibitem{kuchment} P. Kuchment;
       {{Graph models for waves in thin structures},
       {\em Waves Random Media}, {\bf 12} (2002), R1-R24.}
\bibitem{Locker}  J. Locker;
       {{\em Spectral Theory of Non-Self-Adjoint Two-Point Differential Operators},
       {American Mathematical Society}, 2000.}
\bibitem{Naimark}  M. A. Naimark;
       {{\em Linear differential operators, part I},
       {Frederick Ungar Publishing Co., New York}, 1967.}
\bibitem{p-p} Yu. V. Pokornyi, V. L. Pryadiev;
       {{Some problems of the qualitative Sturm-Liouville theory on a spatial network},
       {\em Russian Math. Surveys}, {\bf 59}:3 (2004), 515-552.}
\bibitem{p-p-a} Yu. V. Pokornyi, V. L. Pryadiev, A. Al-Obeid;
       {{On the oscillation of the spectrum of a boundary-value problem on a graph},
       {\em Math. Notes}, {\bf 60} (1997), 351-353.}
\bibitem{sho} R. E. Showalter;
       {\em Hilbert Space Methods for Partial Differential Equations},
       Electron. J. Diff. Eqns., Monograph 01, 2001.
\bibitem{solomyak} M. Solomyak;
       {{On the spectrum of the Laplacian on regular metric trees},
       {\em Waves Random Media}, {\bf 14} (2004), S155-S171.}
\bibitem{vB}J. von Below;
       {{Sturm-Liouville eigenvalue problems on networks},
       {\em Math. Methods Appl. Sci.}, {\bf 10} (1988), 383-395.}
\bibitem{Weid}  J. Weidmann;
       {{\em Linear Operators in Hilbert Spaces},
       {Springer-Verlag}, 1980.}
\bibitem{Wein}  H. F. Weinberger;
       {{\em Variational methods for eigenvalue approximation},
       {Society for Industrial and Applied Mathematics, Philadelphia}, 1974.}
\bibitem{Wloka} J. Wloka;
       {{\em Partial Differential Equations},
       {Cambridge University Press}, 1987.}

\end{thebibliography}

\end{document}