Royal Society Publishing

A Borg–Levinson theorem for trees

B.M Brown, R Weikard


We prove that the Dirichelet-to-Neumann map for a Schrödinger operator on a finite simply connected tree determines uniquely the potential on that tree.

1. Introduction

Recently there has been much interest in the inverse spectral problem for the one dimensional Sturm–Liouville problemEmbedded Imagewhere l may be either finite or infinite. More precisely the problem is to recover q from spectral data. Borg (1946) and Levinson (1949) showed when q was real that it is uniquely determined by the associated Titchmarsh–Weyl function. Local versions of this theorem have recently been proved by Simon (1999), Gesztesy & Simon (2000) and Bennewitz (2001), the latter theorem being the result of an elegant and short proof. In the case of complex q, Brown et al. (2002) have shown, using a method modelled on the approach in Bennewitz (2001), that the local Borg theorem is still true. In the case of real q mention must also be made of the famous result of Gel'fand & Levitan (1951) who showed that q could be determined by the spectral function which in the case of a finite interval can itself be determined by two sets of eigenvalues.

The study of the Sturm–Liouville problem on an interval has been extended to its consideration on trees. This has been motivated by quantum models in both physics and chemistry see for instance (Exner et al. 1988; Gerasimenko 1988; Gerasimenko & Pavlov 1988; Bulla & Trenkler 1990). In the case of real coefficients the self-adjoint extensions of symmetric operators on trees have been studied by Carlson in Carlson (1998) and their self-adjoint extensions characterized. Treelike domains have been used to model the scattering problem for partial differential equations (Melnikov & Pavlov 2001), while in a series of papers (Evans & Saitō 2000; Evans et al. 2001) the authors study PDE problems on domains with fractal boundaries and reduce the study of these problems to ones on trees. Further, a recent result of Carlson (1997) has shown that on an infinite homogeneous tree the spectrum of the free Laplacian consists of bands and gaps and possibly eigenvalues. Sobolev & Solomyak (2002) have studied the effect of introducing a real perturbation of the zero potential on such an infinite homogeneous tree when the coupling constant tends to infinity. A further impetus has been given to these studies by the requirements in micro electronics fabrication problems, in particular the construction of quantum switches and other nano-computational devices (see Mikhailova et al. 2002; Mikhaylova & Pavlov 2002; Pavlov 2002) where scattering problems on trees have been studied. In a recent paper, Pivovarchik (2000) considers the inverse spectral problem of the recovery of the coefficients of the Sturm–Liouville problem on a domain consisting of three intervals together with appropriate interface and boundary conditions. He shows that given the spectrum of the problem on the tree together with the Dirichlet problems on each edge, the coefficients of the Sturm–Liouville problem may be recovered. For further references the reader may consult the January 2004 issue of Waves in Random Media where a special section on quantum graphs appeared.

The approach in Borg (1946) and Levinson (1949) is to show that the Titchmarsh–Weyl m-function determines uniquely the function q in the case of a one-dimensional Schrödinger equation. Nachman et al. (1988) have shown an analogous result in the case of a multi-dimensional Schrödinger equation on a bounded domain using the Dirichlet-to-Neumann map instead of the m-function. Curtis & Morrow (1990, 1991) have a similar result for the (combinatorial) problem of a resistor network. We will show here that this is the right idea also for treelike domains following the approach in Bennewitz (2001) and Brown et al. (2002).

More precisely, in this paper we shall study the inverse spectral problem for the Sturm–Liouville problemEmbedded Imageon each branch of a finite tree where the qj are complex-valued and integrable and where continuity and Kirchhoff type conditions for the solutions and their derivatives are imposed at the internal branch points. We shall follow the approach in Brown et al. (2002) adapted to the tree domain with the m-function being replaced by the Dirichlet-to-Neumann map. The main result of this paper is the following theorem (cf. §§2 and 3 for precise definitions).

Let q be a complex-valued integrable potential supported on a simply connected finite tree. Then the associated (generalized) Dirichlet-to-Neumann map uniquely determines the potential almost everywhere on the tree.

Section 2 contains basic definitions and a formulation of the Sturm–Liouville problem on a tree through interface conditions between the branches. Section 3 defines the Dirichlet-to-Neumann map while §4 discusses the structure of the Green's function for this problem. The Weyl solution is introduced in §5 and its asymptotics are obtained. Section 6 shows how the Dirichlet-to-Neumann map may be used to recover the coefficients of boundary edges while an induction argument in §7 shows how the remaining coefficients are also determined by the map. An appendix contains the asymptotics of the basic solutions on an interval.

2. Preliminaries

(a) Trees

For j=1,…,r let ϵj be homeomorphisms defined on [0,1]. The Hausdorff spaceEmbedded Imageis called a directed finite tree if it is simply connected and if ϵj(t)=ϵk(s) happens only if j=k or if t,s∈{0,1}. The points ϵ1(0), ϵ1(1),…,ϵr(0), ϵr(1) are called vertices. The set of all vertices is denoted by V. It contains precisely r+1 elements. The images of the functions ϵj are called edges. The structure of the tree is described uniquely by specifying the vertices connected by each edge, i.e. by the setEmbedded ImageA vertex is called a boundary vertex if it belongs to only one edge. Such an edge will be called a boundary edge. A vertex which belongs to several edges is called an internal vertex. An edge both of whose endpoints are internal vertices is called an internal edge. Without loss of generality we assume that the boundary edges are labelled 1,…,n0 when n0 denotes the number of boundary vertices. We will also assume that the boundary vertices are given by vj=ϵj(0), j=1,…,n0.

(b) The interface conditions

An integrable function y on T may be represented as y=(y1,…,yr)T, where yj(t)=y(ϵj(t)).

If q is an integrable function on T we are interested in problems associated with the differential expression L given by Embedded Image. We impose the following requirements on y.

  1. For each j the functions yj and Embedded Image are absolutely continuous on [0,1].

  2. For each j the function Embedded Image is in L2([0,1]).

  3. y is continuous on T.

  4. For each internal vertex vk the Kirchhoff condition

Embedded Imageholds.

Conditions (iii) and (iv) are called interface conditions.

If νk edges meet at vertex vk then these are precisely νk conditions. Therefore, every internal edge gives rise to two conditions and every boundary edge gives rise to one condition. Altogether there are therefore 2r −n0 interface conditions.

To represent the interface conditions we introduce next the following operators which map C1([0,1])n to Embedded Image (any n):Embedded ImageThe interface conditions are then given as Embedded Imagey=0, where Embedded Image is a (2rn0r matrix whose entries are zeros or ±E0,…,±D1. Note that the first n0 columns of Embedded Image correspond to boundary edges. Therefore, these columns will not involve E0 or D0.

For example, for the tree given by ((v1, v4), (v2, v4), (v3, v4)) we have r=3, n0=3 andEmbedded ImageFor the tree given by ((v1, v3), (v2, v4), (v3, v4)) we have r=3, n0=2 andEmbedded ImageDenote by cj(λ, .) and sj(λ, .) the solutions of Embedded Image satisfying initial conditions Embedded Image and Embedded Image. Note that cj(., x) and sj(., x) are entire functions of growth order 1/2 at most. Now any solution of Embedded Image can be written asEmbedded Imagewhen aj and bj denote appropriate constants. The column (a1,…,ar, b1,…,br)T will be denoted by ξ.

We introduce the following matricesEmbedded ImageEmbedded ImageEmbedded ImageEmbedded Imageand the block matricesEmbedded ImageandEmbedded ImageThen we haveEmbedded Image

3. The generalized Dirichlet-to-Neumann map

We will show below that for all but countably many values of λ there will be a unique solution of Ly=λy satisfying the Dirichlet boundary conditions yj(0)=fj for j=1,…,n0. One may then compute the values Embedded Image. The relationship between the fj and the gj is linear and is called the Dirichlet-to-Neumann map. Instead of Dirichlet and Neumann data we will consider general linear boundary conditions described by n0 pairs Embedded Image and n0 pairs Embedded Image which satisfy the relationshipEmbedded Image(3.1)for j=1,…,n0. More precisely, given the unique solution of Ly=λy satisfying the non-homogeneous boundary conditions Embedded Image (which exists for all but countably many values of λ) we compute the values Embedded Image and call the corresponding linear map the generalized Dirichlet-to-Neumann map which we will denote by Λ. The goal of this section is to compute it.

The boundary conditions are described by the equation Embedded Imagey=f, where Embedded Image is the n0×r matrix (boundary operator)Embedded Imageand where Embedded Image. We also define the matricesEmbedded Imageas well asEmbedded ImageandEmbedded ImageFinally, letEmbedded ImageandEmbedded ImageThe 2r×2r matrix M is of central importance. Its determinant det M is an entire function of λ whose zeros are the eigenvalues of the boundary value problem determined by the αj and Embedded Image. Hence there are at most countably many eigenvalues which cannot have a finite accumulation point. Note that =Pf, whereEmbedded Imagewhen ξ is the vector of coefficient of the basis functions cj and sj as described in §2b.

Now we haveEmbedded ImageHence the generalized Dirichlet-to-Neumann map isEmbedded Image

4. Green's function

We want to obtain a solution of the non-homogeneous system of equations Ly=h, where hL2(T) and where y is subject to the homogeneous boundary conditions Embedded Imagey=0 as well as the interface conditions Embedded Imagey=0.

Let h(t) denote the column (h(ϵ1(t)),…,h(ϵr(t)))T. DefineEmbedded ImagewhereEmbedded ImageandEmbedded ImageThen the general solution of Ly=h may then be represented asEmbedded ImageSince Embedded Imagey=0 is equivalent to +Embedded ImageK=0 we obtainEmbedded ImageBefore we proceed we need to determine the vector Embedded ImageK. To this end we write Embedded Image=Embedded Image0+Embedded Image1, where Embedded Image0 involves the operators E0 and D0 only while Embedded Image1 involves the operators E1 and D1 only. Then we have Embedded Image0K=0. Suppressing the λ-dependence for a while we see thatEmbedded Imageand, since Embedded ImageEmbedded ImageTherefore,Embedded Imagewhere M0=Embedded Image0(C, S).

Let H be the Heaviside function, i.e. H(t) equals zero or one depending on whether t is negative or positive. ThenEmbedded ImageThe Green's function Γ is now the term in brackets in the integrand on the right-hand side of this equation. Since Embedded Image we haveEmbedded ImageNext let 1≤kn0. ThenEmbedded ImageSince the only entry in column k of Embedded Image0 is Embedded Image situated in row k we obtain that the kth and (k+r)th columns of M0(λ) equal Embedded Image and −αkek, respectively.1 HenceEmbedded ImageIf we compute the determinant of M by expanding with respect to row k (which contains at most two non-zero entries) we obtainEmbedded Imagewhere mrk,j(M) denotes the minor of M obtained by deleting row k and column j. The minors may be expressed by the corresponding entries of M−1. Therefore,Embedded ImageSince we also haveEmbedded Imagewe obtainEmbedded ImageHenceEmbedded ImagewhereEmbedded ImageandEmbedded ImageNote θk(., t) and ϕk(., t) are entire functions of growth order 1/2 at most.

5. Weyl solutions

Fix k∈{1,…,n0}. Let ψ(k, λ, .) be the solution of the problem Ly=λy, Embedded Imagey=0, Embedded Imagey=ek . We call this solution the Weyl solution for the boundary vertex k. The Weyl solutions are uniquely determined for any λ which is not an eigenvalue of the boundary value problem determined by the αj and Embedded Image. Recall that these are the roots of the determinant of M and hence the poles of Λ.

Fix k, j∈{1,…,n0}. The Weyl solution for the boundary vertex k satisfies

Embedded Image

Note that Embedded Image for appropriate values of aj and bj. Hence, using equation (3.1)Embedded ImageandEmbedded Image ▪

In the following lemma and its proof we will use different conventions on labelling and orienting boundary vertices and boundary edges of trees as before. We will designate one of the boundary vertices as the root of the tree and denote it by v0. All other boundary vertices will then be called branch tips. The edge attached to the root, denoted by ϵ0, will be called the stem. Nothing will be assumed about the orientation of boundary edges. Note that every vertex v is connected to another vertex v′ by a unique sequence of edges. The number of these edges will be called the distance between v and v′ and will be denoted by d(v, v′). The numberEmbedded Imageis called the height of the tree with respect to the root v0. (The height of a tree depends on which boundary vertex is designated as root.)

We denote the outward normal derivative of a differentiable function Embedded Image at one of the end points by Embedded Image and Embedded Image, i.e. we defineEmbedded ImageFinally, we will call a ray in the complex plane admissible if it emanates from zero and lies otherwise in the open upper half plane.

Suppose T is a tree with root v0 and ψ(λ, .) satisfies the differential equation Ly=λy and the interface conditions Embedded Imagey=0. Also assume that ψ(λ, .) is zero at the branch tips but not identically zero on T. Then, as Embedded Image tends to infinity along an admissible ray,Embedded Image(5.1)where ψ0(λ, t)=ψ(λ, ϵ0(t)) and p∈{0,1} is such that ϵ0(p)=v0.

The proof is by induction on the height of the tree. Assume that the height of T with respect to v0 is one (i.e. T is an interval). If v0=ϵ0(1) then ψ0(λ, t)=b0s0(λ, t) for some non-zero b0 and, using lemma A 1,Embedded ImageIf v0=ϵ0(0) then Embedded Image where Embedded Image. Using again lemma A 1 we findEmbedded ImageNext assume that equation (5.1) is true for every tree whose height is at most n and that T has height n+1 with respect to v0. In addition to the stem itself there are k subtrees attached to the internal endpoint v1 of the stem. We designate v1 to be the root of each of these subtrees and we assign labels 1,…,k to their stems. We also assume that v1=ϵj(1) for j=1,…, and v1=ϵj(0) for j=+1,…,k.

First, assume again v0=ϵ0(1). Then Embedded Image, where a0=ψ(λ, v1) and whereEmbedded ImageEmploying the induction hypothesis we obtain Embedded Image and thus, using lemma A 1,Embedded ImageIf, however, v0=ϵ0(0) then Embedded Image, where Embedded Image and where, using the induction hypothesis,Embedded ImageSolving for a0 and b0 and a final application of lemma A 1 givesEmbedded Image ▪

The preceding lemma has the following immediate corollary for a Weyl solution if t=0. For t∈(0,1) one simply has to apply the lemma to the tree whose stem is ϵk([t,1]) rather than ϵk([0,1]).

If k∈{1,…,n0} and t∈[0,1) thenEmbedded Imageas Embedded Image tends to infinity along an admissible ray.

If k∈{1,…,n0} and t∈[0,1) then the diagonal Green's function Γk,k(λ, t, t) tends to zero as Embedded Image tends to infinity along an admissible ray.

By lemma 5.1 we have Embedded Image and that the Wronskian of ψk(k, λ, .) and ϕk(λ, .) equals the Wronskian of θk(k, λ, .) and ϕk(λ, .) and hence 1. Therefore, as Embedded Image tends to infinity,Embedded Imageusing lemma A 1 for the first term and corollary 5.3 for the second. ▪

6. The potential on the boundary edges

The (generalized) Dirichlet-to-Neumann map determines uniquely the potential almost everywhere on the boundary edges.

Fix k∈{1,…,n0} and t∈[0,1). Suppose q and Embedded Image are two potentials on T giving rise to the same (generalized) Dirichlet-to-Neumann map. Associated with Embedded Image are the functions Embedded Image, Embedded Image, Embedded Image and Embedded Image just like θ, ϕ, ψ and Λ are associated with q. From lemma A 1 we know that Embedded Image tends to one as λ tends to infinity. This fact and theorem 5.4 yieldEmbedded Imageas Embedded Image tends to infinity along an admissible ray. Recall that Embedded Image and, by assumption, Embedded Image. Therefore we find thatEmbedded ImageAs noted earlier all of the four terms appearing here on the right-hand side are entire functions of growth order 1/2 when viewed as functions of λ. Thus g is an entire function of growth order 1/2, which tends to zero along the positive and the negative imaginary axis (for instance). The Phragmén–Lindelöf theorem implies that g is bounded in Embedded Image, so it is constant by Liouville's theorem and in fact identically equal to zero, i.e.Embedded ImageSince t∈[0,1) was arbitrary this equation holds for all t∈[0,1) and for all Embedded Image. Differentiating both sides with respect to t gives Embedded Image. Differentiating once more gives Embedded Image. Differentiating a third time gives finallyEmbedded Imagealmost everywhere on [0,1]. ▪

7. Pruning the tree

Let T be a tree with n0 boundary edges, q a potential on T and Λ the associated Dirichlet-to-Neumann map. Let v* be a vertex such that all but one of the edges attached to v* are boundary edges. Assume the number of these boundary edges is r* and that the labels of their boundary vertices are n0r*+1,…,n0. Let T* be the tree with the boundary edges just mentioned removed so that its boundary vertices are Embedded Image, and v*. Then the Dirichlet-to-Neumann map Λ* for T* is uniquely determined by Λ and the restriction of the potential q to the boundary edges attached to v*.

We have to compute the values Λ*f* for an arbitrary vector Embedded Image. We will do this for any value of λ which is not an eigenvalue for the Dirichlet problem for T nor an eigenvalue for the Dirichlet problem for T*. It is clearly sufficient to consider only these λ as we are missing at most countably many. Note that we may assume that the functions c(λ, .) and s(λ, .), and hence the function Embedded Image are known for all Embedded Image and all Embedded Image since we know the potentials on the corresponding edges.

Next we want to show that there is a Embedded Image such that Embedded Image. Assume that ψ(n0, λ, v*)=0. Since λ is not an eigenvalue for T* we have that Embedded Image is the zero function. Hence there must be a Embedded Image such that Embedded Image is not identically equal to zero. For this k we have, using lemma 5.1,Embedded Imagei.e. sk(λ, 1)=0 and thus ck(λ, 1)≠0. HenceEmbedded ImageNow defineEmbedded Imagefor some number γ yet to be determined. Then Χ(λ, .) has Dirichlet data given by the vectorEmbedded Imageand Embedded Image has Dirichlet data given by the vector f* provided that Embedded Image, i.e. ifEmbedded ImageSince ψk(k, λ, 1)≠0 we may (and will) choose γ such that this condition is satisfied. ThereforeEmbedded ImageMoreover, by the Kirchhoff conditions,Embedded Imagewhere the right-hand side involves only known quantities. ▪

We are now in a position to prove theorem 1.1.

Proof of theorem 1.1. Let Λ be the generalized Dirichlet-to-Neumann map given. Then the Dirichlet-to-Neumann map ΛD–N itself is given byEmbedded ImageHence we may assume without loss of generality that the given map is the Dirichlet-to-Neumann map. Theorem 6.1 gives q on the boundary edges. If we can show the existence of an internal vertex with the properties of the vertex v* in theorem 7.1 we may use that theorem to show that the Dirichlet-to-Neumann map is now given on the tree where certain edges are removed. Induction then completes the proof.

To show the existence of v* recall the concepts introduced before lemma 5.2 and designate any boundary vertex as the root of the tree. Suppose that the tree has height h with respect to the root. Then any vertex whose distance from the root is h−1 (we may, of course, assume that h>1) has the properties of v*, i.e. all but one of the edges attached to it are boundary edges. ▪


We are indebted to the referees for many useful comments which led to a greatly improved presentation and the abolition of a number of mistakes.

Appendix A Asymptotics of basic solutions

Let qL1([0,1]). Suppose that u(λ, .) solves the equationy″+qy=λy. DefineEmbedded Imageand Embedded Image. Then, for all x∈[0,1] and all complex λ≠0,Embedded Image

Without loss of generality we choose the root of λ in the open upper half plane or the positive real axis. Let Embedded Image and defineEmbedded ImageReplacing u by u0+(uu0) in the variation of constants formulaEmbedded Imageone findsEmbedded Image(A1)Let Embedded Image, move the first term on the right of (A 1) to the left, and multiply with |q(t)|exp(−ϕ(t)). This will produce total derivatives on either side so that integration from 0 to x yieldsEmbedded ImageUsing this estimate in (A 1) gives the desired estimate on uu0. The statement on Embedded Image follows from this and the derivative of the variation of constants formula. ▪

We remark that this proof is fairly standard and that it is included here for the convenience of the reader.


  • This material is based upon work supported by the National Science Foundation under grant no. DMS-0304280.

  • We denote the vector whose entries are zero save for a 1 at position k by ek.

    • Received November 26, 2003.
    • Accepted May 6, 2005.


View Abstract