# Minimal Steklov eigenvalues on combinatorial graphs

Chengjie Yu1 Department of Mathematics, Shantou University, Shantou,
Guangdong, 515063, China<EMAIL_ADDRESS>and  Yingtao Yu  Department of
Mathematics, Shantou University, Shantou, Guangdong, 515063, China
<EMAIL_ADDRESS>
###### Abstract.

In this paper, we study extremal problems of Steklov eigenvalues on
combinatorial graphs by extending Friedman’s theory of nodal domains for
Laplacian eigenfunctions to Steklov eigenfunctions.

###### Key words and phrases:

Steklov eigenvalue, extremal problem, nodal domain

###### 2010 Mathematics Subject Classification:

Primary 05C50; Secondary 39A12

1Research partially supported by GDNSF with contract no. 2021A1515010264 and
NNSF of China with contract no. 11571215.

##  1\. Introduction

For a compact Riemannian manifold with boundary, the Steklov operator or
Dirichlet-to-Neumann map (DtN map for short) is defined to be the map sending
the Dirichlet boundary data of a harmonic function on the manifold to its
Neumann boundary data. The eigenvalues of the Steklov operator are called
Steklov eigenvalues of the manifold. Such notions were originated in Steklov’s
study of liquid sloshing more than a century ago (See [25, 18]). Steklov
operators or DtN maps are also original models for inverse problems such as
detecting the inside of a body by boundary measurements. Escobar [5] also
found relations between Steklov eigenvalues and the Yamabe problems on
Riemannian manifolds with boundary. In recently years, Fraser and Scheon [6]
found relations between Steklov eigenfunctions and free boundary minimal
submanifolds in the Euclidean ball and made important progresses on extremal
problems of Steklov eigenvalues ([6, 7, 8, 9]).

The notions of Steklov operators and Steklov eigenvalues were recently
extended to discrete settings independently by Hua, Huang and Wang in [16] and
Hassannezhad and Miclo in [13]. Colbois and Girouard [3] also considered
similar extensions of Steklov eigenvalues to the discrete settings when
studying Steklov eigenvalues on manifolds constructed out of graphs (See also
[4]). Although the notions are new, there have been a number of studies on
exploring the properties of Steklov eigenvalues in the discrete setting. For
example, in [13, 16, 17, 12, 14, 20, 26], the authors studied isoperimetric
control of Steklov eigenvalues. In [15, 27], the authors studied monotonicity
of Steklov eigenvalues. In [19], the author gave some interesting upper or
lower bounds. In [24], the authors compared the Steklov eigenvalues with the
Laplacian eigenvalues. In [23], the authors obtained a Lichnerowicz-type
estimate for Steklov eigenvalues. In [22], the authors introduced higher
degree versions of Steklove operators and Steklov eigenvalues.

In this paper, motivated by the works of Fraser and Schoen in the smooth
setting and Friedman’s works [10, 11] for Laplacian eigenvalues on
combinatorial graphs, and also motivated by the works [14, 15] of He and Hua,
and our previous work [27], we consider extremal problems on combinatorial
graphs. Let’s first recall some preliminary notions for graphs.

######  Definition 1.1.

  1. (1)

A triple $(G,m,w)$ is called a weighted graph where

    1. (a)

$G$ is a simple graph with $V(G)$ and $E(G)$ the sets of vertices and edges of
$G$ respectively;

    2. (b)

$m:V(G)\to\mathbb{R}^{+}$ is the vertex-measure;

    3. (c)

$w:E(G)\to\mathbb{R}^{+}$ is the edge-weight.

When $m\equiv 1$ and $w\equiv 1$, we say that $G$ is equipped with the unit
weight. A subgraph $G^{\prime}$ of the weighted graph $G$ is viewed as a
weighted graph by restricting the vertex-measure and edge-weight to
$G^{\prime}$. For convenience, the edge-weight $w$ is also viewed as a
symmetric function on $V\times V$ by zero extension.

  2. (2)

A pair $(G,B)$ is called a graph with boundary where $G$ is a simple graph and
$B\subset V(G)$. The set $\Omega:=V(G)\setminus B$ is called the interior of
$G$. We will also denote $B$ and $\Omega$ as $B(G)$ and $\Omega(G)$
respectively if necessary.

  3. (3)

A simple graph $G$ is called a combinatorial graph if it is equipped with the
unit weight and $B(G)=\\{v\in V(G)\ |\ \deg v\leq 1\\}$. For a nontrivial
combinatorial tree $G$, $B(G)=L(G)$ where $L(G)$ is the collection of leaves
in $G$.

On a weighted finite graph $(G,B,m,w)$ with boundary, analogous to the smooth
case, one can similarly define the Steklov operator
$\Lambda:\mathbb{R}^{B}\to\mathbb{R}^{B}$ (See Section 2 for details). The
eigenvalues of $\Lambda$ are called Steklov eigenvalues of the graph and
denoted as

$0=\sigma_{1}(G,B,m,w)\leq\sigma_{2}(G,B,m,w)\leq\cdots\leq\sigma_{|B|}(G,B,m,w).$

For simplicity, we will also write $\sigma_{i}(G,B,m,w)$ as $\sigma_{i}$,
$\sigma_{i}(G)$ or $\sigma_{i}(G,B)$ if the ignored information is clear in
context. When $i>|B|$, we conventionally take $\sigma_{i}=+\infty$. For the
trivial graph $G$ with only one vertex, we view the vertex as a boundary
vertex and hence $\sigma_{1}(G)=0$ and $\sigma_{i}(G)=+\infty$ for $i\geq 2$.

The extremal problem we considered in this paper is: _Let $G$ be a connected
combinatorial graph on $n$ vertices. What is the minimum value of
$\sigma_{i}(G)$?_ This problem is an analogue of the problem considered by
Friedman [11] for Laplacian eigenvalues.

Note that the notion of graphs with boundary considered in this paper is more
general than that in [19]. The main difference is that we don’t require that
$E(B,B)=\emptyset$ in (2) of Definition 1.1. In fact, this kind of more
general graphs with boundary was considered in [3, 4]. Note that if all the
edges in $E(B,B)$ are deleted, we get a graph with boundary under the more
special definition in [19]. Moreover, the process of deleting the edges in
$E(B,B)$ will reduce the Steklov eigenvalues by the simple monotonicity of
Steklov eigenvalues in Theorem 1.2 below. Thus, there will be no difference in
general when considering minimum problems on Steklov eigenvalues for the two
kinds of graphs with boundary. The reason that we take this more general
notion of graphs with boundary is twofold. One is that the notion is simpler
and more general, and the other is that the path with two vertices can not be
viewed as a combinatorial graph with boundary if we take the more special
definition in [19].

Our answer to the extremal problem for Steklov eigenvalues is similar to that
of Friedman [11] for Laplacian eigenvalues. Follows is a summary of the main
results of this paper.

######  Theorem 1.1.

Let $G$ be a connected combinatorial finite graph on $n\geq 2$ vertices. Then,

  1. (1)

$\sigma_{2}(G)\geq\Lambda(\frac{n-1}{2})$. The equality holds if and only if

    1. (a)

$G={\rm DB}(m,2m,m)$ when $n=4m+1$;

    2. (b)

$G={\rm DB}(m,2m+1,m)$ when $n=4m+2$;

    3. (c)

$G={\rm DB}(m+1,2m,m+1),{\rm DB}(m,2m+2,m)\ \mbox{or}\ {\rm DB}(m,2m+1,m+1)$
when $n=4m+3$;

    4. (d)

$G={\rm DB}(m+1,2m+1,m+1)$ when $n=4m+4$;

  2. (2)

for $i$ with $2<i<n$ and $i\not|\ n$,

$\sigma_{i}(G)\geq\Lambda(m)$

where $m=\lfloor\frac{n}{i}\rfloor$. Moreover, when $n=im+1$, the equality
holds if and only if $G$ is a star of degree $i$ such that each arm is a
minimal broom ${\rm Br}(m)$ with the center of the star as the root.

  3. (3)

for $i$ with $2<i<n$ and $i|n$,

$\sigma_{i}(G)\geq\Lambda(m-1+\theta_{i})$

where $m=\frac{n}{i}$ and $\theta_{i}=\frac{1}{4\cos^{2}\frac{\pi}{2i}}$. The
equality holds if and only if $G={\rm Comb}(P_{i};T)$ when $i$ is even, and
$G={\rm Comb}(P_{i};T)\mbox{ or }{\rm Comb}(C_{i};T)$ when $i$ is odd. Here
$P_{i}$ and $C_{i}$ are the path and the cycle on $i$ vertices respectively.
Moreover, $T$ is the minimal broom ${\rm Br}(m-1+\theta_{i})$ with the
Dirichlet boundary vertex deleted and the vertex adjacent to Dirichlet
boundary vertex as the root.

Here,

$\Lambda(l)=\left\\{\begin{array}[]{ll}\frac{1}{l}&0<l<1\\\
\frac{1}{1+\lfloor\frac{l+1}{2}\rfloor(l-\lfloor\frac{l+1}{2}\rfloor)}&l\geq
1.\end{array}\right.$

For the definitions of the minimal broom ${\rm Br}(l)$, dumbbell ${\rm
DB}(d_{1},i,d_{2})$ and regular combs ${\rm Comb}(P_{i};T)$ and ${\rm
Comb}(C_{i};T)$, see Definition 2.4, Definition 2.5 and Definition 2.7 in
Section 2 respectively.

Note that when $m\geq 3$ is an odd number, there are two different brooms in
${\rm Br}(m)$ (See Lemma 2.3). Thus, when $m$ is an odd number not less than
$3$, there are $i+1$ different stars of degree $i$ with all arms minimal
brooms ${\rm Br}(m)$. So, in Theorem 1.1, when $n=im+1$ with $m$ an odd number
not less than $3$, there are $i+1$ different graphs so that the equality
$\sigma_{i}(G)=\Lambda(m)$ holds. When $n=im+s$ with $2\leq s\leq i-1$, the
same as in [11], we are not able to completely characterize the graphs such
that the equality $\sigma_{i}(G)=\Lambda(m)$ holds. However, the equality
holds for example on the star with degree $i+s-1$ such that $i$ arms are
minimal brooms ${\rm Br}(m)$ and $s-1$ arms are paths of length $1$.

Our strategy to solve the extremal problem for Steklov eigenvalues on
combinatorial finite graphs is similar to the strategy by Friedman [11]
solving the corresponding extremal problems for Laplacian eigenvalues. First
by the following simple monotonicity of Steklov eigenvalues that is different
with the monotonicity in [15, 27], we reduce the extremal problems to trees.

######  Theorem 1.2.

Let $(\widetilde{G},\widetilde{B},m,w)$ be a weighted finite graph and $(G,B)$
be such that $G$ is a subgraph of $\widetilde{G}$ and $B\supset\widetilde{B}$.
Then

(1.1) $\sigma_{i}(\widetilde{G},\widetilde{B})\geq\sigma_{i}(G,B)$

for $i=1,2,\cdots,|\widetilde{B}|$. In particular, if $\widetilde{G}$ is a
combinatorial finite graph and $G$ is a spanning subgraph of $\widetilde{G}$,
Then,

(1.2) $\sigma_{i}(\widetilde{G})\geq\sigma_{i}(G)$

for all $i\geq 0$.

After reducing the extremal problem to trees, following the strategy by
Friedman [11], we then study the minimal problem of the first Steklov
eigenvalues with vanishing Dirichlet boundary data on trees (See Section 5 for
details). In [11], Friedman showed that the minimal tree for the first
Laplacian eigenvalues with vanishing Dirichlet boundary data is essentially a
path. However, it is rather different for the Steklov case. The minimal tree
for this case is essentially a minimal broom (See Theorem 5.1 for details).
This makes the minimal graphs for Steklov eigenvalues become more complicated
than those for Lapalcian eigenvalues in [11].

Next, by developing a theory of nodal domains for Steklov eigenvalues that is
similar to the theory of nodal domains for Laplacian eigenvalues established
by Friedman [10], we reduce the extremal problem for Steklov eigenvalues on
trees to the minimum problem of the first Steklov eigenvalues with vanishing
Dirichlet boundary data on its nodal domains which has been solved in the last
step.

The organization of the rest of the paper is as follows. In Section 2, we
introduce some preliminary notions and symbols on analysis of graphs; In
Section 3, we prove the monotonicity in Theorem 1.2 and discuss its rigidity;
In Section 4, we study nodal domains for Steklov eigenfunctions; In Section 5,
we obtain the minimum for the first Steklov eigenvalues with vanishing
Dirichlet boundary data on trees which is an analogue of Lemma 3.1 in [11] and
plays an important role in later applications; In Section 6, we recall the
notion of clump numbers of trees in [11], explore some of its properties and
recall the results in [11] about reducing clump numbers of trees by removing
edges. In Section 7, we prove Theorem 1.1. A crucial step in the proof of
Theorem 1.1 is to relate the first positive Steklov eigenvalue of a tree to
its clump number (See Theorem 7.1) which is an analogue of Lemma 4.1 in [11]
for the first positive Laplacian eigenvalue.

##  2\. Preliminaries

In this section, we recall some notions and symbols on spectral analysis of
graphs.

Let $(G,m,w)$ be a weighted finite graph. As in [1, Definition 2.1], a skew
symmetric function $\alpha:V(G)\times V(G)\to\mathbb{R}$ such that
$\alpha(x,y)=0$ when $x\not\sim y$ is called a flow on the graph $G$. The
collection of all flows on $G$ is denoted as $A^{1}(G)$. Equipped with the
spaces $\mathbb{R}^{V(G)}$ and $A^{1}(G)$ the natural inner products

(2.1) ${\left\langle f,g\right\rangle}_{G}=\sum_{x\in V(G)}f(x)g(x)m_{x}$

and

(2.2) ${\left\langle\alpha,\beta\right\rangle}_{G}=\sum_{\\{x,y\\}\in
E(G)}\alpha(x,y)\beta(x,y)w_{xy}$

respectively. When $A\subset V(G)$ and $S\subset E(G)$, we define

(2.3) ${\left\langle f,g\right\rangle}_{A}=\sum_{x\in A}f(x)g(x)m_{x}$

and

(2.4) ${\left\langle\alpha,\beta\right\rangle}_{S}=\sum_{\\{x,y\\}\in
S}\alpha(x,y)\beta(x,y)w_{xy}.$

Let $d:\mathbb{R}^{V(G)}\to A^{1}(G)$ be the map:

(2.5) $df(x,y)=\left\\{\begin{array}[]{ll}f(y)-f(x)&x\sim y\\\ 0&x\not\sim
y.\end{array}\right.$

Let $d^{*}:A^{1}(G)\to\mathbb{R}^{V(G)}$ be the adjoint operator of $d$ and
define the Laplacian operator of $G$ as

(2.6) $\Delta_{G}f=-d^{*}df.$

By direct computation, it is not hard to check that

(2.7) $\Delta_{G}f(x)=\frac{1}{m_{x}}\sum_{y\in V(G)}(f(y)-f(x))w_{xy}$

for any $x\in V(G)$ and $f\in\mathbb{R}^{V(G)}$. By the definition of
$\Delta_{G}$, it is clear that

(2.8) $-{\left\langle\Delta_{G}f,g\right\rangle}_{G}={\left\langle
df,dg\right\rangle}_{G}$

for any $f,g\in\mathbb{R}^{V(G)}$. So $-\Delta_{G}$ is a nonnegative self-
adjoint operator on $\mathbb{R}^{V(G)}$, its eigenvalues are denoted as

$0=\mu_{1}(G)\leq\mu_{2}(G)\leq\cdots\leq\mu_{|V(G)|}(G)$

and are called the Laplacian eigenvalues of $G$.

Let $(G,B,m,w)$ be a weight finite graph with boundary. For any
$f\in\mathbb{R}^{V(G)}$, define

(2.9) $\frac{\partial f}{\partial n}(x)=\frac{1}{m_{x}}\sum_{y\in
V(G)}(f(x)-f(y))w_{xy}=-\Delta_{G}f(x)$

for any $x\in B$. The operator is regarded as the discrete version of taking
normal derivative on the boundary of a Riemannian manifold. By (2.8) and
(2.9), we have the following Green’s identity:

(2.10) ${\left\langle df,dg\right\rangle}_{G}={\left\langle\frac{\partial
f}{\partial
n},g\right\rangle}_{B}-{\left\langle\Delta_{G}f,g\right\rangle}_{\Omega}.$

This may be the reason that one defines $\frac{\partial f}{\partial n}$ as
$-\Delta_{G}f\big{|}_{B}$.

A real number $\sigma$ is called a Steklov eigenvalue of $(G,B,m,w)$ if the
following boundary value problem:

(2.11) $\left\\{\begin{array}[]{ll}\Delta_{G}f(x)=0&x\in\Omega\\\
\frac{\partial f}{\partial n}(x)=\sigma f(x)&x\in B\end{array}\right.$

have nonzero solutions. A nonzero solution $f$ of the boundary value problem
is called a Steklov eigenfunction for the eigenvalue $\sigma$. It is not hard
the see that the Steklov eigenvalues are the eigenvalues of the so called
Steklov operator or DtN map:

$\Lambda:\mathbb{R}^{B}\to\mathbb{R}^{B},\Lambda(u)=\frac{\partial\widehat{u}}{\partial
n}$

where $\widehat{u}$ means the harmonic extension of $u$. That is,
$\widehat{u}$ satisifies the following Dirichlet boundary value problem:

(2.12) $\left\\{\begin{array}[]{ll}\Delta_{G}\widehat{u}(x)=0&x\in\Omega\\\
\widehat{u}(x)=u(x)&x\in B.\end{array}\right.$

By (2.10), we know that

(2.13) ${\left\langle\Lambda(u),v\right\rangle}_{B}={\left\langle
d\widehat{u},d\widehat{v}\right\rangle}_{G}$

for any $u,v\in\mathbb{R}^{B}$. So, $\Lambda$ is a nonnegative self-adjoint
operator on $\mathbb{R}^{B}$, and its eigenvalues are denoted as

$0=\sigma_{1}(G,B,m,w)\leq\sigma_{2}(G,B,m,w)\leq\cdots\leq\sigma_{|B|}(G,B,m,w).$

For simplicity, we also denote $\sigma_{i}(G,B,m,w)$ as
$\sigma_{i},\sigma_{i}(G),\sigma_{i}(G,B)$ when the ignored information is
clear in context.

To extend Friedman’s theory of nodal domains for Laplacian eigenfunction to
Steklov eigenfunctions, we need to consider Steklov eigenvalues with vanishing
Dirichlet boundary data as in [15, 27]. So, we introduce the notion of graph
with boundary and Dirichlet boundary.

######  Definition 2.1.

A triple $(G,B,B_{D})$ is called a graph with boundary $B$ and Dirichlet
boundary $B_{D}$ if $G$ is a simple graph, $B,B_{D}\subset V(G)$ and $B\cap
B_{D}=\emptyset$. $\Omega_{D}:=V(G)\setminus B_{D}$ is called the Dirichlet
interior of $G$ and $\Omega=\Omega_{D}\setminus B$ is called the interior of
$G$. An edge in $E(B_{D},\Omega_{D})$ is called a Dirichlet boundary edge. We
will also denote $B,B_{D},\Omega$ and $\Omega_{D}$ as
$B(G),B_{D}(G),\Omega(G)$ and $\Omega_{D}(G)$ respectively if necessary.

Let $(G,B,B_{D},m,w)$ be a weighted finite graph with boundary $B$ and
Dirichlet boundary $B_{D}$. A real number $\lambda$ is called a Steklov
eigenvalue of $(G,B,B_{D},m,w)$ with vanishing Dirichlet boundary data on
$B_{D}$ if the following boundary value problem:

(2.14) $\left\\{\begin{array}[]{ll}\Delta_{G}f(x)=0&x\in\Omega\\\
\frac{\partial f}{\partial n}(x)=\lambda f(x)&x\in B\\\ f(x)=0&x\in
B_{D}\end{array}\right.$

has nonzero solutions. A nonzero solution $f$ of the boundary value problem is
called a Steklov eigenfunction with vanishing Dirichlet boundary data on
$B_{D}$ for the eigenvalue $\lambda$. The Steklov eigenvalues with vanishing
Dirichlet boundary data on $B_{D}$ are the eigenvalues of the following
Steklov operator with vanishing Dirichlet boundary data on $B_{D}$:

$\Lambda_{0}:\mathbb{R}^{B}\to\mathbb{R}^{B},\
\Lambda_{0}(u)=\frac{\partial\zeta_{u}}{\partial n}$

where $\zeta_{u}$ satisfies

(2.15) $\left\\{\begin{array}[]{ll}\Delta_{G}\zeta_{u}(x)=0&x\in\Omega\\\
\zeta_{u}(x)=u(x)&x\in B\\\ \zeta_{u}(x)=0&x\in B_{D}.\end{array}\right.$

By (2.10),

(2.16) ${\left\langle\Lambda_{0}(u),v\right\rangle}_{B}={\left\langle
d\zeta_{u},d\zeta_{v}\right\rangle}_{G}$

for any $u,v\in\mathbb{R}^{B}$. So,
$\Lambda_{0}:\mathbb{R}^{B}\to\mathbb{R}^{B}$ is a nonnegative self-adjoint
operator on $\mathbb{R}^{B}$, and its eigenvalues are denoted as:

$0\leq\lambda_{1}(G,B,B_{D},m,w)\leq\lambda_{2}(G,B,B_{D},m,w)\leq\cdots\leq\lambda_{|B|}(G,B,B_{D},m,w).$

For simplicity, we also denote $\lambda_{i}(G,B,B_{D},m,w)$ as
$\lambda_{i},\lambda_{i}(G),\lambda_{i}(G,B,B_{D})$ when the ignored
information is clear in context. By the Dirichlet principle, it is clear that

$\lambda_{1}(G,B,B_{D})=\min\left\\{\frac{{\left\langle
df,df\right\rangle}_{G}}{{\left\langle f,f\right\rangle}_{B}}\ \bigg{|}\
f\in\mathbb{R}^{V(G)}\ \mbox{with }f|_{B}\not\equiv 0\ \mbox{and
}f|_{B_{D}}=0.\right\\}.$

Thus, if $G$ is connected and $B_{D}$ is nonempty, then
$\lambda_{1}(G,B,B_{D})>0$. It is also clear that the measures of the vertices
in $B_{D}$ do not affect the map $\Lambda_{0}$ and the eigenvalues
$\lambda_{i}(G,B,B_{D})$.

Next, we introduce the notion of a broom.

######  Definition 2.2.

Let $P$ be the path of length $i$. The tree formed by adding a Dirichlet
boundary edge to one of the end points of $P$ with length $l$ (i.e. with
weight $\frac{1}{l}$) and adding $d$ boundary vertices to the other end point
of $P$ is denoted as ${\rm Br}(l,i,d)$ which is called a broom with parameters
$(l,i,d)$. When $d=0$, the other end point of $P$ is viewed as the boundary
vertex. The Dirichlet boundary vertex is viewed as the root of the broom and
is denoted as $o$.

Note that ${\rm Br}(l,i,1)={\rm Br}(l,i+1,0)$ by definition. The Steklov
eigenvalue with vanishing Dirichlet boundary data of a broom can be computed
directly.

######  Lemma 2.1.

For any real number $l>0$ and nonnegative integers $i$ and $d$,

$\lambda_{1}({\rm Br}(l,i,d))=\left\\{\begin{array}[]{ll}\frac{1}{l+i}&d=0\\\
\frac{1}{1+(l+i)d}&d\geq 1.\end{array}\right.$

Moreover, let $v_{0}\sim v_{1}\sim\cdots\sim v_{i}$ be the path $P$ and $o\sim
v_{0}$ in ${\rm Br}(l,i,d)$, and $u_{1},u_{2},\cdots,u_{d}$ be the boundary
vertices of ${\rm Br}(l,i,d)$ when $d>0$. Then, the eigenfunction $f$ is given
by

(2.17) $f(x)=\left\\{\begin{array}[]{ll}0&x=o\\\ \frac{l+j}{l+i}&x=v_{j}\mbox{
with }j=0,1,\cdots,i\end{array}\right.$

when $d=0$, and

(2.18) $f(x)=\left\\{\begin{array}[]{ll}0&x=o\\\
\frac{(l+j)d}{1+(l+i)d}&x=v_{j}\mbox{ with }j=0,1,\cdots,i\\\ 1&x=u_{j}\mbox{
with }j=1,2,\cdots,d\\\ \end{array}\right.$

when $d>0$.

###### Proof.

The conclusion can be shown by direct verification. ∎

Next, we introduce the notion of minimal brooms. It plays an important role in
Section 5.

######  Definition 2.3.

For any nonnegative integer $n$ and positive real number $l$, we denote ${\rm
Br}(l,n)$ the brooms that have the minimal $\lambda_{1}$ among all brooms
${\rm Br}(l,i,d)$ with $i+d=n$. We call ${\rm Br}(l,n)$ the minimal brooms
with parameters $(l,n)$ and denote $\lambda_{1}({\rm Br}(l,n))$ as
$\Lambda(l,n)$.

By Lemma 2.1, we have the following conclusion.

######  Lemma 2.2.

The function $\Lambda(l,n)$ is strictly decreasing on $l$ and $n$. More
precisely, when $n=0,1$, ${\rm Br}(l,n)={\rm Br}(l,n,0)$, and when $n\geq 2,$

$\begin{split}{\rm Br}(l,n)=\left\\{\begin{array}[]{ll}{\rm Br}(l,0,n)&l\geq
n\\\ {\rm
Br}\left(l,\lfloor\frac{n-l}{2}\rfloor,n-\lfloor\frac{n-l}{2}\rfloor\right)&l<n,\mbox{
and }\\{\frac{n-l}{2}\\}<\frac{1}{2}\\\ {\rm
Br}\left(l,\lceil\frac{n-l}{2}\rceil,n-\lceil\frac{n-l}{2}\rceil\right)&l<n,\mbox{
and }\\{\frac{n-l}{2}\\}>\frac{1}{2}\\\ {\rm
Br}\left(l,\lfloor\frac{n-l}{2}\rfloor,n-\lfloor\frac{n-l}{2}\rfloor\right)\mbox{
or }&\\\ {\rm
Br}\left(l,\lceil\frac{n-l}{2}\rceil,n-\lceil\frac{n-l}{2}\rceil\right)&l<n,\mbox{
and }\\{\frac{n-l}{2}\\}=\frac{1}{2}.\end{array}\right.\end{split}$

Moreover

$\Lambda(l,n)=\left\\{\begin{array}[]{ll}\frac{1}{l+n}&n=0,1\\\
\frac{1}{1+nl}&l\geq n\geq 2\\\
\frac{1}{1+(l+\lfloor\frac{n-l}{2}\rfloor)(n-\lfloor\frac{n-l}{2}\rfloor)}&n\geq
2,l<n,\\{\frac{n-l}{2}\\}\leq\frac{1}{2}\\\
\frac{1}{1+(l+\lceil\frac{n-l}{2}\rceil)(n-\lceil\frac{n-l}{2}\rceil)}&n\geq
2,l<n,\\{\frac{n-l}{2}\\}>\frac{1}{2}.\end{array}\right.$

Here $\\{x\\}=x-\lfloor x\rfloor$ for $x\in\mathbb{R}$.

We now introduce the notion of minimal broom with total length $l$.

######  Definition 2.4.

For real number $l>0$, define

${\rm Br}(l)=\left\\{\begin{array}[]{ll}{\rm Br}(1,l-1)&\mbox{$l$ is an
integer}\\\ {\rm Br}(\\{l\\},\lfloor
l\rfloor)&\mbox{Otherwise}\end{array}\right.$

and

$\Lambda(l)=\lambda_{1}({\rm Br}(l)).$

By Lemma 2.2, we have the following conclusions for minimal brooms with total
length $l$.

######  Lemma 2.3.

The function $\Lambda(l)$ is strictly decreasing. More precisely,

${\rm Br}(l)=\left\\{\begin{array}[]{ll}{\rm Br}(l-\lceil l-1\rceil,\lceil
l-1\rceil,0)&l\leq 2;\\\ {\rm Br}(1,m-1,m)&l>2\mbox{ and $l=2m$ with
}m\in\mathbb{N}\\\ {\rm Br}(1,m-1,m+1)\mbox{ or}&\\\ {\rm Br}(1,m,m)&l>2\mbox{
and $l=2m+1$ with }m\in\mathbb{N}\\\ {\rm Br}(\alpha,m,m)&l=2m+\alpha\mbox{
with }m\in\mathbb{N},\alpha\in(0,1)\\\ {\rm
Br}(\alpha,m,m+1)&l=2m+1+\alpha\mbox{ with }m\in\mathbb{N},\alpha\in(0,1)\\\
\end{array}\right.$

and

$\Lambda(l)=\left\\{\begin{array}[]{ll}\frac{1}{l}&l\leq 2\\\
\frac{1}{1+m^{2}}&l>2\mbox{ and $l=2m$ with }m\in\mathbb{N}\\\
\frac{1}{1+m(m+1)}&l>2\mbox{ and $l=2m+1$ with }m\in\mathbb{N}\\\
\frac{1}{1+m(m+\alpha)}&l=2m+\alpha\mbox{ with
}m\in\mathbb{N},\alpha\in(0,1)\\\
\frac{1}{1+(m+\alpha)(m+1)}&l=2m+1+\alpha\mbox{ with
}m\in\mathbb{N},\alpha\in(0,1).\\\ \end{array}\right.$

In particular, when $l\geq 1$,

$\Lambda(l)=\frac{1}{1+\lfloor\frac{l+1}{2}\rfloor(l-\lfloor\frac{l+1}{2}\rfloor)},$

and when $l\in\mathbb{N}$,

$\Lambda(l)=\frac{1}{1+\lfloor\frac{l^{2}}{4}\rfloor}.$

Heuristically, the wedge-sum of two brooms on their roots is called a
dumbbell. For the definition of wedge-sum of graphs, see [14, 27].

######  Definition 2.5.

Let $P$ be a path of length $i$. The tree formed by adding $d_{0}$ edges and
$d_{1}$ edges adjacent to the two end vertices of $P$ respectively is called a
dumbbell with parameters $(d_{0},i,d_{1})$ and is denoted as ${\rm
DB}(d_{0},i,d_{1})$.

Next we introduce the notions of stars and combs which extend the notions of
stars and combs in [11].

######  Definition 2.6.

Let $T_{1},T_{2},\cdots,T_{r}$ be $r$ rooted trees with
$o_{1},o_{2},\cdots,o_{r}$ their roots respectively. Then, the wedge-sum of
$T_{1},T_{2},\cdots,T_{r}$ on their roots is called a star of degree $i$ with
arms $T_{1},T_{2},\cdots,T_{r}$, and is denoted as ${\rm
St}(T_{1},T_{2},\cdots,T_{r})$. The identified vertex of the roots is called
the center of the star. When $T_{i}$ is a path of length $l_{i}$ with the root
$o_{i}$ one of its end vertices for $i=1,2,\cdots,r$, ${\rm
St}(T_{1},T_{2},\cdots,T_{r})$ is simply denoted as ${\rm
St}(l_{1},l_{2},\cdots,l_{r})$. If $l_{1}=l_{2}=\cdots=l_{r}=l$, the star
${\rm St}(l_{1},l_{2},\cdots,l_{r})$ is simply denoted as ${\rm St}(r;l)$.

######  Definition 2.7.

Let $G$ be a connected subgraph of the connected graph $\widetilde{G}$. For
each $x\in V(G)$, we denote the connected component of $\widetilde{G}$ with
all the edges in $G$ deleted that containing $x$ by $\widetilde{G}_{x}$.

  1. (1)

If for any $x,y\in V(G)$ with $x\neq y$,
$\widetilde{G}_{x}\cap\widetilde{G}_{y}=\emptyset$, we call $\widetilde{G}$ a
comb over $G$. The subgraph $G$ is called the base of the comb and
$\widetilde{G}_{x}$ is called the tooth of the comb at the base vertex $x\in
V(G)$;

  2. (2)

Let $\widetilde{G}$ be a comb over $G$ and $T$ be a rooted tree with $o$ as
its root. If for each $x\in V(G)$, the tooth $(\widetilde{G}_{x},x)$ is
isomorphic to $(T,o)$ as rooted trees, then $\widetilde{G}$ is called a
regular comb over $G$ with tooth $T$ and is denoted as ${\rm Comb}(G;T)$;
Moreover, when $T$ is a path of length $l$ with one of its end vertices as the
root, $\widetilde{G}$ is simply denoted as ${\rm Comb}(G;l)$.

Similar to Lemma 4.3 in [27], the Steklov eigenvalues and eigenfunctions of a
regular comb can be computed directly as follows.

######  Lemma 2.4.

Let $\widetilde{G}={\rm Comb}(G;T)$ be a regular comb over the nontrivial
connected graph $G$ with tooth the nontrivial rooted tree $(T,o)$. Let

$0=\mu_{1}<\mu_{2}\leq\cdots\leq\mu_{|V(G)|}$

be the Laplacian eigenvalues of the connected graph $G$, and $T_{1}=T$ and
$T_{i}$ be the tree formed by adding a Dirichlet boundary edge
$\\{o^{\prime},o\\}$ of weight $\mu_{i}$ to $T$ adjacent to $o$ for
$i=2,3,\cdots,|V(G)|$. Let $f$ be an eigenfunction of
$(T_{1},L(T_{1})\setminus\\{o\\})$ when $i=1$ or
$(T_{i},L(T_{i})\setminus\\{o^{\prime}\\},\\{o^{\prime}\\})$ when $i\geq 2$,
and $g$ be an eigenfunction of $\mu_{i}(G)$. Moreover, let

(2.19) $h(v)=g(x)f(\varphi_{x}(v))$

when $v\in\widetilde{G}_{x}$ with $x\in V(G)$. Here
$\varphi_{x}:(\widetilde{G}_{x},x)\to(T,o)$ is the isomorphism of the rooted
trees. Then, $h$ is a Steklov eigenfunction for $\widetilde{G}$ with the same
eigenvalue as $f$.

###### Proof.

The conclusion is clearly true for $i=1$ by noting that $g\equiv c$ in this
case. When $i\geq 2$, for any $x\in V(G)$,

(2.20)
$\begin{split}(\Delta_{\widetilde{G}})h(x)=&(\Delta_{G}h)(x)+(\Delta_{\widetilde{G}_{x}}h)(x)\\\
=&f(o)(\Delta_{G}g)(x)+g(x)(\Delta_{T}f)(o)\\\
=&-\mu_{i}f(o)g(x)+g(x)[(\Delta_{T_{i}}f)(o)-(f(o^{\prime})-f(o))\mu_{i}]\\\
=&-\mu_{i}f(o)g(x)+\mu_{i}f(o)g(x)\\\ =&0.\end{split}$

Moreover, when $v\in\widetilde{G}_{x}$ and $v\neq x$,

(2.21)
$(\Delta_{\widetilde{G}}h)(v)=(\Delta_{\widetilde{G}_{x}}h)(v)=g(x)(\Delta_{T}f)(\varphi_{x}(v))=g(x)(\Delta_{T_{i}}f)(\varphi_{x}(v)).$

Thus, we get the conclusion of the lemma. ∎

######  Lemma 2.5.

Let $(G,B,m,w)$ be a weighted connected finite graph with boundary and
$z\in\Omega$. Let $\widetilde{G}$ be a graph formed by adding a Dirichlet
boundary edge $\\{o,z\\}$ of weight $w_{oz}$ to $G$ adjacent to $z$. Then,

(2.22) $\sigma_{2}(G)>\lambda_{1}(\widetilde{G}).$

###### Proof.

Let $f$ be an eigenfunction of $\sigma_{2}(G)$. Then, ${\left\langle
f,1\right\rangle}_{B}=0$ and

(2.23) $\sigma_{2}(G)=\frac{{\left\langle
df,df\right\rangle}_{G}}{{\left\langle f,f\right\rangle}_{B}}.$

Let $g\in\mathbb{R}^{V(\widetilde{G})}$ be such that $g|_{V(G)}=f-f(z)$ and
$g(o)=0$. Then,

(2.24) $\lambda_{1}(\widetilde{G})\leq\frac{{\left\langle
dg,dg\right\rangle}_{\widetilde{G}}}{{\left\langle
g,g\right\rangle}_{B}}=\frac{{\left\langle
df,df\right\rangle}_{G}}{{\left\langle
f,f\right\rangle}_{B}+f^{2}(z)\sum_{x\in B}m_{x}}\leq\sigma_{2}(G).$

When $\lambda_{1}(\widetilde{G})=\sigma_{2}(G)$, we know that $f(z)=0$ and $g$
is an eigenfunction of $\widetilde{G}$ for $\lambda_{1}(\widetilde{G})$.
However, this is impossible by Theorem 4.1. ∎

Combining Lemma 2.4 and Lemma 2.5, we can get
$\sigma_{|V(G)|}\left(\widetilde{G}\right)$ for $\widetilde{G}={\rm
Comb}(G;T)$.

######  Corollary 2.1.

Let $\widetilde{G}={\rm Comb}(G;T)$ and the notations be the same as in Lemma
2.4. Then,
$\sigma_{|V(G)|}(\widetilde{G})=\lambda_{1}\left(T_{|V(G)|}\right)$.

###### Proof.

By Lemma 2.5,

$\sigma_{2}(T_{1},L(T_{1})\setminus\\{o\\})>\lambda_{1}(T_{i}).$

for $i=2,3,\cdots,|V(G)|$. So, by Lemma 2.4, we know that
$\sigma_{1}(\widetilde{G})=0$ and

$\sigma_{i}(\widetilde{G})=\lambda_{1}(T_{i})$

for $i=2,3,\cdots,|V(G)|$. ∎

The following result was essentially obtained in [11] and will be used when
handling the case $i|n$ in Theorem 1.1. Here, we give a more elementary proof
of the result for completeness.

######  Proposition 2.1.

Let $G$ be a connected graph on $n\geq 2$ vertices and $P_{n}$ be a path on
$n$ vertices that are both equipped with the unit weight. Then,

(2.25) $\mu_{n}(G)\geq\mu_{n}(P_{n})=4\cos^{2}\frac{\pi}{2n}.$

The equality holds if and only $G$ is a path when $n$ is even, and is either a
cycle or a path when $n$ is odd.

###### Proof.

If there is a vertex $x\in V(G)$ such that $\deg(x)\geq 3$, let
$y_{1},y_{2},y_{3}\in V(G)$ be such that $x\sim y_{i}$ for $i=1,2,3$. Let
$f\in\mathbb{R}^{V(G)}$ be such that

(2.26) $f(v)=\left\\{\begin{array}[]{ll}-1&v=y_{1},y_{2},y_{3}\\\ 3&v=x\\\
0&\mbox{otherwise.}\end{array}\right.$

Then,

$\mu_{n}(G)\geq\frac{{\left\langle df,df\right\rangle}_{G}}{{\left\langle
f,f\right\rangle}_{G}}\geq\frac{\sum_{i=1}^{3}(f(y_{i})-f(x))^{2}}{f^{2}(x)+\sum_{i=1}^{3}f^{2}(y_{i})}=4>\mu_{n}(P_{n}).$

If for any $x\in V(G)$, $\deg(x)\leq 2$, then $G$ is either a cycle $C_{n}$ or
a path $P_{n}$. Note that

$\mu_{n}(C_{n})=4>\mu_{n}(P_{n})$

when $n$ is even and

$\mu_{n}(C_{n})=\mu_{n}(P_{n})=4\cos^{2}\frac{\pi}{2n}$

when $n$ is odd (See [2, P. 9]). So, we complete the proof of the theorem. ∎

Finally, recall the notion of geometric representation of a graph introduced
by Friedman [10].

######  Definition 2.8.

  1. (1)

Let $G$ be a simple graph. Let $K(G)$ be the one dimensional simplicial
complex with the vertex set $V(G)$ corresponding the set of 0-simplexes in
$K(G)$ and the edge set $E(G)$ corresponding the set of 1-simplexes such that
the boundary points of the 1-simplex $\\{x,y\\}$ are $x$ and $y$. Then, $K(G)$
is called the one dimensional simplicial complex representing $G$.

  2. (2)

A weight on an abstract one dimensional simplicial complex is to assign each
0-simplex a measure and each 1-simplex a length.

  3. (3)

Let $(G,m,w)$ be a weighted graph. Assign to each 0-simplex $x$ of $K(G)$ the
measure $m_{x}$ and assign to each 1-simplex $\\{x,y\\}$ of $K(G)$ the length
$l_{xy}=\frac{1}{w_{xy}}$. We will simply denote such a weighted one
dimensional simplicial complex as $(K(G),m,\frac{1}{w})$ and call it the
geometric representation of $(G,m,w)$.

  4. (4)

Let $(G,m,w)$ be a weighted graph and $K(G)$ be its geometric representation.
We then identify each 1-simplex $\\{x,y\\}$ in $K(G)$ with the interval
$[0,\frac{1}{w_{xy}}]$. Let $f\in\mathbb{R}^{V(G)}$, we denote
$\widetilde{f}:|K(G)|\to\mathbb{R}$ the piecewisely linear extension of $f$.
Here $|K(G)|$ is the underlying topological space of $K(G)$.

Note that the geometric representation $K(G)$ of a weighted graph $(G,m,w)$ is
a one dimensional Riemannian polyhedron in [21, P. 20] equipped the vertex-
measure $m$ such that the length of the 1-simplex $\\{x,y\\}$ is
$\frac{1}{w_{xy}}$. So $|K(G)|$ can be naturally viewed as a geodesic space.
For any two points $x,y\in|K(G)|$, we denote $|xy|$ the geodesic distance of
$x$ and $y$. Moreover, for any $x,y\in|K(G)|$, if $x$ and $y$ are contained in
the same edge of $K(G)$, we denote by $[xy]$ the part of that edge lying
between $x$ and $y$ (including $x$ and $y$) and $|[xy]|$ means the length of
$[xy]$.

Conversely, from a connected open set in $|K(G)|$, we can define its induced
graph.

######  Definition 2.9.

Let $(G,B,m,w)$ be a weighted finite graph with boundary $B$ and $K(G)$ be the
geometric representation of $(G,m,w)$. For any connected open subset $U$ of
$|K(G)|$, we define its induced graph $G_{U}$ as the weighted graph with
boundary and Dirichlet boundary as follows:
(1) $V(G_{U})=\\{x\in\overline{U}\ |\ x\in V(G)\ \mbox{or}\ x\in\partial
U\\}$;
(2) $E(G_{U})=\\{\\{x,y\\}\ |\ x\neq y\in V(G_{U})\ \mbox{lie on the same edge
of }|K(G)|\ \mbox{and}\ (xy)\subset U.\\},$ where
$(xy)=[xy]\setminus\\{x,y\\}$;
(3) $B_{D}(G_{U})=\partial U$;
(4) $B(G_{U})=B(G)\cap U$;
(5) for any $\\{x,y\\}\in E(G_{U})$, $w_{xy}=\frac{1}{|[xy]|}$;
(6) for any $x\in V(G_{U})$, $m_{x}=\left\\{\begin{array}[]{ll}m_{x}&x\not\in
B_{D}(G_{U})\\\ 1&x\in B_{D}(G_{U}).\end{array}\right.$

Similarly as in [11], we need the following two results when considering the
case $i|n$ in Theorem 1.1. They are essentially contained in [11]. Here, we
state them in more general settings and give their detailed proofs for
completeness.

######  Proposition 2.2.

Let $(G,m,w)$ be a weighted connected bipartite finite graph. Then, the
greatest Laplacian eigenvalue $\mu_{|V(G)|}(G)$ is of multiplicity one and its
eigenfunction $f$ must have alternating signs which means that $f(x)f(y)<0$
when $x\sim y$.

###### Proof.

Let $\varphi$ be a function on $V(G)$ taking values in $\\{1,-1\\}$ which has
alternating signs. The existence of $\varphi$ is guaranteed by that $G$ is
bipartite. Let $f$ be an eigenfunction for $\mu_{|V(G)|}$. Note that

(2.27) $\begin{split}\mu_{|V(G)|}\geq&\frac{{\left\langle
d(\varphi|f|),d(\varphi|f|)\right\rangle}_{G}}{{\left\langle\varphi|f|,\varphi|f|\right\rangle}_{G}}\\\
=&\frac{\sum_{\\{x,y\\}\in E(G)}(|f(x)|+|f(y)|)^{2}w_{xy}}{{\left\langle
f,f\right\rangle}_{G}}\\\ \geq&\frac{{\left\langle
df,df\right\rangle}_{G}}{{\left\langle f,f\right\rangle}_{G}}\\\
=&\mu_{|V(G)|}.\end{split}$

So, $\varphi|f|$ is an eigenfunction of $\mu_{|V(G)|}$.

Next, we want to show that $|f|>0$. Otherwise, there is a vertex $v$ with
$f(v)=0$ and some $x\sim v$ with $|f(x)|>0$ since $G$ is connected. Then,

(2.28) $\begin{split}0=&-\mu_{|V(G)|}\varphi(v)|f|(v)\\\
=&\Delta_{G}(\varphi|f|)(v)\\\ =&\frac{1}{m_{x}}\sum_{x\sim
v}\varphi(x)|f(x)|w_{xv}\\\ =&-\frac{\varphi(v)}{m_{x}}\sum_{x\sim
v}|f|(x)w_{xv}\\\ \neq&0\end{split}$

which is a contradiction. So $|f|>0$. Moreover, by that the inequalities in
(2.27) are equalities,

(2.29) $|f(x)|+|f(y)|=|f(x)-f(y)|$

when $x\sim y$. So $f(x)f(y)<0$ when $x\sim y$. This shows that $f$ has
alternating signs.

Suppose the multiplicity of $\mu_{|V(G)|}$ is greater than one. Then, there
are two eigenfunctions $f,g$ of $\mu_{|V(G)|}$ such that ${\left\langle
f,g\right\rangle}_{G}=0$. However, this is impossible because both $f$ and $g$
have alternating signs. This completes the proof of the theorem. ∎

######  Corollary 2.2.

Let $(G,m,w)$ be a weighted connected bipartite finite graph and $f$ be a
Laplacian eigenfunction for $\mu_{|V(G)|}(G)$. Let $K(G)$ be the geometric
representation of $G$ and for any edge $\overline{xy}$ in $|K(G)|$, let
$z_{xy}\in[xy]$ be the zero point of $\widetilde{f}$. Then, for any vertex
$x$,

(2.30) $\frac{1}{m_{x}}\sum_{y\sim
x}\frac{1}{\left|[xz_{xy}]\right|}=\mu_{|V(G)|}(G).$

###### Proof.

Note that $f(x)\neq 0$ and $w_{xy}=\frac{1}{|[xy]|}$ for any edge $\\{x,y\\}$.
So

(2.31) $\begin{split}\mu_{|V(G)|}(G)f(x)=&-(\Delta_{G}f)(x)\\\
=&\frac{1}{m_{x}}\sum_{y\sim x}\frac{f(x)-f(y)}{|[xy]|}\\\
=&\frac{1}{m_{x}}\sum_{y\sim
x}\frac{\widetilde{f}(x)-\widetilde{f}(z_{xy})}{|[xz_{xy}]|}\\\
=&\frac{1}{m_{x}}\sum_{y\sim x}\frac{1}{|[xz_{xy}]|}f(x).\end{split}$

Hence, $\frac{1}{m_{x}}\sum_{y\sim x}\frac{1}{|[xz_{xy}]|}=\mu_{|V|}(G)$. ∎

##  3\. A monotonicity of Steklov eigenvalues

In this section, we prove Theorem 1.2 and discuss the rigidity when the
equalities of (1.1) hold.

###### Proof of Theorem 1.2.

Let
$\varphi_{1}=1,\varphi_{2},\cdots,\varphi_{|\widetilde{B}|}\in\mathbb{R}^{V(\widetilde{G})}$
be an orthogonal system of eigenfunctions of the DtN map for
$(\widetilde{G},\widetilde{B})$ such that $\varphi_{i}$ is an eigenfunction of
$\sigma_{i}(\widetilde{G})$ for $i=1,2,\cdots|\widetilde{B}|$. Let
$\psi_{1}=1,\psi_{2},\cdots,\psi_{|B|}\in\mathbb{R}^{V(G)}$ be an orthogonal
system of eigenfunctions of the DtN maps for $(G,B)$ such that $\psi_{i}$ is
an eigenfunction of $\sigma_{i}(G)$ for $i=1,2,\cdots,|B|$. For each $2\leq
i\leq|\widetilde{B}|$, let

$\varphi=c_{1}\varphi_{1}+c_{2}\varphi_{2}+\cdots+c_{i}\varphi_{i}$

with $c_{1},c_{2},\cdots,c_{i}$ not all zero such that

(3.1) ${\left\langle\varphi,\psi_{j}\right\rangle}_{B}=0$

for $j=1,2,\cdots,i-1$. The existence of such $c_{1},c_{2},\cdots,c_{i}$ comes
from the fact that (3.1) with $j=1,2\cdots,i-1$ form a linear homogeneous
system with $i-1$ equations on $i$ unknowns: $c_{1},c_{2},\cdots,c_{i}$ which
certainly has nonzero solutions. Then, by that $E(G)\subset E(\widetilde{G})$
and $\widetilde{B}\subset B$,

(3.2)
$\begin{split}\sigma_{i}(\widetilde{G},\widetilde{B})\geq\frac{{\left\langle
d\varphi,d\varphi\right\rangle}_{\widetilde{G}}}{{\left\langle\varphi,\varphi\right\rangle}_{\widetilde{B}}}\geq\frac{{\left\langle
d\varphi,d\varphi\right\rangle}_{G}}{{\left\langle\varphi,\varphi\right\rangle}_{B}}\geq\sigma_{i}(G,B).\end{split}$

This completes the proof of the first part of the theorem.

When $\widetilde{G}$ is a combinatorial finite graph and $G$ is its spanning
subgraph, it is clear that $B(G)\supset B(\widetilde{G})$. So, the conclusion
follows. This completes the proof of the theorem. ∎

For completeness, we also discuss the rigidity for (1.1) to hold for all
$i=1,2\cdots,|\widetilde{B}|$.

######  Theorem 3.1.

Let $(\widetilde{G},\widetilde{B},m,w)$ be a weighted connected finite graph
with $|\widetilde{B}|\geq 2$ and $(G,B)$ be such that $G$ is a connected
subgraph of $\widetilde{G}$ and $B\supset\widetilde{B}$. Then, the equalities
of (1.1) hold for all $i=1,2,\cdots,|\widetilde{B}|$ if and only if all the
following statements are true:

  1. (1)

$B\setminus\widetilde{B}\subset Z(\widetilde{G})$;

  2. (2)

for any $u\in H(\widetilde{G})$, $u|_{V(\widetilde{G}_{x})}$ is a constant for
any $x\in V(G)$;

  3. (3)

for any $v\in\mathbb{R}^{V(G)}$ with ${\left\langle v,1\right\rangle}_{B}=0$
and $v|_{\widetilde{B}}$ being constant,

(3.3) ${\left\langle
dv,dv\right\rangle}_{G}\geq\sigma_{|\widetilde{B}|}(\widetilde{G}){\left\langle
v,v\right\rangle}_{B}.$

Here

$H(\widetilde{G})=\\{f\in\mathbb{R}^{V(\widetilde{G})}\ |\
(\Delta_{\widetilde{G}}f)|_{\Omega(\widetilde{G})}=0,\ \mbox{and}\
{\left\langle f,1\right\rangle}_{\widetilde{B}}=0.\\}$

and

$Z(\widetilde{G})=\\{x\in\Omega(\widetilde{G})\ |\ f(x)=0\ \mbox{for any }f\in
H(\widetilde{G}).\\}.$

In particular, if $B=\widetilde{B}$ and $H(\widetilde{G})$ separating vertices
in $V(G)$, then the equalities of (1.1) hold for
$i=1,2,\cdots,|\widetilde{B}|$ if and only if $\widetilde{G}$ is a comb over
$G$.

###### Proof.

If equalities of (1.1) hold for $i=1,2,\cdots,|\widetilde{B}|$, we first
claim: _There are $|\widetilde{B}|$ functions
$u_{1}=1,u_{2},\cdots,u_{|\widetilde{B}|}\in\mathbb{R}^{V(\widetilde{G})}$
such that_

  1. (i)

$u_{i}$_is an eigenfunction for_ $\sigma_{i}(\widetilde{G},\widetilde{B})$ for
$i=1,2,\cdots,|\widetilde{B}|$;

  2. (ii)

$v_{i}:=u_{i}|_{V(G)}$_is an eigenfunction for_ $\sigma_{i}(G,B)$ for
$i=1,2,\cdots,|\widetilde{B}|$;

  3. (iii)

$u_{i}|_{B\setminus\widetilde{B}}=0$_for_ $i=2,3,\cdots,|\widetilde{B}|$;

  4. (iv)

$u_{i}(x)=u_{i}(y)$_for any edge_ $\\{x,y\\}\in E(\widetilde{G})\setminus
E(G)$ and $i=1,2,\cdots,|\widetilde{B}|$;

  5. (v)

${\left\langle u_{i},u_{j}\right\rangle}_{B}=0$_for_ $1\leq
j<i\leq|\widetilde{B}|$.

We will show the claim by induction. For $i\geq 2$, suppose that
$u_{1}=1,u_{2},\cdots,u_{i-1}$ has been constructed. Let

$u_{i}=c_{1}\varphi_{1}+c_{2}\varphi_{2}+\cdots+c_{i}\varphi_{i}$

with $c_{1},c_{2},\cdots,c_{i}$ are constants not all zero such that

(3.4) ${\left\langle u_{i},u_{j}\right\rangle}_{B}=0$

for $j=1,2,\cdots,i-1$. Here
$\varphi_{1},\varphi_{2},\cdots,\varphi_{|\widetilde{B}|}$ are the same as in
the proof of Theorem 1.2. For the same reason as before, the existence of such
constants is clear. Then,

(3.5)
$\begin{split}\sigma_{i}(G,B)=\sigma_{i}(\widetilde{G},\widetilde{B})\geq\frac{{\left\langle
du_{i},du_{i}\right\rangle}_{\widetilde{G}}}{{\left\langle
u_{i},u_{i}\right\rangle}_{\widetilde{B}}}\geq\frac{{\left\langle
du_{i},du_{i}\right\rangle}_{G}}{{\left\langle
u_{i},u_{i}\right\rangle}_{B}}\geq\sigma_{i}(G,B).\end{split}$

So, the above inequalities are all equalities which implies that $u_{i}$
satisfies the above properties (i)–(v). This completes the proof of the claim.

Note that

$H(\widetilde{G})={\rm Span}\\{u_{2},u_{3},\cdots,u_{|\widetilde{B}|}\\}.$

So, we get (1) and (2) by (iii) and (iv). Conversely, when (1) and (2) are
true, for any eigenfunction $u\in\mathbb{R}^{V(\widetilde{G})}$ of
$\sigma_{i}(\widetilde{G})$ with $i\geq 2$, $v=u|_{V(G)}$ is an eigenfunction
of $\sigma_{i}(\widetilde{G})$ since

(3.6) $\Delta_{G}v(x)=\Delta_{\widetilde{G}}u(x)$

for any $x\in V(G)$. Thus, under the assumption of (1) and (2), the equalities
of (1.1) hold for $i=1,2,\cdots,|\widetilde{B}|$ if and only if for any
$v\in\mathbb{R}^{V(G)}$ with

(3.7) ${\left\langle v,u_{i}\right\rangle}_{B}=0$

for $i=1,2,\cdots,|\widetilde{B}|$,

(3.8) ${\left\langle
dv,dv\right\rangle}_{G}\geq\sigma_{|\widetilde{B}|}(\widetilde{G}){\left\langle
v,v\right\rangle}_{B}.$

By (iii), we know that

${\left\langle v,u_{i}\right\rangle}_{\widetilde{B}}={\left\langle
v,u_{i}\right\rangle}_{B}=0$

for $i=2,\cdots,|\widetilde{B}|$. So $v|_{\widetilde{B}}$ is constant. This
completes the proof of the first conclusion the theorem.

When $H(\widetilde{G})$ separating vertices in $V(G)$, by (2), we know that

$\widetilde{G}_{x}\cap\widetilde{G}_{y}=\emptyset$

for any $x\neq y\in V(G)$ if the equalities of (1.1) hold for
$i=1,2,\cdots,|\widetilde{B}|$. So, $\widetilde{G}$ is a comb over $G$.
Conversely, it is clear that if $\widetilde{G}$ is a comb over $G$ and
$B=\widetilde{B}$, then the equalities of (1.1) hold for
$i=1,2,\cdots,|\widetilde{B}|$. This completes the proof of the theorem. ∎

When considering the rigidity of the case $n=im+1$ in Theorem 1.1, we need the
following result.

######  Lemma 3.1.

Let $\widetilde{G}$ be a nontrivial connected combinatorial graph and $G$ be
its spanning tree. Suppose that the first positive Steklov eigenvalue is of
multiplicity $i-1$ for some $2\leq i\leq|B(G)|$. Suppose that
$\sigma_{i}(\widetilde{G})=\sigma_{i}(G)$ and

  1. (1)

$H_{1}(G)$ separates vertices in $\Omega(G)$, and

  2. (2)

for any $x\in B(G)$, there is a function $f\in H_{1}(G)$ such that $f(x)\neq
0$,

where $H_{1}(G)$ be the eigenspace of the first positive Steklov eigenvalue of
$G$. Then, $\widetilde{G}=G$.

###### Proof.

We only need to prove the result for $|V(G)|\geq 3$.

Because $\sigma_{i}(\widetilde{G})=\sigma_{i}(G)=\sigma_{2}(G)$, by Theorem
1.2, we know that

(3.9) $\sigma_{j}(\widetilde{G})=\sigma_{j}(G)=\sigma_{2}(G)$

for $j=2,3,\cdots,i$. Then, by the same argument as in the proof of Theorem
3.1, there are $u_{1}\equiv 1,u_{2},\cdots,u_{i}\in\mathbb{R}^{V(G)}$ such
that

  1. (i)

$u_{j}$ is an eigenfunction both for $G$ and $\widetilde{G}$ with respect to
$\sigma_{j}(G)$ for $j=1,2,\cdots,i$;

  2. (ii)

$u_{j}|_{B(G)\setminus B(\widetilde{G})}=0$ for $j=2,3,\cdots,i$;

  3. (iii)

$u_{j}(x)=u_{j}(y)$ for any edge $\\{x,y\\}\in E(\widetilde{G})\setminus E(G)$
and $j=2,3,\cdots,i$;

  4. (iv)

${\left\langle u_{j},u_{k}\right\rangle}_{B(G)}=0$ for $1\leq j<k\leq i$.

Note that $H_{1}(G)$ is generated by $u_{2},u_{3},\cdots,u_{i}$. By assumption
(2) and (ii), we know that $B(G)=B(\widetilde{G})$. Moreover, by assumption
(1) and (iii), for any $x\neq y\in\Omega(G)$,
$\widetilde{G}_{x}\cap\widetilde{G}_{y}=\emptyset$. This implies that
$\widetilde{G}=G$ since $G$ is a spanning subgraph of $\widetilde{G}$. ∎

##  4\. First Steklov eigenfunction with Dirichlet boundary data and Steklov
nodal domains

In this section, we extend the Friedman’s theory of nodal domains for
Laplacian eigenfunctions to Steklov eigenfunctions. We first show the first
Steklov eigenfunction with vanishing Dirichlet boundary data is positive and
the first eigenvalue is of multiplicity one which is a discrete version of
Courant’s result for Steklov eigenvalues.

######  Theorem 4.1.

Let $(G,B,B_{D},m,w)$ be a weighted connected finite graph with boundary $B$
and Dirichlet boundary $B_{D}$. Suppose that the induced subgraph
$G[\Omega_{D}]$ of $G$ on $\Omega_{D}$ is connected. Then, the eigenfunctions
of $\lambda_{1}(G,B,B_{D})$ must be everywhere positive or everywhere negative
in $\Omega_{D}$.

###### Proof.

Let $f_{0}\in\mathbb{R}^{V(G)}$ be an eigenfunction for
$\lambda_{1}(G,B_{N},B_{D})$. Then, $f_{0}$ is the minimum of the Rayleigh
quotient

(4.1) $R_{0}[f]=\frac{{\left\langle df,df\right\rangle}_{G}}{{\left\langle
f,f\right\rangle}_{B}}$

among all $f\in\mathbb{R}^{V(G)}$ with $f|_{B}\not\equiv 0$ and
$f|_{B_{D}}\equiv 0$. First, note that

(4.2) $\begin{split}{\left\langle
d|f|,d|f|\right\rangle}_{G}=&\sum_{\\{x,y\\}\in
E(G)}(|f|(x)-|f|(y))^{2}w_{xy}\\\ \leq&\sum_{\\{x,y\\}\in
E(G)}(f(x)-f(y))^{2}w_{xy}\\\ =&{\left\langle
df,df\right\rangle}_{G}\end{split}$

with strictly inequality when for some edge $\\{x,y\\}$, $f(x)<0<f(y)$.
Moreover,

(4.3) ${\left\langle
f_{0},f_{0}\right\rangle}_{B}={\left\langle|f_{0}|,|f_{0}|\right\rangle}_{B}.$

So, $|f_{0}|$ is also a first eigenfunction and

(4.4) ${\left\langle df_{0},df_{0}\right\rangle}_{G}={\left\langle
d|f_{0}|,d|f_{0}|\right\rangle}_{G}.$

We then only need to show that $|f_{0}|>0$ on $\Omega_{D}$. Otherwise, because
$f_{0}\not\equiv 0$ and $G[\Omega_{D}]$ is connected, there is a vertex
$v\in\Omega_{D}$, so that $|f_{0}|(v)=0$ and $|f_{0}|(x)>0$ for some
$x\in\Omega_{D}$ with $x\sim v$. If $v\in\Omega$, then

(4.5) $0=\Delta_{G}|f_{0}|(v)=\frac{1}{m_{v}}\sum_{y\sim
v}(|f_{0}|(y)-|f_{0}|(v))w_{vy}=\frac{1}{m_{v}}\sum_{y\sim
v}|f_{0}|(y)w_{vy}>0$

which is a contradiction. If $v\in B$, then

(4.6) $0=\lambda_{1}|f_{0}|(v)=\frac{\partial|f_{0}|}{\partial
n}(v)=-\frac{1}{m_{v}}\sum_{y\sim v}|f_{0}|(y)w_{vy}<0$

which is also a contradiction. This completes the proof of the theorem. ∎

By Theorem 4.1, we have the following straight forward consequence.

######  Corollary 4.1.

Let $(G,B,B_{D},m,w)$ be a weighted connected finite graph with boundary $B$
and Dirichlet boundary $B_{D}$. Suppose that the induced subgraph
$G[\Omega_{D}]$ is connected. Then, $\lambda_{1}(G,B,B_{D})$ is of
multiplicity one and any higher eigenfunctions must change signs.

###### Proof.

If $\lambda_{1}$ is not of multiplicity one, then by Theorem 4.1, there are
two eigenfunctions $f_{1}|_{B}>0,f_{2}|_{B}>0$ of $\lambda_{1}$ such that
${\left\langle f_{1},f_{2}\right\rangle}_{B}=0$. This is ridiculous. So,
$\lambda_{1}$ is of multiplicity one. Let $f$ be an eigenfunction for
$\lambda_{1}$ with $f|_{B}>0$, and $g$ be an eigenfunction for $\lambda_{i}$
with $i\geq 2$, then ${\left\langle f,g\right\rangle}_{B}=0$ implies that $g$
must change signs on $B$. This completes the proof of the corollary. ∎

The following result shows that the assumption on the connectivity of
$G[\Omega_{D}]$ is necessary for the conclusion of Theorem 4.1.

######  Proposition 4.1.

Let $(G,B,B_{D},m,w)$ be a weighted connected finite graph with boundary $B$
and Dirichlet boundary $B_{D}$. Let $G_{1},G_{2},\cdots,G_{k}$ be the
connected components of $G[\Omega_{D}]$, $\widetilde{G}_{i}=G[V(G_{i})\cup
B_{D}]$ and $B_{i}=B\cap V(G_{i})$ for $i=1,2,\cdots,k$. Then,

${\rm Spec}(G,B,B_{D})=\sqcup_{i=1}^{k}{\rm
Spec}(\widetilde{G}_{i},B_{i},B_{D}).$

Here ${\rm Spec}(G,B,B_{D})$ is the collection of all the Steklov eigenvalues
with vanishing Dirichlet boundary data on $(G,B,B_{D},m,w)$ counting
multiplicities and $\sqcup$ means disjoint union.

###### Proof.

Note that any eigenfunction of $(\widetilde{G}_{i},B_{i},B_{D})$ is an
eigenfunction of $(G,B,B_{D})$ with the same eigenvalue after zero extension.
This proves the conclusion. ∎

Next, we give the definition of nodal domains for Steklov eigenfunctions.

######  Definition 4.1.

Let $(G,B,m,w)$ be a weighted connected finite graph with boundary and $K(G)$
be its geometric representation. Let $f\in\mathbb{R}^{V(G)}$ be a Steklov
eigenfunction of $(G,B,m,w)$ and $U$ be a connected component of
$|K(G)|\setminus\widetilde{f}^{-1}(0)$. Then, $U$ or it induced graph $G_{U}$
are both called a nodal domain of $f$.

We first confirm some elementary properties of nodal domains.

######  Proposition 4.2.

Let $(G,B,m,w)$ be a weighted connected finite graph with boundary,
$f\in\mathbb{R}^{V(G)}$ be an Steklov eigenfunction of $(G,B,m,w)$ and $U$ be
a nodal domain of $f$. Then $\Omega_{D}(G_{U})\neq\emptyset$,
$G_{U}[\Omega_{D}(G_{U})]$ is connected, and $B(G_{U})\neq\emptyset$.

###### Proof.

By definition of $U$, there is a vertex $v\in U$ such that $f(v)\neq 0$. Then
$v\in\Omega_{D}(G_{U})$. So $\Omega_{D}(G_{U})\neq\emptyset$. Moreover,
because $U$ is path connected, $G_{U}[\Omega_{D}(G_{U})]$ is a connected
graph.

Finally, if $B(G_{U})=\emptyset$, let $g=\widetilde{f}|_{V(G_{U})}$. Then, for
any $x\in V(G_{U})\setminus B_{D}(G_{U})$, $x\in\Omega(G)$. Thus
$\Delta_{G}f(x)=0$. Furthermore, because $f(x)\neq 0$, for any $y\in V(G)$
adjacent to $x$, either $\\{x,y\\}\in E(G_{U})$ or there is a point $z_{y}$ in
the edge $[xy]$ such that $\widetilde{f}(z_{y})=0$ and $\\{x,z_{y}\\}\in
E(G_{U})$ with weight $\frac{1}{|[xz_{y}]|}$. In the later case, we have

(4.7)
$\frac{\widetilde{f}(z_{y})-\widetilde{f}(x)}{|[xz_{y}]|}=\frac{\widetilde{f}(y)-\widetilde{f}(x)}{|[xy]|}=(f(y)-f(x))w_{xy}.$

Therefore,

(4.8) $\begin{split}\Delta_{G_{U}}g(x)=\Delta_{G}f(x)=0\end{split}$

for any $x\in V(G_{U})\setminus B_{D}(G_{U})$. So $g$ as the solution of the
following boundary value problem:

(4.9) $\left\\{\begin{array}[]{ll}\Delta_{G_{U}}g(x)=0&x\in V(G_{U})\setminus
B_{D}(G_{U})\\\ g(x)=0&x\in B_{D}(G_{U}),\end{array}\right.$

must be vanishing. This is a contradiction. So $B(G_{U})\neq\emptyset$. This
completes the proof of the proposition. ∎

At the end of this section, we extend Friedman’s nodal domain theorem in [10]
for Laplacian eigenfunctions to the case of Steklov eigenfunctions. They are
both discrete analogue of Courant’s nodal domain theorem.

######  Theorem 4.2.

Let $(G,B,m,w)$ be a weighted connected finite graph with boundary and
$f\in\mathbb{R}^{V(G)}$ be a Steklov eigenfunction of $G$ with eigenvalue
$\sigma>0$. Then, for each nodal domain $U$ of $f$,
$\lambda_{1}(G_{U})=\sigma$.

###### Proof.

By the same argument as in the proof of Proposition 4.2 using (4.7), we know
that $\widetilde{f}|_{V(G_{U})}$ is a Steklov eigenfunction for $G_{U}$ with
vanishing Dirichlet boundary data on $B_{D}(G_{U})$ with respect to the
eigenvalues $\sigma$. Moreover $\widetilde{f}|_{\Omega_{D}(G_{U})}$ does not
change sign because $U$ is a nodal domain. Then, by Corollary 4.1 and
Proposition 4.2, we know that $\widetilde{f}|_{V(G_{U})}$ is an eigenfunction
for $\lambda_{1}(G_{U})$. ∎

##  5\. A lower bound for first Steklov eigenvalue with Dirichlet boundary
data

In this section, we first obtain a crucial lower bound for the first Steklov
eigenvalues with vanishing Dirichlet boundary data on trees extending Lemma
3.1 in [11] to the case of Steklov eigenvalues. Then, as an application of the
lower bound, we give more explicit sufficient condition for the rigidity of
the isodiametric estimates by He-Hua [14] and its extension by the authors
[27].

######  Theorem 5.1.

Let $(G,B,B_{D},m,w)$ be a weighted finite tree with boundary $B\neq\emptyset$
and Dirichlet boundary $B_{D}\neq\emptyset$ such that $L(G)=B\cup B_{D}$ and
$G[\Omega_{D}]$ is a tree with unit weight and $|\Omega_{D}|=n+1$ with $n\geq
1$. Then,

(5.1) $\lambda_{1}(G,B,B_{D})\geq\Lambda(l,n).$

The equality of the inequality holds if and only if $G[\Omega]$ is a path of
length $I(l,n)$ and all the Dirichlet boundary vertices are adjacent to the
same end vertex of the path and the other boundary vertices are adjacent to
the other end vertex of the path. Here

$I(l,n)=\left\\{\begin{array}[]{ll}0&l\geq n\\\
\lfloor\frac{n-l}{2}\rfloor&l<n,\mbox{ and }\\{\frac{n-l}{2}\\}<\frac{1}{2}\\\
\lceil\frac{n-l}{2}\rceil&l<n,\mbox{ and }\\{\frac{n-l}{2}\\}>\frac{1}{2}\\\
\lfloor\frac{n-l}{2}\rfloor\mbox{ or }\lceil\frac{n-l}{2}\rceil&l<n,\mbox{ and
}\\{\frac{n-l}{2}\\}=\frac{1}{2}.\end{array}\right.$

In particular, when $|B_{D}|=1$, the equality holds if and only if $G$ is a
minimal broom ${\rm Br}(l,n)$. Here

$l=\frac{1}{\sum_{x\in B_{D},y\in\Omega_{D}}w_{xy}}.$

###### Proof.

We first consider the case $|B_{D}|=1$. Let $f\in\mathbb{R}^{V(G)}$ be an
eigenfunction for $\lambda_{1}$. Then, by Theorem 4.1, we can assume that
$f>0$ on $\Omega_{D}$.

Let $B_{D}=\\{o\\}$ and take $o$ as the root of the tree $G$. we first claim
that _ $f$ is increasing along the tree. More precisely, if $x$ is the parent
of $y$, then $f(x)\leq f(y)$._ Indeed, if this is not true, i.e. $f(x)>f(y)$,
let

(5.2) $g(z)=\left\\{\begin{array}[]{ll}f(z)+2(f(x)-f(y))&\mbox{$z=y$ or $z$ is
a descendant of $y$ }\\\ f(z)&\mbox{otherwise}\end{array}\right.$

Then,

(5.3) ${\left\langle dg,dg\right\rangle}_{G}={\left\langle
dg,dg\right\rangle}_{G}$

and

(5.4) ${\left\langle g,g\right\rangle}_{B}>{\left\langle
f,f\right\rangle}_{B}$

and $g(o)=0$. So,

$\frac{{\left\langle dg,dg\right\rangle}_{G}}{{\left\langle
g,g\right\rangle}_{B}}<\frac{{\left\langle
df,df\right\rangle}_{G}}{{\left\langle f,f\right\rangle}_{B}}$

which contradicts that $f$ is the eigenfunction for $\lambda_{1}$.

Next, we claim that _$f$ is strictly increasing._ In fact, when $x$ is the
parent of $y\in B$,

(5.5) $\begin{split}0<\lambda_{1}f(y)=\frac{\partial f}{\partial
n}(y)=f(y)-f(x).\end{split}$

So, $f(x)<f(y)$. Therefore, if the claim is not true, then there are three
vertices $x,y,z$ such that $x$ is the parent of $y$ and $y$ is the parent of
$z$ with $f(x)=f(y)$ and $f(y)<f(z)$. Note that $y\in\Omega$ since $y$ is not
a leaf. Then

$\begin{split}0=&\Delta_{G}f(y)\\\ =&(f(x)-f(y))+(f(z)-f(y))+\sum_{v\neq
x,z}(f(v)-f(y))w_{vy}\\\ \geq&f(z)-f(y)>0\end{split}$

since $f(v)\geq f(y)$ by that $f$ is increasing. This is a contradiction.

Let $G_{0}$ be a tree satisfying the assumption in the statement of the
theorem achieving the minimum of $\lambda_{1}$ when $|\Omega_{D}|$ and the
weight of the Dirichlet boundary edge are fixed ($G_{0}$ must exist because
the number of such kind of trees is finite.). Let $f_{0}$ be the eigenfunction
for $\lambda_{1}$ with $f_{0}>0$ on $\Omega_{D}(G_{0})$. By the claims before,
we know that $f_{0}$ is strictly increasing when taking the Dirichlet boundary
vertex $o$ as the root.

We first claim that _$G_{0}[\Omega(G_{0})]$ must be a path and $o$ is adjacent
to one of the end vertices of the path._ Otherwise, there are
$x,y,z\in\Omega(G_{0})$ such that $x$ is the parent of $y$ and $z$. Suppose
that $f_{0}(y)\geq f_{0}(z)$. Let $G^{\prime}$ be the tree obtained by
removing the edge $\\{x,y\\}$ and adding a new edge $\\{y,z\\}$ on $G$. Then,

$\frac{{\left\langle df_{0},df_{0}\right\rangle}_{G^{\prime}}}{{\left\langle
f_{0},f_{0}\right\rangle}_{B(G^{\prime})}}=\frac{{\left\langle
df_{0},df_{0}\right\rangle}_{G_{0}}-(f_{0}(y)-f_{0}(x))^{2}+(f_{0}(y)-f_{0}(z))^{2}}{{\left\langle
f_{0},f_{0}\right\rangle}_{B(G_{0})}}<\frac{{\left\langle
df_{0},df_{0}\right\rangle}_{G_{0}}}{{\left\langle
f_{0},f_{0}\right\rangle}_{B(G_{0})}}.$

since $0<f_{0}(x)<f_{0}(z)\leq f_{0}(y)$. This contradicts that $G_{0}$
achieves the minimum of $\lambda_{1}$.

We next claim that _all the leaves in $B(G_{0})$ must be adjacent to the other
end vertex of the path $G_{0}[\Omega(G_{0})]$ (i.e. the end vertex of
$G_{0}[\Omega(G_{0})]$ not adjacent to $o$ when $G_{0}[\Omega(G_{0})]$ is a
nontrivial path)._ Otherwise, let $v$ be the other end vertex of
$G_{0}[\Omega(G_{0})]$, and suppose there is a leave $x\in B(G_{0})$ adjacent
to some vertex $y\in\Omega(G_{0})\setminus\\{v\\}$. By that $f_{0}$ is
strictly increasing, we know that

(5.6) $f_{0}(x)>f_{0}(y)\ \mbox{and}\ f_{0}(v)>f_{0}(y).$

Let $G^{\prime}$ be the graph formed by removing the edge $\\{x,y\\}$ from
$G_{0}$ and adding the edge $\\{x,v\\}$ and $f$ be such that

$f(x)=f_{0}(x)-f_{0}(y)+f_{0}(v)>f_{0}(x)$

and $f(z)=f_{0}(z)$ for $z\neq x$. Then,

(5.7) $\frac{{\left\langle df,df\right\rangle}_{G^{\prime}}}{{\left\langle
f,f\right\rangle}_{B(G^{\prime})}}<\frac{{\left\langle
df_{0},df_{0}\right\rangle}_{G}}{{\left\langle
f_{0},f_{0}\right\rangle}_{B(G_{0})}}=\lambda_{1}(G_{0}).$

This contradicts that $G_{0}$ achieves the minimum of $\lambda_{1}$.

Thus, $G_{0}$ must be a minimal broom ${\rm Br}(l,n)$. This completes the
proof of the theorem when $|B_{D}|=1$.

When $|B_{D}|\geq 2$, let $G_{0}$ be the tree has the minimal $\lambda_{1}$
among all trees satisfying the assumptions in the statement of the theorem and
with $|\Omega_{D}|$, $|B_{D}|$ and the weights of Dirichlet boundary edges are
fixed. Let $f_{0}$ be a first Dirichlet eigenfunction such that
$f_{0}|_{\Omega_{D}(G_{0})}>0$. Let $v\in\Omega(G_{0})$ with

$f(v)=\min_{x\in\Omega(G_{0})}f(x).$

Let $G^{\prime}$ be the tree by moving all the Dirichlet boundary edges of
$G_{0}$ to $v$. Then,

(5.8) $\frac{{\left\langle
df_{0},df_{0}\right\rangle}_{G^{\prime}}}{{\left\langle
f_{0},f_{0}\right\rangle}_{B(G^{\prime})}}\leq\frac{{\left\langle
df_{0},df_{0}\right\rangle}_{G}}{{\left\langle
f_{0},f_{0}\right\rangle}_{B(G_{0})}}=\lambda_{1}(G_{0}).$

So, $G^{\prime}$ is also a tree achieving the minimum of $\lambda_{1}$. Let
$G^{\prime\prime}$ be the tree by removing all the the Dirichlet boundary
edges of $G^{\prime}$ and adding a Dirichlet boundary edge to $v$ with the
weight equal to the total weight of all the removed Dirichlet boundary edges.
Then, it is clear that
$\lambda_{1}(G^{\prime\prime})=\lambda_{1}(G^{\prime})$. Now, we have reduced
to the case that $|B_{D}|=1$ and complete the proof of the theorem. ∎

As an application of Theorem 5.1, we can give a more explicit sufficient
condition for the rigidity of the isodiametric estimate in [14] and its
extension in [27]. First recall the estimate.

######  Theorem 5.2.

For $r\geq 2$ and $l\geq 1$, let $\widetilde{G}$ be a finite tree containing
${\rm St}(r;l)$ as a subtree. Then,

(5.9) $\sigma_{i}(\widetilde{G})\leq\frac{1}{l}$

for $i=2,3,\cdots,r$. Moreover, the equality holds for $i=2$ if and only if
$\widetilde{G}={\rm St}(r;l)\vee_{o}\widetilde{G}_{o}$ with
$\lambda_{1}\left(\widetilde{G}_{o},L(\widetilde{G}_{o})\setminus\\{o\\},\\{o\\}\right)\geq\frac{1}{l}$.
Here $o$ is the center of the star ${\rm St}(r;l)$.

Now, by Theorem 5.1 and Proposition 4.1. we have the following conclusion.

######  Corollary 5.1.

Let $r\geq 2$ and $l\geq 1$ and let $\widetilde{G}={\rm
St}(r;l)\vee_{o}\widetilde{G}_{o}$ be such that each branch of
$\widetilde{G}_{o}$ with respect to $o$ has no more than
$\left\lfloor\sqrt{4(l-1)+1}\right\rfloor$ edges when taking $o$ as the root
of $\widetilde{G}_{o}$. Then, $\sigma_{2}(\widetilde{G})=\frac{1}{l}$.

###### Proof.

Let $\widetilde{G}_{1},\cdots,\widetilde{G}_{k}$ are the branches of
$\widetilde{G}_{o}$. Then, by Theorem 5.1,

(5.10)
$\lambda_{1}(\widetilde{G}_{i},L(\widetilde{G}_{i})\setminus\\{o\\},\\{o\\})\geq\Lambda(|E(\widetilde{G}_{i})|)=\frac{1}{1+\left\lfloor\frac{|E(\widetilde{G}_{i})|^{2}}{4}\right\rfloor}\geq\frac{1}{l}.$

So, by Proposition 4.1,

(5.11)
$\lambda_{1}(\widetilde{G}_{o},L(\widetilde{G}_{o})\setminus\\{o\\},\\{o\\})\geq\frac{1}{l}.$

This completes the proof of the theorem. ∎

##  6\. Clump numbers of trees

In this section, we recall the definition of the clump number of a tree in
[11] and introduce some of its properties.

######  Definition 6.1.

Let $G$ be a finite combinatorial tree and $K(G)$ be its geometry
representation. For any $p\in|K(G)|$, the connected components
$U_{1},U_{2},\cdots,U_{k}$ (or their corresponding trees
$G_{U_{1}},G_{U_{2}},\cdots,G_{U_{k}}$) of $|K(G)|\setminus\\{p\\}$ are called
the clumps of $G$ with respect to $p$. The clump number of $G$ with respect to
$p$ is defined as

${\rm Clump}(G,p)=\max\\{{\rm Length}(U_{1}),{\rm Length}(U_{2}),\cdots,{\rm
Length}(U_{k})\\}$

where ${\rm Length}(U_{i})$ is the total length of $U_{i}$. Moreover, the
clump number of $G$ is defined to be

(6.1) ${\rm Clump}(G)=\inf_{p\in|K(G)|}{\rm Clump}(G,p).$

We have the following properties for ${\rm Clump}(G,p)$.

######  Proposition 6.1.

Let $G$ be a finite combinatorial tree and $K(G)$ be its geometric
representation. Then,

  1. (1)

${\rm Clump}(G,p)$ is a lower semi-continuous function for $p\in|K(G)|$. Thus
there is a point $p\in|K(G)|$ such that ${\rm Clump}(G)={\rm Clump}(G,p)$;

  2. (2)

the point $p\in|K(G)|$ such that ${\rm Clump}(G)={\rm Clump}(G,p)$ is either a
vertex or a mid-point of an edge. Thus, ${\rm Clump}(G)$ is either an integer
or a half-integer.

  3. (3)

if $p\in|K(G)|$ is a mid-point of some edge such that ${\rm Clump}(G)={\rm
Clump}(G,p)$, then the clumps of $G$ with respect to $p$ are two clumps of
equal total length $\frac{|E(G)|}{2}$;

  4. (4)

there is unique point $p\in|K(G)|$ such that ${\rm Clump}(G)={\rm
Clump}(G,p)$. We called the point $p$ the equilibrium point of $G$.

###### Proof.

(1) When $p$ is not a vertex of $K(G)$, it is clear that ${\rm Clump}(G,p)$ is
continuous at $p$ by definition. When $p$ is a vertex of $K(G)$, let
$U_{1},U_{2},\cdots,U_{k}$ be all the clumps of $p$ and suppose that $U_{1}$
has the maximal total length among the $k$ clumps. Then, for any
$\epsilon\in(0,1)$ and $x\in B_{p}(\epsilon)\cap U_{i}$ with $i=2,3,\cdots,k$,

(6.2) ${\rm Clump}(G,x)\geq{\rm Clump}(G,p)\geq{\rm Clump}(G,p)-\epsilon$

because there is a clump of $x$ containing $U_{1}$. Moreover, for any $x\in
B_{p}(\epsilon)\cap U_{1}$, it is clear that

(6.3) ${\rm Clump}(G,x)\geq{\rm Clump}(G,p)-\epsilon$

since $U_{1}\setminus[px]$ is a clump of $x$. So, ${\rm Clump}(G,p)$ is a
lower semi-continuous function of $p\in|K(G)|$.

(2) Let $p\in|K(G)|$ be a point such that ${\rm Clump}(G)={\rm Clump}(G,p)$
and $p$ is not a vertex of $K(G)$. Suppose that $p$ is contained in the edge
$\overline{xy}$. Let $U_{x}$ and $U_{y}$ be the clumps of $p$ containing $x$
and $y$ respectively. Then

(6.4) $L(U_{x})=|[xp]|+n_{x}\ \mbox{and}\ L(U_{y})=|[yp]|+n_{y}$

where $n_{x}+1$ and $n_{y}+1$ are numbers of vertices in $U_{x}$ and $U_{y}$
respectively. We claim that _$n_{x}=n_{y}$_. Otherwise, Suppose that
$n_{x}>n_{y}$. Let $q$ be the mid-point of $[xp]$. Then,

${\rm Clump}(G,q)=n_{x}+|[xq]|=n_{x}+\frac{1}{2}{|[xp]|}<n_{x}+|[xp]|={\rm
Clump}(G,p)={\rm Clump}(G)$

which is a contradiction. Now, let $z$ be the mid-point of the edge
$\overline{xy}$. Then,

${\rm Clump}(G)\leq{\rm Clump}(G,z)=n_{x}+\frac{1}{2}\leq{\rm Clump}(G,p)={\rm
Clump}(G).$

So $p=z$ is the the mid-point of the edge $\overline{xy}$.

(3) It has been shown in the proof of (2).

(4) Let $p,q\in|K(G)|$ be two different points such that

${\rm Clump}(G,p)={\rm Clump}(G,q)={\rm Clump}(G).$

By (2) and (3), we know that $p$ and $q$ must be simultaneously vertices of
$K(G)$ or mid-points of some edges of $K(G)$.

For the first case: $p$ and $q$ are both vertices of $K(G)$, let
$U_{1},U_{2},\cdots,U_{r}$ be the clumps of $p$ and $W_{1},W_{2},\cdots,W_{s}$
be the clumps of $q$ such that $q\in U_{1}$ and $p\in W_{1}$. Then,

(6.5) ${\rm Clump}(G)={\rm Clump}(G,p)\geq{\rm Length}(U_{1})$

and similarly,

(6.6) ${\rm Clump}(G)={\rm Clump}(G,q)\geq{\rm Length}(W_{1}).$

Moreover, it is clear that $U_{i}\subsetneqq W_{1}$ for any $i=2,3,\cdots,r$
and $W_{j}\subsetneqq U_{1}$ for any $j=2,3,\cdots,s$. Thus,

(6.7) ${\rm Length}(U_{i})<{\rm Length}(W_{1})$

for $i=2,3,\cdots,r$ and

(6.8) ${\rm Length}(W_{j})<{\rm Length}(U_{1})$

for $j=2,3,\cdots,s$. Then,

(6.9) $\begin{split}{\rm Clump}(G)=&{\rm Clump}(G,p)\\\ =&\max_{1\leq i\leq
r}{\rm Length}(U_{i})\\\ \leq&\max\\{{\rm Length}(U_{1}),{\rm
Length}(W_{1})\\}\\\ \leq&{\rm Clump}(G)\end{split}$

Thus

${\rm Length}(U_{1})=\max_{1\leq i\leq r}{\rm Length}(U_{i})={\rm Clump}(G).$

Similarly,

${\rm Length}(W_{1})=\max_{1\leq j\leq s}{\rm Length}(W_{j})={\rm Clump}(G).$

Let $v$ be the vertex in $U_{1}$ adjacent to $p$ and $z$ be the mid-point of
$\overline{pv}$. Let $U_{p}$ and $U_{q}$ be the clumps of $z$ containing $p$
and $q$ respectively. Then, $U_{p}\subsetneqq W_{1}$ and $U_{q}\subsetneqq
U_{1}$. So,

(6.10) ${\rm Clump}(G,z)=\max\\{{\rm Length}(U_{p}),{\rm
Length}(U_{q})\\}<{\rm Clump}(G).$

This is a contradiction.

For the second case: both $p$ and $q$ are mid-points of some edges, it is
clear this is impossible by (3). ∎

For further applications, we need the following notions and propositions come
from [11]. To make the paper more self-contained, we quote them at the end of
this section.

######  Proposition 6.2 (Lemma 4.3 in [11]).

Let $G$ be a combinatorial finite tree. Then,

${\rm Clump}(G)\leq\frac{|E(G)|}{2}.$

######  Proposition 6.3 (Lemma 5.1 in [11]).

Let $G$ be a combinatorial finite tree. Suppose that $|E(G)|\leq(r+2)k+r$ for
some integers $r\geq 0$ and $k\geq 1$. Then, we can remove at most $r$ edges
from $G$ to get a forest each of whose trees have clump number not greater
than $k$.

######  Proposition 6.4 (Lemma 5.2 in [11]).

Let $G$ be a combinatorial tree with $|E(G)|\leq(r+2)k+(r+1)$ edges for some
integers $k\geq 0$ and $r\geq 0$. Then, we can remove at most $r$ edges from
$G$ to get a forest each of whose trees have clump number not greater than
$k+\frac{1}{2}$.

######  Definition 6.2 (Definition 8.1 & 8.2 in [11]).

Let $k\geq 1$ be an integer.

(1) A tree $G$ is called of type A with respect to $k$ if $|E(G)|=rk-1$ for
some $r\geq 1$ and by removing $r-1$ edges we are left with a forest of $r$
trees each of $k-1$ edges.

(2) A tree $G$ is called of type B if $(r-1)k\leq|E(G)|\leq rk-1$ for some
$r\geq 2$ and by removing $r-2$ edges we are left with a forest of trees whose
clump number no more than $k-1$.

######  Proposition 6.5 (Lemma 8.3 in [11]).

Let $G$ be finite tree and $k\geq 1$ be an integer. If $|E(G)|\geq k-1$ then
$G$ is either of type A or type B with respect to $k$.

######  Remark 6.1.

The statement of the Proposition 6.5 is slightly more general than the
original statement of Lemma 8.3 in [11]. The proof is the same as Friedman’s
original proof. We state it in this more general form because in Friedman’s
original argument by induction, it seems that such a general form of statement
is needed.

##  7\. Minimal Steklov eigenvalues

In this section, we prove Theorem 1.1. The following conclusion is crucial in
our solution of the extremal problems for Steklov eigenvalues.

######  Theorem 7.1.

Let $G$ be a combinatorial tree. Then,

(7.1) $\sigma_{2}(G)\geq\Lambda({\rm Clump}(G)).$

The equality holds if and only if at least two of the clumps of the
equilibrium point of $G$ are the minimal brooms ${\rm Br}({\rm Clump}(G))$.

###### Proof.

Let $p\in|K(G)|$ be the equilibrium point of $G$ and $f\in\mathbb{R}^{V(G)}$
be an eigenfunction for $\sigma_{2}(G)$. Suppose that $\widetilde{f}(p)\leq
0$. Let $U$ be a clump of $p$ containing a leaf $v$ of $G$ such that $f(v)>0$
and $N(f)$ be the nodal domain of $f$ containing $v$. It is clearly that
$N(f)\subset U$. By Theorem 4.2, $g=\widetilde{f}|_{V(N(f))}$ is an
eigenfunction for $\lambda_{1}(N(f))=\sigma_{2}(G)$. Let
$\overline{g}\in\mathbb{R}^{V(G_{U})}$ be the zero extension of $g$. That is
$g(x)=0$ for any $x\in V(G_{\overline{U}})\setminus V(N(f))$. Then, by Theorem
4.2 and Theorem 5.1,

(7.2) $\begin{split}\sigma_{2}(G)=&\lambda_{1}(N(f))\\\ =&\frac{{\left\langle
dg,dg\right\rangle}_{N(f)}}{{\left\langle g,g\right\rangle}_{B(N(f))}}\\\
\geq&\frac{{\left\langle
d\overline{g},d\overline{g}\right\rangle}_{G_{U}}}{{\left\langle\overline{g},\overline{g}\right\rangle}_{B(G_{U})}}\\\
\geq&\lambda_{1}(G_{U})\\\ \geq&\Lambda({\rm Length}(U))\\\ \geq&\Lambda({\rm
Clump}(G)),\end{split}$

where the first inequality comes from the fact that each edge of $N(f)$ is
contained in some edge of $U$.

Moreover, if $\sigma_{2}(G)=\Lambda({\rm Clump}(G)$, then $U=N(f)$ and
$f(p)=0$. Furthermore, by Theorem 5.1, $G_{U}$ must be a minimal broom ${\rm
Br}({\rm Clump}(G))$. Similarly, let $W$ be a clump of $p$ containing a leaf
$w$ of $G$ such that $f(w)<0$. Then, for the same reason, $G_{W}$ must be a
minimal broom ${\rm Br}({\rm Clump}(G))$. This completes the necessary part
for the equality to hold.

Conversely, if there are two clumps $U,W$ of $p$ that are minimal brooms ${\rm
Br}({\rm Clump}(G))$. Let $f_{U}$ be the eigenfunction and $f_{W}$ be the
eigenfunctions of $G_{U}$ and $G_{W}$ respectively such that

${\left\langle f_{U},1\right\rangle}_{B(G_{U})}+{\left\langle
f_{W},1\right\rangle}_{B(G_{W})}=0.$

Let $\psi\in\mathbb{R}^{V(G)}$ be such that

(7.3) $\psi(x)=\left\\{\begin{array}[]{ll}f_{U}(x)&x\in V(G_{U})\\\
f_{W}(x)&x\in V(G_{W})\\\ 0&\mbox{otherwise.}\end{array}\right.$

Then, $\psi$ is a Steklov eigenfunction of $G$ with eigenvalue $\Lambda({\rm
Clump}(G))$ by Lemma 2.1. By the estimate (7.1), we know that

(7.4) $\sigma_{2}(G)=\Lambda({\rm Clump}(G)).$

This completes the proof of the theorem. ∎

As an application of the Theorem 7.1, we can solve the extremal problem for
$\sigma_{2}(G)$ when $G$ is a tree.

######  Theorem 7.2.

Let $G$ be a combinatorial tree. Then,

(7.5) $\sigma_{2}(G)\geq\Lambda\left(\frac{|E(G)|}{2}\right).$

The equality holds if and only if

  1. (1)

$G={\rm DB}(m,2m,m)$ when $|E(G)|=4m$;

  2. (2)

$G={\rm DB}(m,2m+1,m)$ when $|E(G)|=4m+1$;

  3. (3)

$G={\rm DB}(m+1,2m,m+1),{\rm DB}(m,2m+2,m)\ \mbox{or}\ {\rm DB}(m,2m+1,m+1)$
when $|E(G)|=4m+2$;

  4. (4)

$G={\rm DB}(m+1,2m+1,m+1)$ when $|E(G)|=4m+3$.

###### Proof.

By Proposition 6.2, we know that

${\rm Clump}(G)\leq\frac{|E(G)|}{2}.$

Thus, by Theorem 7.1,

(7.6) $\sigma_{2}(G)\geq\Lambda({\rm
Clump}(G))\geq\Lambda\left(\frac{|E(G)|}{2}\right).$

When the equality of (7.5) holds, we know that ${\rm
Clump}(G)=\frac{|E(G)|}{2}$. Moreover, by the rigidity part of Theorem 7.1, we
get the conclusion. ∎

By combining Theorem 7.2 and Lemma 3.1, we can prove (1) of Theorem 1.1.

###### Proof for (1) of Theorem 1.1.

Let $T$ be spanning tree of $G$. Then, by Theorem 1.2,

(7.7)
$\sigma_{2}(G)\geq\sigma_{2}(T)\geq\Lambda\left(\frac{|E(T)|}{2}\right)=\Lambda\left(\frac{n-1}{2}\right).$

Conversely, if $\sigma_{2}(G)=\Lambda\left(\frac{n-1}{2}\right)$, by the
rigidity part of Theorem 7.2, $T$ must be a dumbbell listed in Theorem 7.2.
Moreover, by Lemma 3.1, $G=T$. This completes the proof. ∎

Next, we come to deal with the case $i\not|n$ in Theorem 1.1. By imitating the
arguments in [11], we need to modify the notion of sub-$k$ in [11, Definition
5.3].

######  Definition 7.1.

Given a positive integer $k$, a tree $G$ is called sub-$k$ if either (i) it
has clump number less than $k$, or (ii) it has clump number $k$ with respect
to some vertex $o$, but contains at most one clump with respect to $o$ which
is a minimal broom ${\rm Br}(k)$ with $o$ as the root.

By Theorem 7.1, if a tree $G$ is sub-$k$, then

(7.8) $\sigma_{2}(G)>\Lambda(k).$

Similarly as in [11, Lemma 5.4], we have the following result with the proof
similar to the proof of [11, Lemma 5.4]. For completeness, we give the proof
of the result in details.

######  Proposition 7.1.

Let $G$ be a tree with $|E(G)|=(r+2)k$ edges for some integers $r\geq 0$ and
$k\geq 1$. Then, unless $G$ is star of degree $r+2$ with each arm a minimal
broom ${\rm Br}(k)$ with the center of the star as the root, we can remove at
most $r$ edges from $G$ to get a forest, each of whose trees are sub-$k$.

###### Proof.

We proceed by induction.

When $r=0$, if $G$ is not sub-$k$, then ${\rm Clump}(G)\geq k$ and there is
vertex $o$ such that there are least two clumps with respect to $o$ that are
minimal brooms ${\rm Br}(k)$ with $o$ as the root. This means that $G$ is a
star with two arms that are minimal brooms ${\rm Br}(k)$. This proves the
conclusion for $r=0$.

When $r=1$, let $p$ be the equilibrium point of $G$. By Proposition 6.2,

${\rm Clump}(G,p)\leq|E(G)|/2=\frac{3k}{2}.$

If $p$ is an mid-point of some edge, by replacing $p$ by an end-vertex $v$ of
that edge, we know that there is a vertex of $G$ such that

(7.9) ${\rm Clump}(G,v)\leq 2k.$

Let $T$ be a clump of $G$ with respect to $v$ such that

$|E(T)|={\rm Clump}(G,v)\leq 2k.$

If $|E(T)|>k$, after removing the edge in $T$ joining to $v$, we get two trees
$T_{1}$ and $T_{2}$ such that

$k\leq|E(T_{1})|=|E(T)|-1\leq 2k-1$

and

$k\leq|E(T_{2})|=|E(G)|-|E(T)|\leq 2k-1.$

By Proposition 6.2, we know that $T_{1}$ and $T_{2}$ are both sub-$k$.

If $|E(T)|\leq k$ and $G$ is not a star with center $v$ and each arm a minimal
broom ${\rm Br}(k)$, then there are at most two clumps of $G$ that are minimal
brooms ${\rm Br}(k)$. If there is no clump of $G$ with respect to $v$ that is
a minimal broom ${\rm Br}(k)$, the $G$ itself is sub-$k$. So no edge need to
be removed. If there is a clump of $G$ that is a minimal broom ${\rm Br}(k)$,
remove the edge in that clump that is adjacent to $v$, we get a forest of two
trees whose trees are both sub-$k$ because there are at most two clumps of $G$
that are minimal brooms ${\rm Br}(k)$. This proves the conclusion for $r=1$.

Suppose the conclusion is true for $r\leq m-1$ with $m\geq 2$. When $r=m$, let
$p$ be the equilibrium point of $G$. Then, by Proposition 6.2,

${\rm Clump}(G,p)\leq\frac{|E(G)|}{2}=\frac{(m+2)k}{2}.$

If $p$ is an mid-point of some edge, by replacing $p$ by an end-vertex $v$ of
that edge, we know that there is a vertex of $G$ such that

(7.10) ${\rm Clump}(G,v)\leq mk.$

If there is a clump $T$ of $v$ with $|E(T)|=kq$ with $2\leq q\leq m$, then
after removing the edge in $T$ adjacent to $v$, the tree $G$ will separate to
two trees $T_{1}$ and $T_{2}$ with

(7.11) $|E(T_{1})|=|E(T)|-1=kq-1=q(k-1)+q-1$

and

(7.12) $|E(T_{2})|=|E(G)|-|E(T)|=(m+2-q)k.$

By Proposition 6.4 and the induction hypothesis, we can remove no more than
$q-2$ edges from $T_{1}$ to get a forest whose trees are of clump numbers not
greater than $k-\frac{1}{2}<k$, and we can also remove $m-q$ edges from
$T_{2}$ to get a forest whose trees are all sub-$k$. Note that we have removed
no more than

$1+q-2+m-q=m-1$

edges from $G$. We get the conclusion for this case.

If there is a clump $T$ of $v$ with clump number greater than $k$ but not a
multiple of $k$, let $|E(T)|=kq+i$ with $i=1,2,\cdots,k-1$ and $q\geq 1$.
Then, by removing the edge in $T$ adjacent to $v$, we get two trees $T_{1}$
and $T_{2}$ such that

$|E(T_{1})|=kq+i-1\leq qk+k-2<(q+1)(k-1)+q$

and

$|E(T_{2})|\leq(m-q+2)k-1=(m-q+2)(k-1)+(m-q+1).$

So, by Proposition 6.4, we can remove $q-1$ and $m-q$ edges from $T_{1}$ and
$T_{2}$ respectively to get a forest whose trees are of clump numbers not
greater than $k-\frac{1}{2}<k$. This gives us the conclusion in this case when
$r=m$.

The remaining case is that each clump of $v$ is of total length not greater
than $k$. Let $P_{1},P_{2},\cdots,P_{t},T_{1},T_{2},\cdots,T_{s}$ be clumps of
$G$ with respect to $v$. Such that $P_{1},P_{2},\cdots,P_{t}$ are minimal
brooms ${\rm Br}(k)$ and $T_{1},\cdots,T_{s}$ are either trees of total length
not greater $k-1$ or trees of of total length $k$ that are not a minimal broom
${\rm Br}(k)$. If $t=m+2$, then $G$ is a star with degree $m+2$ and each arm a
minimal broom ${\rm Br}(k)$. If $t\leq m+1$, then by removing the edges in
$P_{1},P_{2},\cdots,P_{t-1}$ adjacent to $v$, we get a forest whose trees are
all sub-$k$. This completes the proof of the conclusion. ∎

We are now ready to solve the extremal problem for trees when $i\not||V(G)|$.

######  Theorem 7.3.

Let $G$ be a finite combinatorial tree and $2<i<|V(G)|$ be an integer with
$i\not|\ |V(G)|$. Then

(7.13) $\sigma_{i}(G)\geq\Lambda(m)$

where $m=\left\lfloor\frac{V(G)}{i}\right\rfloor$. Moreover, when
$|V(G)|=im+1$, the equality holds if and only if $G$ is a star of degree $i$
such that each arm is a minimal broom ${\rm Br}(m)$ with the center of the
star as the root.

###### Proof.

Note that

$|E(G)|=|V(G)|-1\leq mi+i-2.$

So, by Proposition 6.3, one can remove no more than $i-2$ edges from $G$ to
get a forest $F$ whose trees $T_{1},T_{2},\cdots,T_{k}$ are of clump numbers
not greater than $m$. Note that $k\leq i-1$. So, by Theorem 1.2 and Theorem
7.1,

(7.14)
$\sigma_{i}(G)\geq\sigma_{i}(F)\geq\min\\{\sigma_{2}(T_{1}),\cdots,\sigma_{2}(T_{k})\\}\geq\Lambda(m)$

by noting that the Steklov spectrum of the forest $F$ is the disjoint union of
the Steklov spectrums of its trees: $T_{1},T_{2},\cdots,T_{k}$.

When $|V(G)|=mi+1$, that is $|E(G)|=mi$, if $G$ is not a star of degree $i$
with each arm a minimal broom ${\rm Br}(m)$, by Proposition 7.1, one can
remove no more than $i-2$ edges to get a forest whose trees are all sub-$m$.
In this case, similarly as before,

(7.15)
$\sigma_{i}(G)\geq\sigma_{i}(F)\geq\min\\{\mu_{2}(T_{1}),\cdots,\mu_{2}(T_{k})\\}>\Lambda(m).$

This means that if the equality is achieved, then $G$ must be a star of degree
$i$ with each arm a minimal broom ${\rm Br}(m)$. This completes the proof of
theorem. ∎

By Theorem 7.3 and Lemma 3.1, we can prove (2) of Theorem 1.1

###### Proof for (2) of Theorem 1.1.

Let $T$ be a spanning tree of $G$. Then, by Theorem 1.2 and Theorem 7.3,

(7.16) $\sigma_{i}(G)\geq\sigma_{i}(T)\geq\Lambda(m).$

When $V(G)=mi+1$ and the equality holds, by Theorem 7.3, $T$ must be a star of
degree $i$ with each arm a minimal broom ${\rm Br}(m)$. Finally, by Lemma 3.1,
$G=T$. This completes the proof. ∎

We finally come to deal with the case $i|n$ in Theorem 1.1. We first solve the
extremal problem for trees.

######  Theorem 7.4.

Let $G$ be a finite combinatorial tree and $2<i<|V(G)|$ with $i|\ |V(G)|$.
Then

(7.17) $\sigma_{i}(G)\geq\Lambda(m-1+\theta_{i})$

where $m=\frac{V(G)}{i}$ and $\theta_{i}=\frac{1}{4\cos^{2}\frac{\pi}{2i}}$.
The equality holds if and only if $G$ is the regular comb ${\rm
Comb}(P_{i};T)$ where $P_{i}$ is a path on $i$ vertices and $T$ is the minimal
broom ${\rm Br}(m-1+\theta_{i})$ with the Dirichlet boundary vertex deleted
and the vertex adjacent to Dirichlet boundary vertex as the root.

###### Proof.

Note that $|E(G)|=im-1$, by Proposition 6.5, $G$ is either of type $A$ or type
$B$.

When $G$ is of type $B$, by removing $i-2$ edges from $G$ we are left a forest
$F$ consisting of $i-1$ trees $T_{1},T_{2},\cdots,T_{i-1}$ with clump numbers
all no more than $m-1$. Then, by Theorem 1.2 and Theorem 7.1,

$\begin{split}\sigma_{i}(G)\geq\sigma_{i}(F)\geq\min\\{\sigma_{2}(T_{1}),\cdots,\sigma_{2}(T_{i-1})\\}\geq\Lambda(m-1)>\Lambda(m-1+\theta_{i}).\end{split}$

When $G$ is of type A, we can remove $i-1$ edges to get a forest $F$ of $i$
trees $T_{1},T_{2},\cdots,T_{i}$ that are all of size $m-1$. Let $G^{\prime}$
be a graph with

$V(G^{\prime})=\\{T_{1},T_{2},\cdots,T_{i}\\}$

and

$E(G^{\prime})=\\{\\{T_{r},T_{s}\\}\ |\ \mbox{ There is an edge joining}\
T_{r}\ {\rm and}\ T_{s}\ {\rm in}\ G.\\}$

It is clear that $G^{\prime}$ is a tree. Let $\varphi$ be a Laplacian
eigenfunction of $G^{\prime}$ for $\mu_{i}(G^{\prime})$. By Proposition 2.2,
$\varphi$ has alternating signs. So, on each edge $e$ of $|K(G^{\prime})|$,
there is zero point $z_{e}$ of $\widetilde{\varphi}$. Because each edge of $e$
corresponding to an edge in $G$, we can simply view $z_{e}$ as a point on the
corresponding edge of $|K(G)|$. Let
$\widetilde{T}_{1},\widetilde{T}_{2},\cdots,\widetilde{T}_{i}$ be the
connected components of $|K(G)|$ with all the $z_{e}$’s deleted such that
$\widetilde{T}_{j}\supset T_{j}$ for $j=1,2,\cdots,i$. By Corollary 2.2,

(7.18) $\sum_{e\in
E(B_{D}(\widetilde{T}_{j}),\Omega_{D}(\widetilde{T}_{j}))}w_{e}=\mu_{i}(G^{\prime}).$

for $j=1,2,\cdots,i$.

Let $f_{1}\equiv 1,f_{2},\cdots,f_{|V(G)|}\in\mathbb{R}^{V(G)}$ be an
orthogonal system of Steklov eigenfunctions for $G$ such that $f_{j}$ is an
eigenfunction of $\sigma_{j}(G)$ for $j=1,2,\cdots,|V(G)|$. Let
$U=\mbox{span}\\{f_{1},f_{2},\cdots,f_{i}\\}$ and

$W=\\{f\in\mathbb{R}^{V(G)}\ |\ \widetilde{f}(z_{e})=0\mbox{ for all
}z_{e}.\\}.$

Note that $\dim U=i$ and $\dim W\geq|V(G)|-i+1$. So $U\cap W\neq 0$. Let $g\in
U\cap W$ be a nonzero function. Then, by Theorem 5.1, Proposition 2.1 and
(7.18),

(7.19) $\begin{split}\sigma_{i}(G)\geq&\frac{{\left\langle
dg,dg\right\rangle}_{G}}{{\left\langle g,g\right\rangle}_{B(G)}}\\\
=&\frac{\sum_{j=1}^{i}{\left\langle
d\widetilde{g},d\widetilde{g}\right\rangle}_{\widetilde{T}_{j}}}{\sum_{j=1}^{i}{\left\langle\widetilde{g},\widetilde{g}\right\rangle}_{B(\widetilde{T}_{j})}}\\\
\geq&\min_{1\leq j\leq i}\left\\{\frac{{\left\langle
d\widetilde{g},d\widetilde{g}\right\rangle}_{\widetilde{T}_{j}}}{{\left\langle\widetilde{g},\widetilde{g}\right\rangle}_{B(\widetilde{T}_{j})}}\right\\}\\\
\geq&\min\\{\lambda_{1}(\widetilde{T}_{1}),\lambda_{1}(\widetilde{T}_{2}),\cdots,\lambda_{1}(\widetilde{T}_{i})\\}\\\
\geq&\Lambda\left(\frac{1}{\mu_{i}(G^{\prime})},m-1\right)\\\
\geq&\Lambda\left(\frac{1}{\mu_{i}(P_{i})},m-1\right)\\\
=&\Lambda(m-1+\theta_{i}).\\\ \end{split}$

When the equality holds, we know that $G$ must be of type A and $G^{\prime}$
must be a path on $i$ vertices. Moreover, the function $g$ before must be an
eigenfunction for $\sigma_{i}(G)$. Let $N_{1},N_{2},\cdots,N_{s}$ be the nodal
domains of $g$. It is clear that each $N_{j}$ is contained in some
$\widetilde{T}_{\nu}$. Then, by Theorem 4.2 and Theorem 5.1,

(7.20)
$\Lambda(m-1+\theta_{i})=\sigma_{i}(G)=\lambda_{1}(N_{j})\geq\lambda_{1}(\widetilde{T}_{\nu})\geq\Lambda(m-1+\theta_{i}).$

The inequality $\lambda_{1}(N_{j})\geq\lambda_{1}(\tilde{T}_{\nu})$ comes from
the same argument as in (7.2) by zero extension. Thus, by the rigidity part of
Theorem 5.1 and Corollary 2.1, we completes the proof of the theorem. ∎

Finally, we come to prove (3) of Theorem 1.1.

###### Proof for (3) of Theorem 1.1.

Let $G^{\prime}$ be a spanning tree of $G$. By Theorem 1.2,

(7.21) $\sigma_{i}(G)\geq\sigma_{i}(G^{\prime})\geq\Lambda(m-1+\theta_{i})$

When the equality holds, by the rigidity part of the last theorem, we know
that every spanning tree of $G$ must be isomorphic to ${\rm Comb}(P_{i};T)$.
By [28, Theorem in P.424], we know that $G={\rm Comb}(P_{i};T)$ or ${\rm
Comb}(C_{i};T)$. When $i$ is even, because

$\mu_{i}(C_{i})=4>\mu_{i}(P_{i}),$

by Corollary 2.1, we know that

(7.22) $\sigma_{i}({\rm Comb}(C_{i},T))>\sigma_{i}({\rm Comb}(P_{i},T)).$

When $i$ is odd, by [2, P. 9],

$\mu_{i}(C_{i})=\mu_{i}(P_{i}).$

So, by Corollary 2.1,

(7.23) $\sigma_{i}({\rm Comb}(C_{i},T))=\sigma_{i}({\rm
Comb}(P_{i},T))=\Lambda(m-1+\theta_{i}).$

This completes the proof. ∎

## References

  * [1] Barlow M. T.,Random walks and heat kernels on graphs. London Mathematical Society Lecture Note Series, 438. Cambridge University Press, Cambridge, 2017.
  * [2] Brouwer A. E., Haemers W. H., Spectra of graphs. Universitext. Springer, New York, 2012. xiv+250 pp.
  * [3] Colbois B., Girouard A., The spectral gap of graphs and Steklov eigenvalues on surfaces. Electron. Res. Announc. Math. Sci. 21 (2014), 19–27.
  * [4] Colbois B., Girouard A., Raveendran B., The Steklov spectrum and coarse discretizations of manifolds with boundary. Pure Appl. Math. Q. 14 (2018), no. 2, 357–392.
  * [5] Escobar J. F. The Yamabe problem on manifolds with boundary. J. Differential Geom. 35 (1992), no. 1, 21–84.
  * [6] Fraser, A.; Schoen, R., The first Steklov eigenvalue, conformal geometry, and minimal surfaces, Adv. Math. 226 (2011), no. 5, 4011–4030.
  * [7] Fraser A., Schoen R. Sharp eigenvalue bounds and minimal surfaces in the ball. Invent. Math. 203 (2016), no. 3, 823–890.
  * [8] Fraser A., Schoen R., Shape optimization for the Steklov problem in higher dimensions. Adv. Math. 348 (2019), 146–162.
  * [9] Fraser A., Schoen R., Some results on higher eigenvalue optimization. Calc. Var. Partial Differential Equations 59 (2020), no. 5, Paper No. 151, 22 pp.
  * [10] Friedman J., Some geometric aspects of graphs and their eigenfunctions. Duke Math. J. 69 (1993), no. 3, 487–525.
  * [11] Friedman J., Minimum higher eigenvalues of Laplacians on graphs. Duke Math. J. 83 (1996), no. 1, 1–18.
  * [12] Han W., Hua B., Steklov eigenvalue problem on subgraphs of integer lattics. arXiv: 1902.05831. To appear in Communication in Analysis and Geometry.
  * [13] Hassannezhad A., Miclo, L., Higher order Cheeger inequalities for Steklov eigenvalues. Ann. Sci. École Norm. Sup. (to appear).
  * [14] He Z., Hua B. Bounds for the Steklov eigenvalues on trees. arXiv:2011.11014.
  * [15] He Z., Hua B. Steklov flows on trees and applications. arXiv: 2103.07696.
  * [16] Hua B., Huang Y., Wang Z., First eigenvalue estimates of Dirichlet-to-Neumann operators on graphs. Calc. Var. Partial Differential Equations 56 (2017), no. 6, Art. 178, 21 pp.
  * [17] Hua B., Huang Y., Wang Z., Cheeger esitmates of Dirichlet-to-Neumann operators on infinite subgraphs of graphs. arXiv: 1810.10763.
  * [18] Kuznetsov, N., Kulczycki T., Kwaśnicki M., Nazarov A., Poborchi S., Polterovich I., Siudeja B., The legacy of Vladimir Andreevich Steklov. Notices Amer. Math. Soc. 61 (2014), no. 1, 9–22.
  * [19] Perrin H., Lower bounds for the first eigenvalue of the Steklov problem on graphs. Calc. Var. Partial Differential Equations 58 (2019), no. 2, 58–67.
  * [20] Perrin H., Isoperimetric upper bound for the first eigenvalue of discrete Steklov problems. J. Geom. Anal. 31 (2021), no. 8, 8144–8155.
  * [21] Petrunin A., Metric geometry on manifolds: two lectures. arXiv:2010.10040.
  * [22] Shi Y., Yu C., Higher order Dirichlet-to-Neumann maps on graphs and their eigenvalues. arXiv:1904.03880.
  * [23] Shi Y., Yu C., A Lichnerowicz-type estimate for Steklov eigenvalues on graphs and its rigidity. arXiv: 2010.13966.
  * [24] Shi Y., Yu C., Comparison of Steklov eigenvalues and Laplacian eigenvalues on graphs. To appear in Proceedings of American Mathematical Society.
  * [25] Stekloff W., Sur les problèmes fondamentaux de la physique mathématique. Ann. Sci. École Norm. Sup. (3) 19 (1902), 191–259.
  * [26] Tschan L., Upper bounds for Steklov eigenvalues of subgraphs of polynomial growth Cayley graphs. Ann. Glob. Anal. Geom., (1) 61 (2022), 37–55.
  * [27] Yu C., Yu Y., Monotonicity of Steklov eigenvalues on graphs and applications. arXiv:2112.12885.
  * [28] Vestergaard P. D.,Finite and infinite graphs whose spanning trees are pairwise isomorphic. Graph theory in memory of G. A. Dirac (Sandbjerg, 1985), 421–435, Ann. Discrete Math., 41, North-Holland, Amsterdam, 1989.