# Nodal domain count for the generalized graph $p$-Laplacian

Piero Deidda  ,  Mario Putti  Department of Mathematics “Tullio Levi-Civita”,
University of Padua, Italy<EMAIL_ADDRESS><EMAIL_ADDRESS>and  Francesco Tudisco  School of Mathematics, Gran Sasso Science Institute,
Italy<EMAIL_ADDRESS>
###### Abstract.

Inspired by the linear Schrödinger operator, we consider a generalized
$p$-Laplacian operator on discrete graphs and present new results that
characterize several spectral properties of this operator with particular
attention to the nodal domain count of its eigenfunctions. Just like the one-
dimensional continuous $p$-Laplacian, we prove that the variational spectrum
of the discrete generalized $p$-Laplacian on forests is the entire spectrum.
Moreover, we show how to transfer Weyl’s inequalities for the Laplacian
operator to the nonlinear case and prove new upper and lower bounds on the
number of nodal domains of every eigenfunction of the generalized
$p$-Laplacian on generic graphs, including variational eigenpairs. In
particular, when applied to the linear case $p=2$, in addition to recovering
well-known features, the new results provide novel properties of the linear
Schrödinger operator.

###### Key words and phrases:

Graph $p$-Laplacian, nodal domains, variational eigenpairs, Weyl’s
inequalities

##  1\. Introduction

The study of nodal domains dates back to Sturm’s oscillation theorem that
states that the zeros of the $k$-th mode of vibration of an oscillating string
are the endpoints of a partition of the string into $k$ subdomains where the
mode has constant sign. Later Courant extended this result to higher
dimensions, proving that the $k$-th eigenfunction of an oscillating membrane
admits no more than $k$ subdomains, called nodal domains [15]. The count of
the nodal domains of the Laplacian operator, and its generalized version
called the Schrödinger operator, has been shown to hold important information
about the geometry of the system [9, 27, 26]. In particular, nodal domains are
tightly connected to higher-order isoperimetric constants of graphs, making
the study of nodal domains particularly relevant in the context of data
clustering, expander graphs, and mixing time of Markov chains [1, 16, 22, 30].
Because of these reasons, the estimation of the number of nodal domains of the
Schrödinger eigenfunctions both on continuous manifolds and on discrete and
metric graphs has been an active field of research in recent years.

In the discrete graph setting, it was proved in [5, 7] that trees behave like
strings and that the $k$-th eigenvector $f_{k}$ of the Schrödinger operator,
if everywhere non-zero, induces exactly $k$ nodal domains. Moreover, again
under the assumption that the $k$-th eigenvector $f_{k}$ of the graph
Schrödinger operator is everywhere non-zero, it was proved in [6] that for
general graphs the following inequality holds for the number of nodal domains
$\nu(f_{k})$ of $f_{k}$, provided the corresponding eigenvalue is simple:

$k-\beta+l(f_{k})\leq\nu(f_{n})\leq k\,.$

Here $\beta$ is the total number of independent loops of the graph and
$l(f_{k})$ is the number of independent loops where $f_{k}$ has constant sign.
In the general case of eigenvalues with any multiplicity and eigenvectors with
possibly some zero entry, it was proved in [17, 19, 41] that the following
inequality holds:

$k+r-1-\beta-z\leq\nu(f_{k})\leq k+r-1\,,$

where $f_{k}$ is an eigenvector of the eigenvalue $\lambda_{k}$, $z$ is the
number of zeros of $f_{k}$ and $r$ is the multiplicity of $\lambda_{k}$.

In recent years, there has been a surge in interest towards extensions of the
above results to the nonlinear $p$-Laplacian and $p$-Schrödinger operators and
their spectral properties, including the nodal domain count, have been widely
investigated both in the continuous and in the discrete cases [3, 32, 31, 18].
This interest is prompted by applications to biological and physical processes
often connected to complex networks and data clustering, as well as semi-
supervised learning and machine learning in general [12, 21, 20, 24, 13, 36,
35], where the limiting cases $p=1$ and $p=\infty$ are especially noteworthy.
In particular, similarly to the linear case, an important relation connects
the nodal domains of the $p$-Laplacian on graphs and the $k$-th order
isoperimetric constant $h_{k}$ of the graph. Indeed, it is shown in [40] that
this fundamental graph invariant can be bounded from above and from below
using the variational spectrum $\lambda_{k}$ of the $p$-Laplacian and its
nodal domain count via the Cheeger-like inequality

(1) $\lambda_{\nu(f_{k})}\leq h_{\nu(f_{k})}\leq c(p)\lambda_{k}^{1/p}$

where $c(p)\to 1$ as $p\to 1$ and $f_{k}$ is any eigenfunction of
$\lambda_{k}$. To our knowledge, this result is the tightest available
connection between $h_{k}$ and the spectrum of the graph $p$-Laplacian and
clearly highlights the importance of the nodal domain count in connection to,
for example, the quality of $p$-Laplacian graph embeddings for data
clustering, for which there is a wealth of empirical evidence [10, 11, 12,
21]. A nodal domain theorem for the graph $p$-Laplacian is provided in [40],
where it is shown that, for any eigenfunction $f_{k}$ of the $p$-Laplacian,
the number of nodal domains is bounded above as $\nu(f_{k})\leq k+r-1$, where
$r$ is the multiplicity of the corresponding eigenvalue. Analogous results are
proved in [14] for the case $p=1$. However no lower bounds for $\nu(f_{k})$
are known in the general case.

The main aim of this paper is to provide lower bounds on the number of nodal
domains of the generic eigenfunction of the $p$-Laplacian. To this end, we
will introduce a class of generalized $p$-Laplacian operators, already
addressed in [34]. Such operators, inspired by the generalized linear
Laplacian or Schrödinger operator [5, 41], are also largely related to
$p$-Laplacian problems with zero Dirichlet boundary conditions [28]. Thus, all
our results apply to both the classical $p$-Laplacian and the generalized
$p$-Schrödinger operators. We prove a classical characterization of the first
and the second variational eigenpairs and nonlinear Weyl’s like inequalities.
These are fundamental instruments to study the nodal domains of the generic
eigenfunction. Our general strategy, inspired by the work of [5], consists in
defining appropriate rules to remove nodes or edges from the graph without
changing an eigenpair. Repeated applications of this procedure allows us to
arrive to a structured graph (e.g. a tree or the disjoint union of the nodal
domains) for which nodal domain numbers or other spectral quantities can be
fully characterized. This characterization can be brought back to the original
graph by reversing the proposed procedure. This strategy allows us to find new
lower bounds as well as retrieve known upper bounds for the number of nodal
domains of any eigenfunction, as a function of the position of the
corresponding eigenvalue in the variational spectrum. In addition, our
estimates, with $p=2$, provide an improvement on the known results for the
linear case.

An important side result of our work is that we are able to prove that, if the
graph is a tree, the variational eigenvalues are all and only the eigenvalues
of the $p$-Laplacian operator and that the $k$-th eigenfunction, if everywhere
nonzero, admits exactly $k$ nodal domains. This result extends what is already
known in the particular cases of the path graph [40] and the star graph [3],
and is a generalization to the $p$-Laplacian of analogous findings known in
the linear case [7, 5]. This is of independent interest for its potential
applications to nonlinear spectral graph sparsification, expander graphs, and
graph clustering [38]. In particular, note that our findings in combination
with (1) show that the $k$-th order isoperimetric constant of a tree coincides
with the $k$-th variational eigenvalue of the $1$-Laplacian.

The paper is organized as follows. In Section 2 we introduce notations and
needed definitions. Our main results are collected without proofs in Section
3. The strategy for the proofs is organized into several steps. In Section 4
we provide some preliminary results about the eigenfunctions of the
generalized graph $p$-Laplacian, including the characterization of the first
two eigenvalues. In Section 5 we develop the procedures that remove nodes and
edges maintaining an eigenpair, and, along the way, we prove Weyl’s like
inequalities. In section 6 we analyze the particular case of a tree. Finally,
in Section 7 we provide the proofs of the main results, namely new
inequalities on the number of the nodal domains of the eigenfunctions of the
graph $p$-Laplacian operator.

##  2\. Notation

Let $\mathcal{G}=(V,E)$ be a connected undirected graph, where $V$ and $E$ are
the sets of nodes and edges endowed with positive measures
$\varrho:V\to\mathbb{R}_{+}$ and $\omega:E\to\mathbb{R}_{+}$, respectively.
Given a function $f:V\to\mathbb{R}$, for any $p>1$ consider the $p$-Laplacian
operator:

$(\Delta_{p}f)(u):=\sum_{v\sim
u}\omega_{uv}|f(u)-f(v)|^{p-2}(f(u)-f(v))\qquad\forall u\in V\,,$

where $v\sim u$ denotes the presence of an edge between $v$ and $u$. We point
out that, while the $p$-Laplacian is well-defined also for $p=1$, throughout
this work will not consider this limit case and we will always implicitly
assume that $p>1$. Throughout the paper, we will often use the function
$\phi_{p}(x):=|x|^{p-2}x$, so that the above equation reads simply:

$(\Delta_{p}f)(u):=\sum_{v\sim
u}\omega_{uv}\phi_{p}\left(f(u)-f(v)\right)\qquad\forall u\in V\,.$

In analogy to the linear case, where the generalized Laplacian is defined as
the Laplacian plus a diagonal matrix [41], we define the generalized
$p$-Laplacian (or $p$-Schrödinger) operator as

$(\mathcal{H}_{p}f)(u):=(\Delta_{p}f)(u)+\kappa_{u}|f(u)|^{p-2}f(u)\qquad\forall
u\in V\,,$

where $\kappa_{u}$ is a real coefficient. We say that $f$ is an eigenfunction
of $\mathcal{H}_{p}$ if there exists $\lambda\in\mathbb{R}$ such that

(2) $(\mathcal{H}_{p}f)(u)=\lambda\,\varrho_{u}|f(u)|^{p-2}f(u)\qquad\forall
u\in V\,.$

Similarly to the linear case, generalized $p$-Laplacians and their
eigenfunctions are directly connected with the solutions of Dirichlet problems
on graphs for the $p$-Laplacian operator. In fact, assume we have a graph
$\mathcal{G}=(V,E)$ with node and edge sets that can be partitioned as the
disjoint union of internal and boundary sets $V=(V_{I}\sqcup V_{B})$ and
$E=(E_{I}\sqcup E_{B})$, defined as $E_{I}=\\{uv\in E:u,u\in V_{I}\\}$ and
$E_{B}=\\{uv\in E:u\in V_{I},v\in V_{B}\\}$. This is the definition used for
example in [25]. Then, if $f$ is a solution to the Dirichlet problem

(3)
$\begin{cases}(\Delta_{p}f)(u)=\lambda\,\varrho_{u}|f(u)|^{p-2}f(u)&\quad\forall
u\in V_{I}\\\ f(u)=0&\quad\forall u\in{V}_{B}\end{cases}\,,$

we deduce that $f$ is automatically also solution to the following eigenvalue
equation for a generalized $p$-Laplacian where the information about the
boundary nodes has been condensed in the nodal weights:

$\sum_{v\in{V}_{I}}\omega_{uv}|f(u)-f(v)|^{p-2}(f(u)-f(v))+\Big{(}\sum_{v\in{V}_{B}}\omega_{uv}\Big{)}|f(u)|^{p-2}f(u)\\\
=\lambda\,\varrho_{u}|f(u)|^{p-2}f(u)\,.$

In other words, the $p$-Laplacian Dirichlet problem with zero boundary
conditions is equivalent to the eigenvalue problem (2) for the generalized
$p$-Laplacian $\mathcal{H}_{p}$ with
$\kappa_{u}=\sum_{v\in{V}_{B}}\omega_{uv}$.

Finally, the following definition introduces the concept of strong nodal
domains of $\mathcal{G}$, corresponding to a given function
$f:V\to\mathbb{R}$.

######  Definition 2.1 (Nodal domains).

Consider a graph $\mathcal{G}=(V,E)$ and a function
$f:V\rightarrow\mathbb{R}$. A set of vertices $A\subseteq V$ is a nodal domain
induced by $f$ if the subgraph $\mathcal{G}_{A}$ with vertices in $A$ is a
maximal connected subgraph of $\mathcal{G}$ where $f$ is nonzero and has
constant sign. For convenience, in the following we will refer interchangeably
to both $A$ and $\mathcal{G}_{A}$ as the nodal domain induced by $f$.

Sometimes it is useful to distinguish between maximal subgraphs where the sign
is strictly defined and those where zero entries are allowed. In particular,
when zero entries of $f$ are allowed in the definition above, the maximal
subgraphs are called weak nodal domains, whereas the maximal subgraphs with
strictly positive or strictly negative sign as in Definition 2.1 are called
strong nodal domains. However, as in this work we are not interested in weak
nodal domains, throughout we shall simply use the term “nodal domain” to refer
to the strong nodal domains, as defined above.

##  3\. Variational spectrum and main results

In this section we state our main results and will devote the remainder of the
paper to their proof. We first need to introduce the notion of variational
spectrum. A set of $N$ variational eigenvalues of the generalized
$p$-Laplacian on the graph $\mathcal{G}=(V,E)$ can be defined via the
Lusternik–Schnirelman theory and the min-max procedure based on the
Krasnoselskii genus, which we review below [29].

######  Definition 3.1 (Krasnoselksii genus).

Let $X$ be a Banach space and consider the class $\mathcal{A}$ of closed
symmetric subsets of $X$, $\mathcal{A}=\\{A\subseteq
X|\;A\;\>closed\,,\;\>A=-A\\}\;.$ For any $A\in\mathcal{A}$ consider the space
of the Krasnoselskii test maps on $A$ of dimension $k$:

$\Lambda_{k}(A)=\\{\varphi:A\to\mathbb{R}^{k}\text{continuous and such that
}\varphi(x)=-\varphi(-x)\\}.$

The Krasnoselskii genus of $A$ is the number $\gamma(A)$ defined as

$\gamma(A)=\begin{cases}\inf\\{k\in\mathbb{N}\,:\,\exists\,\varphi\in\Lambda_{k}(A)\;\,s.t.\;\,0\not\in\varphi(A)\\}&\\\
{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\infty\qquad\qquad\qquad\qquad\text{if
$\nexists\;k$ as above}}\\\
{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}0\qquad\qquad\qquad\qquad\;\>\text{if
$A=\emptyset$}}\end{cases}\,.$

Our reference Banach space is the space of vertex states
$X=\\{f:V\rightarrow\mathbb{R}\\}=\mathbb{R}^{N}$ and $\mathcal{A}$ denotes
the family of all closed symmetric subsets of $\mathbb{R}^{N}$. Let
$\mathcal{S}_{p}=\\{f\in X:\|f\|_{p}=1\\}$ be the $p$-unit sphere on $X$ and
for $1\leq k\leq N$ consider the family of closed symmetric subsets of
$\mathcal{S}_{p}$ of genus greater than $k$

$\mathcal{F}_{k}(\mathcal{S}_{p}):=\\{A\subseteq\mathcal{A}\cap\mathcal{S}_{p}\,|\,\gamma(A)\geq
k\\}\,.$

In order to define the variational eigenvalues of $\mathcal{H}_{p}$, we
consider the Rayleigh quotient functional

$\mathcal{R}_{\mathcal{H}_{p}}(f)=\frac{\sum_{uv\in
E}\omega_{uv}|f(u)-f(v)|^{p}+\sum_{u\in V}\kappa_{u}|f(u)|^{p}}{\sum_{u\in
V}\varrho_{u}|f(u)|^{p}}\,.$

As $\mathcal{R}_{\mathcal{H}_{p}}$ is positively scale invariant, i.e.
$\mathcal{R}_{\mathcal{H}_{p}}(\alpha f)=\mathcal{R}_{\mathcal{H}_{p}}(f)$ for
all $\alpha>0$, it is not difficult to observe that the eigenvalues and
eigenfunctions of the generalized $p$-Laplacian operator are the critical
values and the critical points of $\mathcal{R}_{\mathcal{H}_{p}}$ on
$\mathcal{S}_{p}$. The Lusternik-Schnirelman theory allows us to define a set
of $N$ variational such critical values, via the following principle

(4) $\lambda_{k}=\min_{A\in\mathcal{F}_{k}(\mathcal{S}_{p})}\max_{f\in
A}\,\mathcal{R}_{\mathcal{H}_{p}}(f)\,.$

We emphasize that the Krasnoselskii genus is a homeomorphism-invariant
generalization to symmetric sets of the notion of dimension. In particular, if
$A\in\mathcal{A}$ is the intersection of any subspace of dimension $k$ with
$\mathcal{S}_{p}$, then $\gamma(A)=k$. Moreover, note that any $A$ such that
$\gamma(A)\geq k$ contains at least $k$ mutually orthogonal functions (see
e.g. [37]). Therefore, the definition in (4) is a generalization of the
Courant-Fisher min-max characterization of the eigenvalues of a symmetric
matrix, as $\mathcal{F}_{k}(\mathcal{S}_{p})$ contains all subspaces of
dimension greater than $k$. However, while Courant-Fisher applies directly to
the case $p=2$, linear subspaces alone are not sufficient to provide critical
points in the general case $p\neq 2$.

###  3.1. Multiplicity and $\gamma$-multiplicity

Similarly to the case of symmetric matrices, we note that the variational
eigenvalues $\\{\lambda_{k}\\}$ are by definition an increasing sequence. This
allows us to define a notion of multiplicity for variational eigenvalues:

######  Definition 3.2.

Let $\lambda_{k}$ be a variational eigenvalue of $\mathcal{H}_{p}$. If
$\lambda_{k}$ appears $m$ times in the sequence of the variational eigenvalues

(5)
$\lambda_{1}\leq\lambda_{2}\leq\dots\leq\lambda_{k-1}<\lambda_{k}=\dots=\lambda_{k+m-1}<\lambda_{k+r}\leq\dots\leq\lambda_{N}\,.$

we say that $\lambda_{k}$ has multiplicity $m$ and we write
$\mathrm{mult}_{\mathcal{H}_{p}}(\lambda_{k})=m$ or simply
$\mathrm{mult}(\lambda_{k})=m$ when no ambiguity may occur.

The notion of multiplicity defined above applies only to variational
eigenvalues. In the case of a generic eigenvalue $\lambda$, we can use the
Krasnoselskii genus to extend the notion of geometric multiplicity to the
nonlinear setting:

######  Definition 3.3.

Let $\lambda$ be an eigenvalue of $\mathcal{H}_{p}$. If

(6)
$\gamma\Big{(}\\{f\in\mathcal{S}_{p}\,:\,\mathcal{H}_{p}(f)=\lambda|f|^{p-2}f\\}\Big{)}=m$

we say that $\lambda$ has $\gamma$-multiplicity $m$ and we write
$\gamma\text{-}\mathrm{mult}_{\mathcal{H}_{p}}(\lambda)=m$, or simply
$\gamma\text{-}\mathrm{mult}(\lambda)=m$ when no ambiguity may occur.

Finally, we define simple eigenvalues

######  Definition 3.4.

We say that $\lambda$ is a simple eigenvalue of $\mathcal{H}_{p}$ if $\lambda$
has a unique eigenfunction $f\in\mathcal{S}_{p}$.

Notice that the notions of multiplicity and $\gamma$-multiplicity do not
coincide and an eigenvalue with $\gamma$-multiplicity equal to one is not
necessarily simple. Viceversa, if $\lambda$ is a simple eigenvalue, then
necessarily $\gamma\text{-}\mathrm{mult}(\lambda)=1$ and, if $\lambda$ is
variational then also $\mathrm{mult}(\lambda)=1$. This result is a direct
consequence of the next lemma, whose proof follows directly from Lemma 5.6 and
Proposition 5.3, Chapter II of [39]:

######  Lemma 3.5.

If $\lambda$ is a variational eigenvalue, then

$\gamma\text{-}\mathrm{mult}(\lambda)\geq\mathrm{mult}(\lambda)\,.$

Note that the inequality above implies, in particular, that, to any
variational eigenvalue $\lambda$, there correspond at least
$\mathrm{mult}(\lambda)$ orthogonal eigenfunctions. Finally, we remark the
following direct consequence of Lemma3.5

######  Corollary 3.6.

Let $\mathcal{H}_{p}$ be the generalized $p$-Laplacian operator on a graph
$\mathcal{G}$ with $N$ nodes. Let $\\{\lambda_{i}\\}_{i=1}^{n}$ be the
variational eigenvalues of $\mathcal{H}_{p}$ counted without multiplicity,
i.e. $\lambda_{i}\neq\lambda_{j}\;\forall i\neq j$. Then

$\sum_{i=1}^{n}\gamma\text{-}\mathrm{mult}(\lambda_{i})\geq\sum_{i=1}^{n}\mathrm{mult}(\lambda_{i})=N\,,$

with the equality holding if and only if
$\gamma\text{-}\mathrm{mult}(\lambda_{i})=\mathrm{mult}(\lambda_{i})$, for all
$i=1,\dots,n$.

###  3.2. Main results

We present below our main results. Recalling the idea summarized in the
introduction, our strategy for counting nodal domains of generalized
$p$-Laplacians is to come up with algorithmic steps to remove vertices and
edges from the original graph in such a way that the original eigenpairs can
be recovered from the eigenpairs of the new graph. Since the proofs of our
main results require relatively long arguments, we state the results here and
devote the remainder of the paper to their proofs. In particular, after
discussing in Sections 4 and 5 a number of preliminary observations and
results, which are of independent interest, Section 6 will provide proofs for
Theorems 3.7 and 3.8, which deal with the special case of trees and forests,
whereas Section 7 will present the proofs of Theorems 3.9 and 3.10, which
address the case of general graphs.

1243 (1) $f=(1,1,1,1),\quad\lambda=0$ (2) $f=(1,0,-1,0),\quad\lambda=2$ (3)
$f=(0,1,0,-1),\quad\lambda=2+2^{p-1}$ (4)
$f=(1,0,1,-2^{\frac{1}{p-1}}),\quad\lambda=1+\big{(}1+2^{\frac{1}{p-1}}\big{)}^{p-1}$
(5) $f=(1,-1,1,-1),\quad\lambda=2^{p}$ Figure 1.  Left: Example graph in which
the corresponding generalized $p$-Laplacian $\mathcal{H}_{p}$ with
$\omega_{uv}=\varrho_{u}=1$ and $\kappa_{u}=0$, for all $u,v=1,\dots,4$, has
at least one non-variational eigenvalue. Right: Set of five eigenfunctions and
the corresponding eigenvalues, for $\mathcal{H}_{p}$.

Notice that, unlike linear operators, the variational spectrum does not cover
the entire spectrum of the generalized $p$-Laplacian and, in general,
establishing whether a certain eigenvalue is variational or not is still an
open problem. For example, Amghibech shows in [2] that the $p$-Laplacian on a
complete graph admits more than just the variational eigenvalues. Another
simple example for the setting $\omega\equiv 1$, $\varrho\equiv 1$ and
$\kappa\equiv 0$ is provided by Figure 1, while a more refined analysis of
non-variational eigenvalues is recently provided by Zhang in [42].

Our first main result shows that the situation is different for the special
case of trees and, more in general, forests. In fact, as for the standard
linear case, we prove that when $\mathcal{G}$ is a forest, the variational
spectrum covers all the eigenvalues of the generalized $p$-Laplacian. Here and
in the following, we use the symbol $\sqcup$ to denote disjoint union.

######  Theorem 3.7.

Let $\mathcal{G}=\sqcup_{i=1}^{k}\mathcal{T}_{i}$ be a forest,
$\mathcal{H}_{p}$ a generalized $p$-Laplacian operator on $\mathcal{G}$,
$p>1$, and $\mathcal{H}_{p}(\mathcal{T}_{i})$ the restriction of
$\mathcal{H}_{p}$ to the $i$-th tree $\mathcal{T}_{i}$. Then $\mathcal{H}_{p}$
admits only variational eigenvalues and for any such eigenvalue $\lambda$ it
holds

$\mathrm{mult}_{\mathcal{H}_{p}}(\lambda)=\gamma\text{-}\mathrm{mult}_{\mathcal{H}_{p}}(\lambda)=\sum_{i=1}^{k}\mathrm{mult}_{\mathcal{H}_{p}(\mathcal{T}_{i})}(\lambda)$

where $\mathrm{mult}_{\mathcal{H}_{p}(\mathcal{T}_{i})}(\lambda)=0$ if
$\lambda$ is not an eigenvalue of $\mathcal{H}_{p}(\mathcal{T}_{i})$.

In addition, we are able to prove the following theorem about the number of
nodal domains induced on a forest, which generalizes well-known results for
the case of the linear Laplacian [23, 5, 7].

######  Theorem 3.8.

Let $\mathcal{G}=\sqcup_{i=1}^{m}\mathcal{T}_{i}$ be a forest and consider the
generalized $p$-Laplacian operator $\mathcal{H}_{p}$, $p>1$, on $\mathcal{G}$.
If $f_{k}$ is an everywhere nonzero eigenfunction associated to the eigenvalue
$\lambda_{k}=\dots=\lambda_{k+m-1}$ of $\mathcal{H}_{p}$, then $f_{k}$ changes
sign on exactly $k-1$ edges. In other words, $f_{k}$ induces exactly $k-1+m$
nodal domains.

Next, we address the case of general graphs. A tight upper bound for the
number of nodal domains of the eigenfunctions of the $p$-Laplacian on graphs
is provided in [40]. It is not difficult to observe that the same upper bound
carries over unchanged to the generalized $p$-Laplacian case. This is
summarized in the following result.

######  Theorem 3.9.

Suppose that $\mathcal{G}$ is connected and
$\lambda_{1}<\lambda_{2}\leq\dots\leq\lambda_{N}$ are the variational
eigenvalues of $\mathcal{H}_{p}$, $p>1$. Let $\lambda$ be an eigenvalue of
$\mathcal{H}_{p}$ such that $\lambda<\lambda_{k}$. Any eigenfunction
associated to $\lambda$ induces at most $k-1$ nodal domains.

Finally, the following theorem provides novel lower bounds for the number of
nodal domains of $\mathcal{H}_{p}$ in the case of general graphs. Morever,
when tailored to the case $p=2$, it provides improved estimates of the nodal
domain count that are strictly tighter than the currently available results
[41, 6]. We will discuss these properties in more details below.

######  Theorem 3.10.

Suppose that $\mathcal{G}$ is a connected graph with $\beta=|E|-|V|+1$
independent loops, and let $\lambda_{1}\leq\cdots\leq\lambda_{N}$ be the
variational eigenvalues of $\mathcal{H}_{p}$, $p>1$. For a function
$f:V\to\mathbb{R}$, let $\nu(f)$ be the number of nodal domains induced by
$f$, $l(f)$ the number of independent loops in $\mathcal{G}$ where $f$ has
constant sign and $\\{v_{i}\\}_{i=1}^{z(f)}$ the nodes such that $f(v_{i})=0$,
with $z(f)$ being the number of such nodes. Let
$\mathcal{G}^{\prime}=\mathcal{G}\setminus\\{v_{i}\\}_{i=1}^{z(f)}$ be the
graph obtained by removing from $\mathcal{G}$ all the nodes where $f$ is zero
as well as all the edges connected to those nodes. Let
$c{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(f)}$
be number of connected components of $\mathcal{G}^{\prime}$ and
$\beta^{\prime}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(f)}=|E^{\prime}|-|V^{\prime}|+c{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(f)}$
the number of independent loops of the graph $\mathcal{G}^{\prime}$. Then:

  1. P1.

If $f$ is an eigenfunction of $\mathcal{H}_{p}$ with eigenvalue $\lambda$ such
that $\lambda>\lambda_{k}$, then $f$ induces strictly more than
$k-\beta+l(f)-z(f)$ nodal domains. Precisely, it holds $\nu(f)\geq
k-\beta^{\prime}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(f)}+l(f)-z(f)+c(f)$.

  2. P2.

If $f$ is an eigenfunction of $\mathcal{H}_{p}$ corresponding to the
variational eigenvalue $\lambda_{k}>\lambda_{k-1}$ with
$\mathrm{mult}_{\mathcal{H}_{p}}(\lambda_{k})=m$, then $\nu(f)\geq
k+{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}m}-1-\beta^{\prime}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(f)}+l(f)-z(f)$.

Before moving on, we would like to briefly comment on the above results and
provide a comparison with respect to lower bounds available for the linear
case $p=2$. First, note that both P1 and P2 in Theorem 3.10 apply to
variational eigenvalues of $\mathcal{H}_{p}$. However they are not corollaries
of each other in the sense that there are settings where P1 is more
informative than P2 and vice-versa. Indeed, if $\lambda_{k}$ is a variational
eigenvalue of multiplicity equal to one, then $\lambda_{k}>\lambda_{k-1}$ and
from P1 we obtain

(7) $\nu(f)\geq
k-\beta^{\prime}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(f)}+l(f)-z(f)+(c{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(f)}-1)$

for any eigenfunction $f$ of $\lambda_{k}$, which is strictly tighter than the
lower bound in P2. However, in P2, when $\lambda_{k}$ has multiplicity
${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}m}>1$,
we have
$\lambda_{k}>\lambda_{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}k-1}}$
and the two lower bounds in P1 and P2 cannot be compared a-priori. Instead,
their combination leads to

(8)
$\nu(f)\geq\max\Big{\\{}\Big{(}k-\beta^{\prime}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(f)}+l(f)-z(f)+(c{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(f)}-{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1})\Big{)},\Big{(}k-\beta^{\prime}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(f)}+l(f)-z(f)+(m-1)\Big{)}\Big{\\}}$

for any eigenfunction $f$ of $\lambda_{k}$. These observations allow us to
draw new lower bounds for the eigenvalues of $\mathcal{H}_{2}$, which are all
variational. In fact, for a simple eigenvalue $\lambda_{k}$ of
$\mathcal{H}_{2}$ with an everywhere nonzero eigenfunction $f$, it was proved
in [6] that $\nu(f)\geq k-\beta+l(f)$. Point P1 of Theorem 3.10 improves this
result by allowing eigenfunctions with zero nodes via inequality (7). Note
that this implies in particular $\nu(f)\geq k-\beta+l(f)-z(f)$, as $c>1$ and
$\beta^{\prime}(f)\leq\beta$. Similarly, when $\lambda_{k}$ is a multiple
eigenvalue of multiplicity $m$ and $f$ is any corresponding eigenfunction, it
was proved in [41] for the linear case that $\nu(f)\geq k+m-1-\beta-z(f)$.
Combining P1 and P2 allows us to improve this bound via the sharper version
given in (8), which further accounts for the number of independent loops of
$f$, the number of connected components of $\mathcal{G}^{\prime}$ and its
number of independent loops.

##  4\. Preliminary properties of the eigenfunctions of the generalized
$p$-Laplacian

In this section we present a brief review of the main results about
$p$-Laplacian eigenpairs and discuss how to extend them to the generalized
$p$-Laplacian case. We start with the characterization of the first and the
last variational eigenvalues. Classical results available for the
$p$-Laplacian equation in the continuous case [32, 31], have been extended to
the discrete case in [40, 28]. In the following we present analogous results
for the generalized $p$-Laplacian operator on graphs.

###  4.1. The smallest variational eigenvalue

We consider in this section the first (smallest) variational eigenvalue
$\lambda_{1}$ of $\mathcal{H}_{p}$, defined as:

(9)
${\lambda_{1}=\min_{f\in\mathcal{S}_{p}}\mathcal{R}_{\mathcal{H}_{p}}(f)}\,.$

Since obviously
$\mathcal{R}_{\mathcal{H}_{p}}(f)\geq\mathcal{R}_{\mathcal{H}_{p}}(|f|)$ for
all $f\in\mathcal{S}_{p}$, we can assume that the first eigenfunction $f_{1}$
is always greater then or equal to zero. On the other hand, if $f_{1}(u)=0$
for some $u\in V$, then from the eigenvalue equation (2) we get

$\mathcal{H}_{p}(f_{1})(u)=-\sum_{v\in
V}\Big{(}\omega_{uv}|f_{1}(v)|^{p-2}f_{1}(v)\Big{)}=0\,,$

which shows that $f_{1}$ assumes both positive and negative values,
contradicting the previous assumption. We deduce that any eigenfunction
corresponding to $\lambda_{1}$ must be everywhere strictly positive, i.e.,
$f_{1}(u)>0$ $\forall u$. This observation generalizes a well-known result for
the standard $p$-Laplacian ($\kappa_{u}=0$) on a graph with no boundary for
which $\lambda_{1}=0$ and any corresponding eigenfunction is positive and has
constant values [2]. We formalize the characterization of the first
eigenfunction of the generalized $p$-Laplacian in the following theorem.

######  Theorem 4.1.

Let $\lambda_{1}$ be the first eigenvalue of $\mathcal{H}_{p}$ on a connected
graph $\mathcal{G}$ as in (9). Then

  1. (1)

$\lambda_{1}$ is simple and the corresponding eigenfunction $f_{1}$ is
strictly positive, i.e., $f_{1}(u)>0\;\forall u\in V$;

  2. (2)

if $g$ is an eigenfunction associated to an eigenvalue $\lambda$ of
$\mathcal{H}_{p}$ and $g(u)>0\;\forall u\in V$, then $\lambda=\lambda_{1}$.

###### Proof.

We have already observed that any eigenfunction $f$ of $\lambda_{1}$ must be
strictly positive so it remains to prove that for any strictly positive
eigefunction $g$ associated to an eigenvalue $\lambda$, it holds $g=f_{1}$ and
$\lambda=\lambda_{1}$. From the eigenvalue equation, we have

(10) $\displaystyle\sum_{v\sim
u}\omega_{uv}\phi_{p}(f_{1}(u)-f_{1}(v))=\big{(}\lambda_{1}\varrho_{u}-\kappa_{u}\big{)}\,f_{1}(u)^{p-1}$
(11) $\displaystyle\sum_{v\sim
u}\omega_{uv}\phi_{p}(g(u)-g(v))=\big{(}\lambda\varrho_{u}-\kappa_{u}\big{)}\,g(u)^{p-1}$

where $\phi_{p}$ is defined in Section 2. If we multiply both sides of (10) by
the function $f_{1}(u)-g(u)^{p}f_{1}(u)^{1-p}$ and both sides of (11) by
$g(u)-f_{1}(u)^{p}g(u)^{1-p}$, we obtain

$\displaystyle\sum_{v\sim
u}\omega_{uv}\phi_{p}\big{(}f_{1}(u)\\!-\\!f_{1}(v)\big{)}\Big{(}\\!f_{1}(u)\\!-\\!g(u)^{p}f_{1}(u)^{1-p}\\!\Big{)}\\!=\\!\big{(}\lambda_{1}\varrho_{u}-\\!\kappa_{u}\big{)}\Big{(}\\!f_{1}(u)^{p}-\\!g(u)^{p}\\!\Big{)},$
$\displaystyle\sum_{v\sim
u}\omega_{uv}\phi_{p}\big{(}g(u)-g(v)\big{)}\Big{(}g(u)-f_{1}(u)^{p}g(u)^{1-p}\Big{)}\\!=\\!\big{(}\lambda\varrho_{u}-\kappa_{u}\big{)}\Big{(}g(u)^{p}-f_{1}(u)^{p}\Big{)}.$

Summing the two equations first together and then over all the vertices, we
obtain

(12) $S(f_{1},g)+S(g,f_{1})=\big{(}\lambda_{1}-\lambda\big{)}\sum_{u\in
V}\varrho_{u}\Big{(}f_{1}(u)^{p}-g(u)^{p}\Big{)}$

with

$S(f,g)=\sum_{uv\in
E}\omega_{uv}\Bigg{(}|g(u)-g(v)|^{p}-\phi_{p}(f(u)-f(v))\Big{(}\frac{g(u)^{p}}{f(u)^{p-1}}-\frac{g(v)^{p}}{f(v)^{p-1}}\Big{)}\Bigg{)}\,.$

If we apply Lemma A.1 to the above sums first with
${\alpha={f_{1}(u)}/{f_{1}(v)}>0}$ and then with $\alpha={g(u)}/{g(v)}>0$, we
deduce that both $S(f_{1},g)$ and $S(g,f_{1})$ are non-negative. Thus, if
$\lambda=\lambda_{1}$, in which case $S(f_{1},g)=S(g,f_{1})=0$, again using
Lemma A.1, we obtain

$\displaystyle{\frac{g(u)}{g(v)}=\frac{f_{1}(u)}{f_{1}(v)}}\,,$

which shows that, since the graph is connected, $g$ is proportional to
$f_{1}$, implying $\lambda_{1}$ simple. This allows us to conclude that
$f_{1}$ and $g$ are the same eigenfunction. Assume now that there exists an
eigenvalue $\lambda>\lambda_{1}$ with the associated eigenfunction $g$ being
strictly positive. For any $\varepsilon>0$, the function $\varepsilon g$ is
also a strictly positive eigenfunction associated with $\lambda$. Thus we can
find a $\varepsilon>0$ such that $f_{1}(u)>\varepsilon{g(u)}$ for all
$u\in{V}$. This yields an absurd in (12) as the left hand side term is
strictly positive and the right hand side is strictly negative. Thus, every
eigenfunction that does not change sign has to be necessarily associated to
the first eigenvalue and this concludes the proof. ∎

The following corollary is a direct consequence of Theorem 4.1 and generalizes
to $\mathcal{H}_{p}$ a well-known property of the eigenfunctions of the
standard $p$-Laplacian (see e.g. [40, Cor. 3.6])

######  Corollary 4.2.

The first eigenvalue $\lambda_{1}$ of the generalized $p$-Laplacian operator
defined on a connected graph is simple, i.e. $\lambda_{1}<\lambda_{2}$, and
any eigenvector associated to an eigenvalue different from $\lambda_{1}$ has
at least two nodal domains.

###  4.2. The largest variational eigenvalue

Opposite to the case of the first variational eigenvalue, the last variational
eigenvalue realizes the maximum of the Rayleigh quotient:

$\lambda_{N}=\max_{f\in\mathcal{S}_{p}}\mathcal{R}_{\mathcal{H}_{p}}(f)$

and, following [3], one can provide an upper bound to the magnitude of
$\lambda_{N}$ in terms of $\omega,\varrho$ and the potential $\kappa$.

######  Proposition 4.3.

The largest variational eigenvalue $\lambda_{N}$ of the generalized
$p$-Laplacian operator $\mathcal{H}_{p}$ defined on a connected graph
satisfies:

$|\lambda_{N}|\leq\max_{u\in V}\ \Big{(}2^{p-1}\sum_{v\sim
u}\frac{\omega_{uv}}{\varrho_{u}}+\frac{|\kappa_{u}|}{\varrho_{u}}\Big{)}\,.$

###### Proof.

Let $f_{N}$ be an eigenfunction associated to $\lambda_{N}$ and let $u_{0}$ be
a node where $\varrho f_{N}$ assumes the maximal absolute value
$|\varrho_{u_{0}}f_{N}(u_{0})|=\max_{v\in V}|\varrho_{v}f_{N}(v)|$. Then, from
the eigenvalue equation, we have

$\varrho_{u_{0}}|\lambda_{N}||f_{N}(u_{0})|^{p-1}=\Big{|}\sum_{v\sim
u_{0}}\omega_{u_{0}v}\phi_{p}\big{(}f_{N}(u_{0})-f_{N}(v)\big{)}+\kappa_{u_{0}}\phi_{p}\big{(}f_{N}(u_{0})\big{)}\Big{|}$

from which we obtain

$|\lambda_{N}|\leq\sum_{v\sim
u_{0}}\frac{\omega_{u_{0}v}}{\varrho_{u_{0}}}2^{p-1}+\frac{|\kappa_{u_{0}|}}{\varrho_{u_{0}}}\leq\max_{u\in
V}\ \big{(}2^{p-1}\sum_{v\sim
u}\frac{\omega_{uv}}{\varrho_{u}}+\frac{|\kappa_{u}|}{\varrho_{u}}\big{)}.\qed$

As done for the first eigenfunction, we provide here a characterization of the
sign pattern of the last (maximal) eigenfunction in the particular case of
bipartite graphs. Our result extends to the generalized $p$-Laplacian the
analogous results obtained in the linear case in [33, 8] and in the case of
the $p$-Laplacian with Dirichlet boundary conditions in [28].

######  Theorem 4.4.

If $\mathcal{G}$ is a bipartite connected graph, then the largest eigenvalue
$\lambda_{N}$ of $\mathcal{H}_{p}$ is simple and the corresponding unique
eigenfunction $f_{N}$ is such that $f_{N}(u)f_{N}(v)<0$, for any $u\sim v$.

###### Proof.

We start by proving that if $f\in\mathcal{S}_{p}$ is a maximizer of the
Rayleigh quotient, necessarily $f(u)f(v)<0$, $\forall u\sim v$. Indeed, since
$\mathcal{G}$ is a bipartite graph we can decompose $V$ into two subsets
$V=V_{1}\sqcup V_{2}$, such that if $u,v\in V_{i}$, $i=1,2$, then $u\not\sim
v$. Thus, starting from $f$, we define $f^{\prime}$ such that
$f^{\prime}(u)=|f(u)|$, $\forall u\in V_{1}$ and $f^{\prime}(u)=-|f(u)|$,
$\forall u\in V_{2}$. Now observe that

$\displaystyle\begin{aligned} \mathcal{R}_{\mathcal{H}_{p}}(f)&=\sum_{uv\in
E}\omega_{uv}|f(u)-f(v)|^{p}+\sum_{u\in V}\kappa_{u}|f(u)|^{p}\\\
&\leq\sum_{uv\in E}\omega_{uv}\big{|}|f(u)|+|f(v)|\big{|}^{p}+\sum_{u\in
V}\kappa_{u}|f(u)|^{p}=\mathcal{R}_{\mathcal{H}_{p}}(f^{\prime})\end{aligned}$

where the equality holds if and only if $f=\pm f^{\prime}$. Since $f$ is a
maximal eigenfunction, then $f=f^{\prime}$ up to a sign and thus $f(u)f(v)\leq
0$, $\forall u\sim v$. To conclude, if $f^{\prime}(u)=0$ then, for $u\in
V_{1}$ we have $\lambda_{n}f^{\prime}(u)=\mathcal{H}_{p}(f^{\prime})(u)\leq 0$
and the equality holds only if $f^{\prime}(v)=0$ for every $v\sim u$. Since
the graph is connected this would lead to the absurd $f^{\prime}\equiv 0$.
Thus, we have that $f^{\prime}(u)\neq 0$, $\forall u$, implying $f(u)f(v)<0$,
$\forall u\sim v$.

We now prove uniqueness of the maximizer. Given two maximizers
$f,g\in\mathcal{S}_{p}$ such that

$\mathcal{R}_{\mathcal{H}_{p}}(f)=\lambda_{n}=\mathcal{R}_{\mathcal{H}_{p}}(g)\,,$

up to a sign as above, $f$ and $g$ must be strictly greater than zero on
$V_{1}$ and strictly smaller than zero on $V_{2}$. Then, similarly to the
proof of Theorem 4.1, we first multiply the eigenvalue equations for $f$ and
$g$ by ${f(u)-{|g(u)|^{p}}/{\phi_{p}(f(u))}}$ and
${g(u)-{|f(u)|^{p}}/{\phi_{p}(g(u))}}$, respectively. Then, we sum the two
equations together and over all the nodes to obtain:

$\sum_{uv\in
E}\omega_{uv}\bigg{(}|g(u)-g(v)|^{p}-\phi_{p}\big{(}(f(u)-f(v)\big{)}\Big{(}\frac{|g(u)|^{p}}{\phi_{p}\big{(}f(u)\big{)}}-\frac{|g(v)|^{p}}{\phi_{p}\big{(}f(v)\big{)}}\Big{)}\bigg{)}+\\\
\sum_{uv\in
E}\omega_{uv}\bigg{(}|f(u)-f(v)|^{p}-\phi_{p}\big{(}g(u)-g(v)\big{)}\Big{(}\frac{|f(u)|^{p}}{\phi_{p}\big{(}g(u)\big{)}}-\frac{|f(v)|^{p}}{\phi_{p}\big{(}g(v)\big{)}}\Big{)}\bigg{)}=0$

From Lemma A.1, both the sums above are smaller than zero unless $f=g$, thus
showing uniqueness of the maximizer and hence of the maximal eigenfunction
$f_{N}$. ∎

######  Corollary 4.5.

Consider a graph $\mathcal{G}$ and the generalized $p$-Laplacian operator
$\mathcal{H}_{p}$. Then, the graph $\mathcal{G}$ is bipartite and connected if
and only if the maximal eigenfunction $f_{N}$ of $\mathcal{H}_{p}$ induces
exactly $N$ nodal domains.

###### Proof.

If the graph is bipartite, by Theorem 4.4 the $N$-th variational eigenfunction
is unique and induces $N$ nodal domains. Vice-versa, let $f_{N}$ be an
eigenfunction such that $f_{N}$ induces exactly $N$ nodal domains. Then,
considering $V_{1}=\\{v|f_{N}(v)>0\\}$ and $V_{2}=\\{v|f_{N}(v)<0\\}$, we have
$V=V_{1}\sqcup V_{2}$ and each node in $V_{1}$ is connected only to nodes in
$V_{2}$, showing that the graph is bipartite. ∎

###  4.3. Further properties of $\mathcal{H}_{p}$ and its eigenfunctions

Observe that, similarly to the linear Schrödinger operator and unlike the
$p$-Laplacian case, the eigenvalues of the generalized $p$-Laplacian depend on
the potential $\kappa_{u}$ and may attain both positive and negative values.
This follows directly from the eigenvalue equation (2) for
$(\lambda_{1},f_{1})$:

$\sum_{v\sim
u}\Big{(}\omega_{uv}|f_{1}(u)-f_{1}(v)|^{p-2}(f_{1}(u)-f_{1}(v))\Big{)}+\kappa_{u}f_{1}(u)^{p-1}=\lambda_{1}\,\varrho_{u}f_{1}(u)^{p-1}\,.$

In fact, summing over all the vertices $u\in{V}$ yields

$\lambda_{1}=\frac{\sum_{u\in V}\kappa_{u}f_{1}(u)^{p-1}}{\sum_{u\in
V}\varrho_{u}f_{1}(u)^{p-1}}=\frac{\sum_{u\in
V}\frac{\kappa_{u}}{\varrho_{u}}\varrho_{u}f_{1}(u)^{p-1}}{\sum_{u\in
V}\varrho_{u}f_{1}(u)^{p-1}}$

which shows that $\lambda_{1}$ is in the convex hull of the coefficients
$\\{\frac{\kappa_{u}}{\varrho_{u}}\\}$ and, since $\kappa_{u}$ may be
negative, $\mathcal{H}_{p}$ may not be positive definite.

The next lemmas extend to the generalized $p$-Laplacian the results proved in
[40] for the standard $p$-Laplacian, and provide partial orderings for the
given eigenpairs. In particular, Lemma 4.6 below follows directly by replacing
the standard $p$-Laplacian with the generalized operator $\mathcal{H}_{p}$ in
the proof of [40, Lemma 3.8] and, for this reason, its proof is omitted.

######  Lemma 4.6.

If $f$ is an eigenfunction relative to an eigenvalue $\lambda$ and
$A_{1},\dots,A_{m}$ are the nodal domains of $f$, consider $f|_{A_{i}}$ the
function that is equal to $f$ on $A_{i}$ and zero on $V\setminus A_{i}$. Then

$\max\Big{\\{}\mathcal{R}_{\mathcal{H}_{p}}(f):f\in\mathrm{span}\\{f|_{A_{1}},\dots,f|_{A_{m}}\\}\Big{\\}}\leq\lambda\,.$

######  Corollary 4.7.

If $f$ is an eigenfunction relative to an eigenvalue $\lambda$ and $f$ induces
$k$ nodal domains, then $\lambda\geq\lambda_{k}$.

###### Proof.

If $A_{1},\dots,A_{k}$ are the nodal domains of $f$, consider $f|_{A_{i}}$ the
function that is equal to $f$ on $A_{i}$ and zero on $V\setminus A_{i}$. If
$\mathcal{A}=\mathrm{span}\\{f|_{A_{1}},\dots,f|_{A_{k}}\\}$, then notice that
the Krasnoselskii genus of $\mathcal{A}$ is $k$, i.e.,
$\gamma(\mathcal{A})=k$. Thus, from Lemma 4.6, we have that
$\lambda_{k}=\min_{A\in\mathcal{F}_{k}}\max_{f\in
A}\mathcal{R}_{\mathcal{H}_{p}}\leq\max_{f\in\mathcal{A}}\mathcal{R}_{\mathcal{H}_{p}}(f)\leq\lambda$.
∎

We conclude by noticing that, combining Corollaries 4.2 and 4.7, one
immediately obtains that, as for the standard $p$-Laplacian, the second
variational eigenvalue $\lambda_{2}$ of the generalized $p$-Laplacian is the
smallest eigenvalue larger than $\lambda_{1}$. Precisely, it holds:

$\lambda_{2}=\min\\{\lambda:\lambda>\lambda_{1}\text{ is an eigenvalue of
}\mathcal{H}_{p}\\}$

##  5\. Graph perturbations and Weyl’s-like inequalities

In this section we show how to modify the graph and, consequently, the
associated generalized $p$-Laplacian operator, maintaining eigenpairs. In
particular, we will show how to remove edges and nodes obtaining a new
generalized $p$-Laplacian operator on a simpler graph written as a “small”
perturbation of the initial operator $\mathcal{H}_{p}$. For this perturbed
operator, we will prove Weyl’s like inequalities relating its variational
eigenvalues to those of the starting operator.

###  5.1. Removing an edge

Consider a graph $\mathcal{G}$ and the generalized $p$-Laplacian operator
$\mathcal{H}_{p}$ on $\mathcal{G}$. Let $\lambda$ and $f$ be an eigenvalue and
a corresponding eigenfunction of $\mathcal{H}_{p}$ and let
$e_{0}=(u_{0},v_{0})$ be an edge of the graph such that $f(u_{0})f(v_{0})\neq
0$. We want to define a new generalized $p$-Laplacian operator
$\mathcal{H}^{\prime}_{p}$ on the graph
$\mathcal{G}^{\prime}:=\mathcal{G}\setminus e_{0}$, such that $(f,\lambda)$ is
also an eigenpair of $\mathcal{H}_{p}^{\prime}$.

Our strategy extends to the nonlinear case the work of [5], where the new
operator $\mathcal{H}_{p}^{\prime}$ is written as a rank-one variation of the
starting Laplacian. To this end, we write
$\mathcal{H}^{\prime}_{p}=\mathcal{H}_{p}+\Xi_{p}$ where

(13) $(\Xi_{p}g)(u)=\begin{cases}0&\text{if $u\neq\;u_{0},v_{0}$}\\\
\omega_{u_{0}v_{0}}\Big{(}\phi_{p}(1-\alpha)\phi_{p}\big{(}g(u_{0})\big{)}-\phi_{p}\big{(}g(u_{0})-g(v_{0})\big{)}\Big{)}&\text{if
$u=u_{0}$}\\\
\omega_{u_{0}v_{0}}\Big{(}\phi_{p}(1-\frac{1}{\alpha})\phi_{p}\big{(}g(v_{0})\big{)}-\phi_{p}\big{(}g(v_{0})-g(u_{0})\big{)}\Big{)}&\text{if
$u=v_{0}$}\end{cases}\,,$

$\alpha:={f(v_{0})}/{f(u_{0})}$ and $\phi_{p}(x):=|x|^{p-2}x$ as before. It
can be easily proved that $\mathcal{H}^{\prime}_{p}$ is obtained from
$\mathcal{H}_{p}$ by considering the edge weights $\omega^{\prime}$ given by
$\omega^{\prime}_{uv}=\omega_{uv}$ if $(uv)\neq(u_{0}v_{0})$ and
$\omega^{\prime}_{u_{0}v_{0}}=0$. Thus $\mathcal{H}^{\prime}_{p}$ can be seen
as a generalized $p$-Laplacian operator on a graph $\mathcal{G^{\prime}}$ that
is obtained from $\mathcal{G}$ by deleting the edge $e_{0}$ and that acts on
the nodes that are not adjacent to $e_{0}$ exactly as $\mathcal{H}_{p}$ does.
Observe that $\mathcal{H}_{p}^{\prime}$ depends on the original eigenfunction
$f$ and a direct computation shows that $(\lambda,f)$ is still an eigenpair of
the new operator.

Now we want to compare the variational eigenvalues of
$\mathcal{H}^{\prime}_{p}$ with the ones of $\mathcal{H}_{p}$ with ordering
purposes. We first write the Rayleigh quotient of the new operator
$\mathcal{H}^{\prime}_{p}$ as

$\mathcal{R}_{\mathcal{H}^{\prime}_{p}}(g)=\mathcal{R}_{\mathcal{H}_{p}}(g)+\mathcal{R}_{\Xi_{p}}(g)\,,$

where, for $g\in\mathcal{S}_{p}$:

(14)
$\frac{\mathcal{R}_{\Xi_{p}}(g)}{\omega_{u_{0}v_{0}}}=\left(\frac{|g(u_{0})|^{p}}{\phi_{p}(f(u_{0}))}-\frac{|g(v_{0})|^{p}}{\phi_{p}(f(v_{0}))}\right)\phi_{p}\big{(}f(u_{0})-f(v_{0})\big{)}\\\
-\big{(}g(u_{0})-g(v_{0})\big{)}\phi_{p}\Big{(}g(u_{0})-g(v_{0})\Big{)}\,.$

A direct application of Lemma A.1, shows that $R_{\Xi_{p}}$ is positive if
$\frac{f(v_{0})}{f(u_{0})}$ is negative and negative if
$\frac{f(v_{0})}{f(u_{0})}$ is positive. Moreover, if we assume that
$g(v_{0})$ and $g(u_{0})$ are non zero, we can write $\Xi_{p}g$ in the
following equivalent way

$(\Xi_{p}g)(u)=\begin{cases}0&\text{if $u\neq\;u_{0},v_{0}$}\\\
\omega_{u_{0}v_{0}}\phi_{p}\big{(}g(u_{0})\big{)}\Big{(}\phi_{p}(1-\alpha)-\phi_{p}(1-\frac{g(v_{0})}{g(u_{0})}\Big{)}&\text{if
$u=u_{0}$}\\\
\omega_{u_{0}v_{0}}\phi_{p}\big{(}g(v_{0})\big{)}\Big{(}\phi_{p}(1-\frac{1}{\alpha})-\phi_{p}(1-\frac{g(u_{0})}{g(v_{0})})\Big{)}&\text{if
$u=v_{0}$}\end{cases}\,.$

From this last equation we can easily see that, if $g(v_{0})=\alpha g(u_{0})$,
then $\Xi_{p}g=\mathcal{R}_{\Xi_{p}}(g)=0$.

To continue, we need the following lemma from [37], reported here without
proof, which provides a bound on the Krasnoselskii genus of the intersection
of different subsets.

######  Lemma 5.1.

[37, Prop. 4.4] Let $X$ be a Banach space and $\mathcal{A}$ the class of the
closed symmetric subsets of $X$. Given $A\in\mathcal{A}$, consider a
Karsnoselskii test map $\varphi\in\Lambda_{k}(A)$ with $k<\gamma(A)$. Then,
$\gamma(\varphi^{-1}(0))\geq\gamma(A)-k$.

Using the fact that $R_{\Xi_{p}}$ is zero on the hyperplane
$\pi=\\{g:g(u_{0})f(v_{0})-g(v_{0})f(u_{0})=0\\}$, we obtain the following
ordering of the $k$-th eigenvalue of $\mathcal{H}_{p}$ within the spectrum of
$\mathcal{H}_{p}^{\prime}$.

######  Lemma 5.2.

Assume that there exist an eigenfunction $f$ of $\mathcal{H}_{p}$ and an edge
$e_{0}=(u_{0},v_{0})$ such that $f(u_{0}),f(v_{0})\neq 0$ and consider the
operator $\mathcal{H}^{\prime}_{p}=\mathcal{H}_{p}+\Xi_{p}$, where $\Xi_{p}$
is defined as in (13). Let $\eta_{k}$ be the variational eigenvalues of
$\mathcal{H}^{\prime}_{p}$ and $\lambda_{k}$ those of $\mathcal{H}_{p}$. The
following inequalities hold:

  * •

If $\frac{f(v_{0})}{f(u_{0})}<0$, then
$\eta_{k-1}\leq\lambda_{k}\leq\eta_{k}$;

  * •

If $\frac{f(v_{0})}{f(u_{0})}>0$, then
$\eta_{k}\leq\lambda_{k}\leq\eta_{k+1}$.

###### Proof.

Let $\mathcal{F}_{k}$ be the Krasnoselskii family
$\mathcal{F}_{k}=\\{A\subseteq\mathcal{A}\cap\mathcal{S}_{p}|\gamma(A)\geq
k\\}$ as defined in Section 3. Let $A_{k}\in\mathcal{F}_{k}$ be such that
$\lambda_{k}=\max_{f\in A_{k}}\mathcal{R}_{\mathcal{H}_{p}}(f)\,,$ and let

$\pi=\\{g:g(u_{0})f(v_{0})-g(v_{0})f(u_{0})=0\\}\,.$

Then $A_{k}\cap\pi=\phi|_{A_{k}}^{-1}(0)$, and from Lemma 5.1, since
$\phi|_{A_{k}}\in\Lambda_{1}(A_{k})$, we have

$\gamma(A_{k}\cap\pi)\geq\gamma(A_{k})-1\geq k-1\,.$

Thus, $A_{k}\cap\pi\in\mathcal{F}_{k-1}$ and

$\eta_{k-1}=\min_{A\in\mathcal{F}_{k-1}}\max_{f\in
A}\mathcal{R}_{\mathcal{H}^{\prime}_{p}}(f)\leq\max_{f\in
A_{k}\cap\pi}\mathcal{R}_{\mathcal{H}^{\prime}_{p}}(f)=\max_{f\in
A_{k}\cap\pi}\mathcal{R}_{\mathcal{H}_{p}}+\mathcal{R}_{\Xi_{p}}\leq\lambda_{k}\,.$

This implies that $\eta_{k-1}\leq\lambda_{k}$. Moreover, since
$\mathcal{R}_{\Xi_{p}}\geq 0$ we have that
$\mathcal{R}_{\mathcal{H}^{\prime}_{p}}(f)\geq\mathcal{R}_{\mathcal{H}_{p}}$,
which implies

$\lambda_{k}=\min_{A\in\mathcal{F}_{k}}\max_{f\in
A}\mathcal{R}_{\mathcal{H}_{p}}(f)\leq\min_{A\in\mathcal{F}_{k}}\max_{f\in
A}\mathcal{R}_{\mathcal{H}^{\prime}_{p}}(f)=\eta_{k}\,,$

and this concludes the proof of the first inequality. The second inequality
can be proved analogously, by exchanging the roles of
$\mathcal{H}^{\prime}_{p}$ and $\mathcal{H}_{p}$. ∎

###  5.2. Removing a node

Consider a generalized $p$-Laplacian operator $\mathcal{H}_{p}$ defined on a
graph $\mathcal{G}$ and let $u_{0}$ be a node of $\mathcal{G}$. We want to
define a new operator $\mathcal{H}^{\prime}_{p}$ on the graph
$\mathcal{G}^{\prime}:=\mathcal{G}\setminus\\{u_{0}\\}$ that behaves on
$\mathcal{G}^{\prime}$ like $\mathcal{H}_{p}$ behaves on the hyperplane
$\\{f\,:\,f(u_{0})=0\\}$. Note that, in the linear case, this operation is
equivalent to considering the principal submatrix of the generalized Laplacian
matrix obtained by removing the row and the column relative to $u_{0}$. If we
remove a node $u_{0}$, we have to remove also all its incident edges from the
graph $\mathcal{G}$. Thus, on the graph $\mathcal{G}^{\prime}$ we can define
the generalized $p$-Laplacian:

(15) $\mathcal{H}_{p}^{\prime}(f)(u):=\sum_{v\in
V^{\prime}}\omega^{\prime}_{uv}\phi_{p}(f(u)-f(v))+\kappa^{\prime}_{u}\phi_{p}(f(u))\,,$

where $V^{\prime}=V\setminus\\{u_{0}\\}$, $\omega^{\prime}_{uv}=\omega_{uv}$
and $\kappa^{\prime}_{u}=\kappa_{u}+\omega_{uu_{0}}$.

######  Remark 5.3.

If $f$ is an eigenfunction of the generalized $p$-Laplacian $\mathcal{H}_{p}$
on $\mathcal{G}$, with eigenvalue $\lambda$ and such that $f(u_{0})=0$, then
the restriction $f^{\prime}$ of $f$ on the graph
$\mathcal{G}^{\prime}=\mathcal{G}\setminus\\{u_{0}\\}$ is automatically an
eigenfunction of $\mathcal{H}_{p}^{\prime}$ with eigenvalue $\lambda$. Indeed,
for each $u\neq u_{0}$ we have

$\lambda\varrho_{u}\phi_{p}(f(u))=\sum_{v\neq
u_{0}}\omega_{uv}\phi_{p}(f(u)-f(v))+\omega_{uu_{0}}\phi_{p}(f(u))+\kappa_{u}\phi_{p}(f(u))=\mathcal{H}_{p}^{\prime}(f)(u)\,.$

Next, we provide an ordering for the variational eigenvalues of
$\mathcal{H}^{\prime}_{p}$, in comparison with those of $\mathcal{H}_{p}$, as
stated in the following lemma.

######  Lemma 5.4.

Given a node $u_{0}$ of $\mathcal{G}$, let $\mathcal{H}_{p}$ and
$\mathcal{H}^{\prime}_{p}$ be generalized $p$-Laplacian operators defined on
the graphs $\mathcal{G}$ and
$\mathcal{G}^{\prime}=\mathcal{G}\setminus\\{u_{0}\\}$, respectively, and let
$\lambda_{k}$ and $\eta_{k}$ be the corresponding variational eigenvalues.
Then:

$\lambda_{k}\leq\eta_{k}\leq\lambda_{k+1}\,.$

###### Proof.

Let $\mathcal{S}_{p}^{\prime}=\\{f:V^{\prime}\to\mathbb{R}:\|f\|_{p}=1\\}$ and
consider $A_{k}^{\prime}\in\mathcal{F}_{k}(\mathcal{S}_{p}^{\prime})$ such
that

$\eta_{k}=\max_{f\in
A_{k}^{\prime}}\mathcal{R}_{\mathcal{H}^{\prime}_{p}}(f)=\max_{f\in
A_{k}^{\prime}}\sum_{(uv)\in
E^{\prime}}w^{\prime}(uv)|f(u)-f(v)|^{p}+\sum_{u\in
V^{\prime}}\kappa^{\prime}_{u}|f(u)|^{p}\,,$

where $E^{\prime}$ is the set of edges of $\mathcal{G}^{\prime}$. Consider now
$A_{k}$, the immersion of $A_{k}^{\prime}$ in the $N-1$ dimensional hyperplane
$\pi=\\{f:V\to\mathbb{R}:f(u_{0})=0\\}$, i.e. the set of functions $f$ that,
when restricted to the nodes different from $u_{0}$, belong to
$A_{k}^{\prime}$ and are such that $f(u_{0})=0$. Thus, $A_{k}$ belongs to
$\mathcal{F}_{k}(\mathcal{S}_{p})$ since $A_{k}$ and $A_{k}^{\prime}$ are
homeomorphic, and we obtain:

$\lambda_{k}=\min_{A\in\mathcal{F}_{k}}\max_{f\in
A}\mathcal{R}_{\mathcal{H}_{p}}(f)\leq\max_{f\in
A_{k}}\mathcal{R}_{\mathcal{H}_{p}}(f)=\max_{f\in
A_{k}^{\prime}}\mathcal{R}_{\mathcal{H}_{p}^{\prime}}(f)=\eta_{k}\,.$

To prove the other inequality, consider
$A_{k+1}\in\mathcal{F}_{k+1}(\mathcal{S}_{p})$ such that

$\lambda_{k+1}=\max_{f\in A_{k+1}}\mathcal{R}_{\mathcal{H}_{p}}(f)\,.$

Because of Lemma 5.1, we have that $\gamma(A_{k+1}\cap\\{f:f(u_{0})=0\\})\geq
k$, which implies that
$A_{k+1}\cap\\{f:f(u_{0})=0\\}\in\mathcal{F}_{k}(\mathcal{S}_{p})$. Thus

$\eta_{k}\leq\max_{f\in
A_{k}^{\prime}}\mathcal{R}_{\mathcal{H}_{p}^{\prime}}(f)=\max_{f\in
A_{k+1}\cap\pi}\mathcal{R}_{\mathcal{H}_{p}}(f)\leq\max_{f\in
A_{k+1}}\mathcal{R}_{\mathcal{H}_{p}}(f)=\lambda_{k+1}\,,$

where $A_{k}^{\prime}$ is the set of functions
$f^{\prime}:V^{\prime}\to\mathbb{R}$ obtained as the restriction of functions
from $A_{k+1}\cap\pi$ to $\mathcal{G}^{\prime}$, i.e., $f^{\prime}\in
A_{k}^{\prime}$ if the lifting $f:V\to\mathbb{R}$ defined as $f(u_{0})=0$ and
$f(u)=f^{\prime}(u)$, $\forall u\neq u_{0}$, belongs to $A_{k+1}\cap\pi$. ∎

This result can be generalized by induction to the case of $n$ removed nodes,
obtaining the main theorem of this section.

######  Theorem 5.5.

Let $\mathcal{H}_{p}$ be the generalized $p$-Laplacian operator defined on the
graph $\mathcal{G}$ and let $\mathcal{G}^{\prime}$ be the graph obtained from
$\mathcal{G}$ by deleting the $n$ nodes $u_{1},u_{2},\dots,u_{n}$. Consider
the generalized $p$-Laplacian operator on $\mathcal{G}^{\prime}$ defined as

$\mathcal{H}_{p}^{\prime}(u):=\sum_{v\in
V^{\prime}}\omega^{\prime}_{uv}\phi_{p}(f(u)-f(v))+\kappa^{\prime}_{u}\phi_{p}(f(u))\,,$

where $V^{\prime}=V\setminus\\{u_{1},\dots,u_{n}\\}$,
$\omega^{\prime}_{uv}=\omega_{uv}$ and
$\kappa^{\prime}_{u}=\kappa_{u}+\sum_{i=1}^{n}\omega_{uu_{i}}$. Let
$\\{\lambda_{k}\\}$ denote the variational eigenvalues of $\mathcal{H}_{p}$
and $\\{\eta_{k}\\}$ those of $\mathcal{H}_{p}^{\prime}$. Then

$\lambda_{k}\leq\eta_{k}\leq\lambda_{k+n}\,,$

for any $k\in\\{1,\dots,|V|-n\\}$.

###### Proof.

The proof follows directly from Lemma 5.4, removing recursively the nodes
$u_{1},\dots,u_{n}$. ∎

##  6\. Nodal domain count on trees (proofs of Theorems 3.7 and 3.8)

In this section we deal with the case in which
$\mathcal{T}:=\mathcal{G}=(V,E)$ is a tree and we provide proofs of the two
Theorems 3.7 and 3.8. In particular, we will prove that the eigenvalues of the
generalized $p$-Laplacian on a tree are all and only the variational ones.
Moreover, again restricting ourselves to trees, we will show that, if an
eigenfunction of the $k$-th variational eigenvalue is everywhere non zero,
then it induces exactly $k$ nodal domains. This generalizes to the nonlinear
case a well-known result for the linear Shrödinger operator.

In the following, given a tree $\mathcal{T}=(V,E)$, we assume a root $r\in V$
is chosen arbitrarily. This provides a partial ordering of the nodes so that a
precise root is automatically assigned to any subtree of $\mathcal{T}$. In
particular, we write $v<u$ if $v$ is a descendant of $u$ and $v\prec u$ if $v$
is a direct child of $u$. Moreover, for each node $u\in V$, we let
$\mathcal{T}_{u}$ denote the subtree of $\mathcal{T}$ having $u$ as root and
formed by all the descendants of $u$. On this subtree we can define a new
operator $\mathcal{H}_{p}^{u}$ obtained as follows: starting from
$\mathcal{T}$, we remove all the nodes that do not belong to $\mathcal{T}_{u}$
and, for each deleted node, we modify the original operator $\mathcal{H}_{p}$
on $\mathcal{T}$ as in Section 5.2.

We also consider the operator $\mathcal{H}_{p}^{\widetilde{u}}$, obtained by
removing from $\mathcal{T}_{u}$ also the root node $u$ and by modifying
$\mathcal{H}_{p}^{u}$ accordingly. This latter operator is defined on a
subforest, $\mathcal{T}_{\widetilde{u}}=\sqcup_{i}\mathcal{T}_{i}$, that has
as many connected components as the number of children of $u$. From the
generalized Weyl’s inequalities of Section 5, we have that

(16)
$\cdots\leq\lambda_{i}(\mathcal{H}_{p}^{u})\leq\lambda_{i}(\mathcal{H}_{p}^{\widetilde{u}})\leq\lambda_{i+1}(\mathcal{H}_{p}^{u})\leq\cdots\,$

where $\lambda_{i}(\mathcal{H}_{p}^{u})$ and
$\lambda_{i}(\mathcal{H}_{p}^{\widetilde{u}})$ denote the $i$-th variational
eigenvalue of $\mathcal{H}_{p}^{u}$ and $\mathcal{H}_{p}^{\widetilde{u}}$,
respectively. Observe also that
$\displaystyle\mathcal{H}_{p}^{\widetilde{u}}=\mathop{\oplus}_{v_{i}\prec
u}{\mathcal{H}}_{p}(\mathcal{T}_{i})$, where
${\mathcal{H}}_{p}(\mathcal{T}_{i})$ is the generalized $p$-Laplacian of
$\mathcal{T}_{i}$ and $v_{i}\prec u$ indicates that $v_{i}$ is a direct child
of $u$.

###  6.1. Generating functions

Consider now an eigenfunction $f$ of $\mathcal{H}_{p}$ with eigenvalue
$\lambda$ and assume that $f\neq 0$ everywhere. For each $u$ different from
the root $r$, we denote by $u_{F}$ the parent of $u$ in $\mathcal{T}$. Then,
the following quantity

(17) $g(u):=\frac{f(u_{F})}{f(u)}$

is well defined for all $u\neq r$ and we can rewrite the eigenvalue equation
$\mathcal{H}_{p}(f)(u)=\lambda\varrho_{u}\phi_{p}(f(u))$ as

(18)
$\omega_{uu_{F}}\phi_{p}(1-g(u))=\lambda\varrho_{u}-\kappa_{u}-\sum_{v\prec
u}\omega_{uv}\phi_{p}\Big{(}1-\frac{1}{g(v)}\Big{)}\,,$

for each $u\neq r$.

Now, if $u$ is a leaf, Equation (18) allows us to write $g(u)$ explicitly as a
function of $\lambda$:

(19)
$g_{u}(\lambda)=1+\phi_{p}^{-1}\Big{(}\frac{\kappa_{u}-\varrho_{u}\lambda}{\omega_{uu_{F}}}\Big{)}\,.$

Similarly, for a generic node $u$ different from the root, we can use (18) to
characterize $g(u)$ implicitly as a function of the variable $\lambda$:

(20)
$g_{u}(\lambda)=1+\phi_{p}^{-1}\Bigg{(}\frac{\kappa_{u}-\varrho_{u}\lambda+\sum_{v\prec
u}\omega_{uv}\phi_{p}\Big{(}1-\frac{1}{g_{v}(\lambda)}\Big{)}}{\omega_{uu_{F}}}\Bigg{)}\,.$

Finally, for the root $u=r$, we define

(21)
$g_{r}(\lambda):=1+\phi_{p}^{-1}\Big{(}\kappa_{r}-1-\lambda\varrho_{r}+\sum_{v\prec
r}\omega_{rv}\phi_{p}\Big{(}1-\frac{1}{g_{v}(\lambda)}\Big{)}\Big{)}\,.$

We call the functions $g_{u}$ defined in (19), (20), (21) the generating
functions of the eigenfunction $f$. In fact, we will show in Section 6.2 that
$g_{u}(\lambda)$ characterizes the ratio $f(u_{F})/f(u)$ for any eigenfunction
of $\lambda$ such that $f(u)\neq 0$. To this end, we need a number of
preliminary results to unveil several properties of the generating functions
$g_{u}$.

First, observe that when $f\neq 0$ everywhere, the claimed characterizing
property follows directly from the definition of $g_{u}$. We highlight this
statement in the following remark.

######  Remark 6.1.

If $\lambda$ is an eigenvalue of $\mathcal{H}_{p}^{u_{0}}$ for some $u_{0}\in
V$, and $f$ is an associated eigenfunction such that $f(u)\neq 0$, $\forall
u\in\mathcal{T}_{u_{0}}$, then by the definition of the functions
$g_{u}(\lambda)$ one directly obtains that

$\frac{f(u_{F})}{f(u)}=g_{u}(\lambda)\neq 0,\quad\forall
u\in\mathcal{T}\setminus\\{u_{0}\\}\qquad\text{and}\qquad
g_{u_{0}}(\lambda)=0\,.$

On the other hand, it is not difficult to observe that also the opposite
property holds, namely

######  Remark 6.2.

Assume that $\lambda$ is a zero of $g_{u_{0}}(\lambda)$ and
$g_{u}(\lambda)\neq 0$, for all $u<u_{0}$, i.e., for all the descendents of
$u_{0}$ and not only the direct children. Then $\lambda$ is an eigenvalue of
$\mathcal{H}_{p}^{u_{0}}$ and a corresponding eigenfunction $f$ can be defined
on the subtree $\mathcal{T}_{u_{0}}$ by setting $f(u_{0})=1$ and
$f(u)=\frac{f(u_{F})}{g_{u}(\lambda)}$, for all $u<u_{0}$. Indeed, with these
definitions, (19) and (20) imply that $\lambda$ and $f$ are solutions of the
system of equations

$\displaystyle\begin{cases}\displaystyle\sum_{v\prec
u_{0}}\omega_{u_{0}v}\phi_{p}(f(u_{0})-f(v))+\omega_{u_{0}u_{0,f}}\phi_{p}(f(u_{0}))+\kappa_{u}\phi_{p}(f(u_{0}))=\lambda\varrho_{u}\phi_{p}(f(u_{0}))\,,&\\\\[15.00002pt]
\displaystyle\sum_{v\in\mathcal{G}}\omega_{uv}\phi_{p}(f(u)-f(v))+\kappa_{u}\phi_{p}(f(u))=\lambda\varrho_{u}\phi_{p}(f(u))\qquad\forall
u<u_{0}\,,&\end{cases}$

which shows that $\lambda$ and $f$ are an eigenvalue and an eigenfunction of
$\mathcal{H}_{p}^{u_{0}}$.

We have observed already that it is possible to relate the eigenpairs of the
subtrees of $\mathcal{T}$ with the values of the functions $g_{u}(\lambda)$.
Then, we show that it is always possible to immerse the tree $\mathcal{T}$ in
a larger tree for which the values of the functions $g_{u}(\lambda)$ do not
change.

######  Remark 6.3.

Let $\mathcal{H}_{p}$ be the generalized $p$-Laplacian operator defined on a
tree $\mathcal{T}=(V,E)$. We can always immerse $\mathcal{T}$ in a tree
$\widetilde{\mathcal{T}}$ obtained adding a parent $r_{F}$ to the root $r$.
Next, we define the generalized $p$-Laplacian operator
$\widetilde{\mathcal{H}}_{p}$ on $\widetilde{\mathcal{T}}$ by setting
$\widetilde{\omega}_{uv}=\omega_{uv}$, $\forall(u,v)\in E$,
$\widetilde{\omega}_{rr_{F}}=1$, $\widetilde{\kappa}_{u}=\kappa_{u}$, $\forall
u\in V\setminus\\{r\\}$ and $\widetilde{\kappa}_{r}=\kappa_{r}-1$. Considering
$\widetilde{\mathcal{T}}_{r_{F}}$ and $\widetilde{\mathcal{H}}_{p}^{r_{F}}$,
the subtree and the operator obtained removing the root $r_{F}$ from
$\widetilde{\mathcal{T}}$, it is straightforward to observe that
$\mathcal{T}=\widetilde{\mathcal{T}}_{r_{F}}$ and
$\mathcal{H}_{p}=\widetilde{\mathcal{H}}_{p}^{r_{F}}$. Morover, working on
$\widetilde{\mathcal{T}}$ and the associated operator
$\widetilde{\mathcal{H}}_{p}$, it is possible to introduce the functions
$\widetilde{g}_{u}(\lambda)$ as in (19), (20), (21).

$g_{u}(\lambda)=\widetilde{g}_{u}(\lambda),\quad\forall u\in\mathcal{T}\,.$

Thus, the generalized $p$-Laplacian eigenavalue problem on a tree can always
be studied as the generalized $p$-Laplacian eigenvalue problem on a subtree of
a suitable larger tree.

Finally, the following lemma summarizes several relevant structural properties
of the functions $g_{u}(\lambda)$.

######  Lemma 6.4.

For each $u\in V$, consider the function $g_{u}(\lambda)$ defined as in
(19)–(21). Then:

  1. (1)

the poles of $g_{u}(\lambda)$ are the zeros of the functions
$\\{g_{v}(\lambda)\\}_{v\prec u}$;

  2. (2)

$g_{u}$ is strictly decreasing between each two consecutive poles;

  3. (3)

$\lim_{\lambda\to-\infty}g_{u}=+\infty$,
$\lim_{\lambda\to+\infty}g_{u}=-\infty$, $\lim_{\lambda\to
p^{-}}g_{u}=-\infty$, $\lim_{\lambda\to p^{+}}g_{u}=+\infty$ where $p$ is any
of the poles.

###### Proof.

Let $u\in V$, if $u$ is a leaf then the three properties follow immediately
from (19). Otherwise, assume by induction the thesis holds for each $v\prec
u$. From (20), it immediately follows that the poles of $g_{u}$ are the zeros
of $\\{g_{v}\\}_{v\prec u}$. To show that the function $\sum_{v\prec
u}\omega_{uv}\phi_{p}\Big{(}1-\frac{1}{g_{v}(\lambda)}\Big{)}$ is strictly
decreasing between any couple of neighboring poles, observe that
$x\mapsto\phi_{p}(x)$ is strictly increasing and, by induction, $\forall
v\prec u$, $\lambda\mapsto g_{v}(\lambda)$ is strictly decreasing between any
two of its zeros (i.e. the poles of $g_{u}$). Moreover, since
$\lambda\mapsto-\varrho_{u}\lambda$ is decreasing and $\phi_{p}^{-1}$
increasing, we can conclude that the function $\lambda\mapsto g_{u}(\lambda)$
is strictly decreasing between any two of its poles. Finally, the limits of
$g_{u}(\lambda)$ for $\lambda\to p^{\pm}$ in the third statement follow as a
consequence of the previous observations, while the limits for
$\lambda\to\pm\infty$ can be proved directly by the induction assumption. ∎

###  6.2. Eigenfunction characterization via generating functions

The following result shows that the generating functions $g_{u}(\lambda)$
always characterize the eigenfunctions of $\lambda$, generalizing what
observed earlier in Remark 6.1.

######  Theorem 6.5.

Let $(f,\lambda)$ be an eigenpair of a generalized $p$-Laplacian operator,
$\mathcal{H}_{p}$, defined on a tree $\mathcal{T}=(V,E)$ with root $r$. For
any node $u\in V\setminus\\{r\\}$ such that $f(u)\neq 0$, it holds

$\frac{f(u_{F})}{f(u)}=g_{u}(\lambda)\,,$

where $u_{F}$ is the parent of $u$ in $\mathcal{T}$.

###### Proof.

If $f(v)\neq 0\;\forall v\in\mathcal{T}$ we have already observed in Remark
6.1 that the thesis holds. Assume thus that there exist $v_{1},\dots,v_{k}\in
V$ such that

$f(v_{i})=0,\quad i=1,\dots,k\qquad\text{and}\qquad f(u)\neq 0,\quad\forall
u\not\in\\{v_{i}\\}_{i=1}^{k}$

and let
$\mathcal{T}^{\prime}=\mathop{\sqcup}_{\begin{subarray}{c}i=1\end{subarray}}^{h}\mathcal{T}_{i}$
and
$\mathcal{H}_{p}^{\prime}=\mathop{\oplus}_{i=1}^{h}\mathcal{H}_{p}(\mathcal{T}_{i})$
be the forest and the corresponding operator obtained from $\mathcal{G}$
removing the nodes $v_{1},\dots,v_{k}$ as in Section 5.2. From Remark 5.3,
$\forall\,i=1,\dots,h$, the pair $(f|_{\mathcal{T}_{i}},\lambda)$ is an
eigenpair of $\mathcal{H}_{p}(\mathcal{T}_{i})$ such that
$f|_{\mathcal{T}_{i}}(u)\neq 0,\;\forall\,u\in\mathcal{T}_{i}$. Denoting with
$r_{i}$ the root of $\mathcal{T}_{i}$ and using (19),(20), (21) and Remark
6.1, $\forall\,\mathcal{T}_{i}$, starting from the leaves, we can define
functions $g_{u}^{\mathcal{T}_{i}}(\lambda)$ such that

(22)
$\begin{cases}g_{u}^{\mathcal{T}_{i}}(\lambda)=\displaystyle{\frac{f|_{\mathcal{T}_{i}}(u_{F})}{f|_{\mathcal{T}_{i}}(u)}}\neq
0\qquad\forall u\in\mathcal{T}_{i}\setminus\\{r_{i}\\}\\\\[6.99997pt]
g_{r_{i}}^{\mathcal{T}_{i}}(\lambda)=0\end{cases}$

We claim that $\forall i=1,\dots,h$ and $\forall u\in\mathcal{T}_{i}$, then
$g_{u}(\lambda)=g_{u}^{\mathcal{T}_{i}}(\lambda)$. The thesis follows directly
from this claim since

$g_{u}(\lambda)=g_{u}^{\mathcal{T}_{i}}(\lambda)=\frac{f(u_{F})}{f(u)}\qquad\forall\,u\in\>\mathcal{T}_{i}\,.$

To prove the claim, first we introduce a partial ordering on
$\\{\mathcal{T}_{i}\\}_{i=1}^{h}$ and $\\{v_{j}\\}_{j=1}^{k}$ so that
$\mathcal{T}_{i}\prec v_{j}$ if $v_{j}$ is the parent of the root of
$\mathcal{T}_{i}$, while $v_{j}\prec\mathcal{T}_{i}$ if $v_{j}$ is the child
of some node of $\mathcal{T}_{i}$. Then, if $v_{j}\prec\mathcal{T}_{i}$ there
exists a subtree $\mathcal{T}_{l}\prec v_{j}$. In fact, considering the
generalized $p$-Laplacian eigenvalue equation in $v_{j}$ with
$u_{i}={v_{j}}_{F}\in\mathcal{T}_{i}$, we can write

$\omega_{v_{j}u_{i}}\phi_{p}\Big{(}f(u_{i})\Big{)}+\sum_{u\prec\leavevmode\nobreak\
v_{j}}\omega_{v_{j}u}\phi_{p}\Big{(}f(u)\Big{)}=0\,.$

Since $f(u_{i})\neq 0$, there exists a node $u_{l}\prec v_{j}$ such that
$f(u_{l})\neq 0$ i.e. $u_{l}\in\mathcal{T}_{l}\prec v_{j}$. Similarly, one
observes that if $f(v_{j})=0$, and $v_{j}$ is a leaf, then also
$f({v_{j}}_{F})=0$. Because of these two facts, there exists some
$\mathcal{T}_{i_{0}}$ in the set $\\{\mathcal{T}_{i}\\}_{i=1}^{h}$ such that a
node $v_{j}$ with $v_{j}\prec\mathcal{T}_{i_{0}}$ cannot exists. In addition,
the leaves of $\mathcal{T}_{i_{0}}$ are all and only the leaves of
$\mathcal{T}$ that are connected to $\mathcal{T}_{i_{0}}$. It is then easy to
observe that, for any such $\mathcal{T}_{i_{0}}$, by definition,
$g_{u}^{\mathcal{T}_{i_{0}}}(\lambda)=g_{u}(\lambda)\;\forall\,u\in\mathcal{T}_{i_{0}}$,
$u\neq r_{i_{0}}$. Moreover, when $u=r_{i_{0}}\prec v_{j}$ we have

(23) $\begin{aligned}
g_{r_{i_{0}}}^{\mathcal{T}_{i_{0}}}(\lambda):&=1+\phi_{p}^{-1}\Bigg{(}\kappa_{r_{i_{0}}}^{\prime}-1-\lambda\varrho_{r_{i_{0}}}+\sum_{v\prec{r_{1}}}\omega_{r_{i_{0}}v}\phi_{p}\Big{(}1-\frac{1}{g_{v}(\lambda)}\Big{)}\Bigg{)}=0\end{aligned}\,,$

which implies

(24)
$\kappa_{r_{i_{0}}}+\omega_{r_{i_{0}}v_{j}}-\lambda\varrho_{r_{i_{0}}}+\sum_{v\prec{r_{1}}}\omega_{r_{i_{0}}v}\phi_{p}\Big{(}1-\frac{1}{g_{v}(\lambda)}\Big{)}=0\,,$

where, since $v_{j}$ is one of the removed nodes, we have used the expression
$\kappa_{r_{i_{0}}}^{\prime}=\kappa_{r_{i_{0}}}+\omega_{r_{i_{0}}v_{j}}$ that
we obtain when moving from $\mathcal{H}_{p}$ to $\mathcal{H}_{p}^{\prime}$ as
in Section 5.2.

Thus, (24) implies

(25) $\displaystyle g_{r_{i_{0}}}(\lambda)$
$\displaystyle=1+\phi_{p}^{-1}\Bigg{(}\frac{\kappa_{r_{i_{0}}}-\varrho_{r_{i_{0}}}\lambda_{0}+\sum_{v\prec
r_{i_{0}}}\omega_{r_{i_{0}}v}\phi_{p}\Big{(}1-\frac{1}{g_{v}(\lambda)}\Big{)}}{\omega_{r_{i_{0}}v_{j}}}\Bigg{)}$
$\displaystyle=1+\phi_{p}^{-1}\Bigg{(}\frac{-\omega_{r_{i_{0}}v_{j}}}{\omega_{r_{i_{0}}v_{j}}}\Bigg{)}=0\,,$

that is
$g_{r_{i_{0}}}(\lambda)=g_{r_{i_{0}}}^{\mathcal{T}_{i_{0}}}(\lambda)=0$ and
$\lambda$ is a pole of $g_{v_{j}}$, due to Lemma 6.4.

Now, given a general subtree $\mathcal{T}_{i_{0}}$, w.l.o.g. we can assume
that the claim is true for any $\mathcal{T}_{i}\prec
v_{j}\prec\mathcal{T}_{i_{0}}$. Then if $u$ is a leaf of $\mathcal{T}_{i_{0}}$
that is also a leaf of $\mathcal{T}$, clearly

$g_{u}^{\mathcal{T}_{i_{0}}}(\lambda)=g_{u}(\lambda)\,.$

Consider now the case of a leaf, $u$, of $\mathcal{T}_{i_{0}}$ that is not a
leaf of $\mathcal{T}$. Since $u$ is not a leaf of $\mathcal{T}$, by
construction, there exist some node $v_{j}\prec u$ and some subtree
$\mathcal{T}_{i}\prec v\prec\mathcal{T}_{i_{0}}$. For any such $v_{j}$, by the
inductive assumption, $\lambda$ has to be a pole of the corresponding
$g_{v_{j}}$, leading to the following equation:

(26) $\displaystyle g_{u}(\lambda)$
$\displaystyle=1+\phi_{p}^{-1}\Bigg{(}\frac{\kappa_{u}-\varrho_{u}\lambda+\sum_{v_{j}\prec
u}\omega_{uv_{j}}\phi_{p}\Big{(}1-\frac{1}{g_{v_{j}}(\lambda)}\Big{)}}{\omega_{uu_{F}}}\Bigg{)}$
$\displaystyle=1+\phi_{p}^{-1}\Bigg{(}\frac{\kappa_{u}-\varrho_{u}\lambda+\sum_{v_{i}\prec
u}\omega_{uv_{i}}\phi_{p}(1)}{\omega_{uu_{F}}}\Bigg{)}$
$\displaystyle=1+\phi_{p}^{-1}\Bigg{(}\frac{\kappa_{u}^{\prime}-\varrho_{u}\lambda}{\omega_{uu_{F}}}\Bigg{)}=g_{u}^{\mathcal{T}_{i}}(\lambda)\,.$

Here we have used as before the fact
$\kappa_{u}^{\prime}=\kappa_{u}+\sum_{v_{j}\prec u}\omega_{uv_{j}}$, see
Section 5.2.

The case of $u$ a generic node of $\mathcal{T}_{i_{0}}$ can be proved
analogously assuming, w.l.o.g., the claim true for any $w<u$,
$w\in\mathcal{T}_{i_{0}}$. Indeed, recalling
$\kappa_{u}^{\prime}=\kappa_{u}+\sum_{v_{j}\prec u}\omega_{uv_{j}}$ and that,
by the inductive assumption, $\lambda$ is a pole of $g_{v_{j}}$ for any
$v_{j}\prec u$, we get

(27) $\displaystyle g_{u}(\lambda)$
$\displaystyle=1+\phi_{p}^{-1}\Bigg{(}\omega_{uu_{F}}^{-1}\bigg{(}\kappa_{u}-\varrho_{u}\lambda_{0}+{\sum_{v_{j}\prec
u}}\omega_{uv_{j}}+{\sum_{\begin{subarray}{c}w\prec u\\\
w\in\mathcal{T}_{i_{0}}\end{subarray}}}\omega_{uw}\phi_{p}\Big{(}1-\frac{1}{g_{w}(\lambda)}\Big{)}\bigg{)}\Bigg{)}$
$\displaystyle=1+\phi_{p}^{-1}\Bigg{(}\omega_{uu_{F}}^{-1}\bigg{(}\kappa_{u}^{\prime}-\varrho_{u}\lambda+{\sum_{\begin{subarray}{c}w\prec
u\\\
w\in\mathcal{T}_{i_{0}}\end{subarray}}}\omega_{uw}\phi_{p}\Big{(}1-\frac{1}{g_{w}(\lambda)}\Big{)}\bigg{)}\Bigg{)}=g_{u}^{\mathcal{T}_{i}}(\lambda)$

The case of $u=r_{i_{0}}$ can be finally dealt with as done in (23)(25),
concluding the proof. ∎

######  Corollary 6.6.

Let $(f,\lambda)$ be an eigenpair of $\mathcal{H}_{p}$, then, if
$g_{u}(\lambda)=0$, necessarily $f(u_{F})=0$.

###### Proof.

First, notice that Remark 6.3 allows us to assume that, given any
$u\in\mathcal{T}\setminus{r}$, also the node $u_{F}$ has a parent, since we
can always think of $\mathcal{T}$ as immersed in a larger tree with a suitably
defined generalized $p$-Laplacian. Assume by contradiction that $f(u_{F})\neq
0$, then by Theorem 6.5 we would have that

(28) $\frac{f({u_{F}}_{F})}{f(u_{F})}=g_{u_{F}}(\lambda)\,.$

At the same time, Lemma 6.4 implies that $\lambda$ is a pole of the function
$g_{u_{F}}$, leading to a contradiction. ∎

###  6.3. Multiplicity via generating functions

Theorem 6.5 shows that given any eigenpair $(f,\lambda)$, the generating
functions $\\{g_{u}(\lambda)\\}_{u}$ characterize the value of $f$ up to a
scaling factor. In this section we observe that counting the number of
generating functions that vanishes on the eigenvalue $\lambda$ provides
several insights about its multiplicity.

First, we obtain the following sufficient result for simple eigenvalues, which
directly follows from Theorem 6.5.

######  Proposition 6.7.

Let $\mathcal{H}_{p}$ be the generalized $p$-Laplacian operator defined on a
tree $\mathcal{T}=(V,E)$, and let $u_{0}\in V$. If $g_{u}(\lambda)\neq 0$,
$\forall u<u_{0}$ and $g_{u_{0}}(\lambda)=0$, then $\lambda$ is a simple
eigenvalue of $\mathcal{H}_{p}^{u_{0}}$ associated to an everywhere nonzero
eigenfunction.

###### Proof.

We have alredy observed in Remark 6.2 that such a non zero eigenfunction $f$
exists. Assume by absurd that there exist also an eigenfunction $f^{*}$ of
$\mathcal{H}_{p}^{u_{0}}$ associated to $\lambda$ with $f^{*}\neq cf$,
$\forall c\in\mathbb{R}$. Then, due to Theorem 6.5, there has to exist a node
$v$ such that $f^{*}(v)=0$. Since $f^{*}(v)=0$ and for any node $u$ such that
$f^{*}(u)\neq 0$ it holds that $f^{*}(u_{F})=f^{*}(u)g_{u}(\lambda)\neq 0$,
then necessarily we get that $f^{*}(u)=0$, $\forall u<v$. On the other hand,
by the generalized $p$-Laplacian eigenvalue equation, if $f^{*}(v)=0$ and
$f^{*}(u)=0$, then $\forall u\prec v$ we have in addition that
$f^{*}(u_{F})=0$. Thus, if $f^{*}$ is zero in some node then necessarily
$f^{*}=0$ everywhere, yielding a contradiction. ∎

Next, in the following lemma, we establish a more general condition for
$\lambda$ to be an eigenvalue, counted with its $\gamma$-multiplicity, in
terms of zeros of the generating functions $g_{u}(\lambda)$.

######  Lemma 6.8.

Let $\mathcal{H}_{p}$ be a generalized $p$-Laplacian on a forest $\mathcal{G}$
and, for any $u\in V$ and any tree of the forest, let $g_{u}(\lambda)$ be the
function defined in (19)(20)(21). Given $\lambda$, assume there exist
$v_{1},\dots,v_{k}\in V$ such that

$g_{v_{i}}(\lambda)=0\qquad\forall i=1,\dots,k\,.$

Let $\\{u_{j}\\}_{j=1}^{h}$ be the set of the parents of the nodes
$\\{v_{i}\\}_{i=1}^{k}$, where roots do not have parents. Then, $\lambda$ is
an eigenvalue of $\mathcal{H}_{p}$ if and only if $k-h>0$, and

$\gamma\text{-}\mathrm{mult}(\lambda)=k-h\,.$

###### Proof.

From Theorem 6.5 and Corollary 6.6 we know that if $\lambda$ is an eigenvalue,
any corresponding eigenfunction $f$ is such that

$f(u_{j})=0\qquad\text{and}\qquad\frac{f(w_{F})}{f(w)}=g_{w}(\lambda)\quad\mathrm{if}\;f(w)\neq
0\,.$

Following the strategy of Section 5.2, remove the nodes
$\\{u_{j}\\}_{j=1}^{h}$ from the forest $\mathcal{G}$ ending with a forest
$\mathcal{G}^{\prime}$ and an associated operator $\mathcal{H}_{p}^{\prime}$
of the form

(29)
$\mathcal{G}^{\prime}=\mathop{\sqcup}_{\begin{subarray}{c}l=1\end{subarray}}^{n}\mathcal{T}_{l}\qquad\mathcal{H}_{p}^{\prime}=\mathop{\oplus}_{l=1}^{n}\mathcal{H}_{p}(\mathcal{T}_{l})\,.$

for some $n\geq 1$. Then, from Remark 5.3, any eigenfunction of
$\mathcal{H}_{p}$ with eigenvalue $\lambda$ corresponds to an eigenfunction of
$\mathcal{H}_{p}^{\prime}$. In particular, given any subtree $\mathcal{T}_{l}$
and corresponding operator $\mathcal{H}_{p}(\mathcal{T}_{l})$ it is easy to
observe that

$g_{u}^{\mathcal{T}_{l}}(\lambda)=g_{u}(\lambda)\qquad u\in\mathcal{T}_{l}\,,$

where $g_{u}^{\mathcal{T}_{l}}$ are the generating functions defined starting
from $\mathcal{H}_{p}(\mathcal{T}_{l})$ via equations (19),(20),(21) (see the
proof of Theorem 6.5 for a similar construction). Among the
$\\{\mathcal{T}_{l}\\}_{l=1}^{n}$, let
$\\{\mathcal{T}_{i}^{\prime}\\}_{i=1}^{k}$ be the subtrees with root
$r_{i}=v_{i}$. Due to Proposition 6.7, for any such $\mathcal{T}_{i}^{\prime}$
and corresponding $\mathcal{H}_{p}(\mathcal{T}_{i}^{\prime})$ there exists a
unique everywhere nonzero eigenfunction $f_{i}^{\prime}$ of
$\mathcal{H}_{p}(\mathcal{T}_{i}^{\prime})$ with eigenvalue $\lambda$ whose
ratios $f_{i}^{\prime}(w_{F})/f_{i}^{\prime}(w)$ are induced by the functions
$g_{w}(\lambda)$, $\forall w\in\mathcal{T}_{i}^{\prime}$. Moreover, notice
that for any $f$ eigenfunction of $\mathcal{H}_{p}$ with eigenvalue $\lambda$,
since $f$ is also an eigenfunction of $\mathcal{H}_{p}^{\prime}$, we have
$f|_{\mathcal{T}_{i}^{\prime}}=\alpha_{i}f_{i}^{\prime}$, for some
$\alpha_{i}\in\mathbb{R}$.

On the other hand, on the subtrees
$\\{\mathcal{T}_{j}^{\prime\prime}\\}_{j=1}^{n-k}$ whose root $r_{j}$ is such
that $r_{j}\neq v_{i}$ $\forall i=1,\dots,k$, since $g_{w}(\lambda)\neq 0$,
$\forall w\in\mathcal{T}_{j}^{\prime\prime}$, any eigenfunction associated to
$\lambda$ of $\mathcal{H}_{p}$ has to be such that
$f|_{\mathcal{T}_{j}^{\prime\prime}}(w)=0$ because of Theorem 6.5. Indeed,
suppose by contradiction that $f$ is an eigenfunction associated to $\lambda$
such that $f|_{\mathcal{T}_{j}^{\prime\prime}}\neq 0$, then $f$ should be an
eigenfunction of $\mathcal{H}_{p}(\mathcal{T}_{j}^{\prime\prime})$ with same
eigenvalue $\lambda$. However, $g_{w}(\lambda)\neq 0$, $\forall
w\in\mathcal{T}_{j}^{\prime\prime}$ implies that
$f|_{\mathcal{T}_{j}^{\prime\prime}}(w)\neq 0$, $\forall
w\in\mathcal{T}_{j}^{\prime\prime}$ and thus, by Remark 6.1, we would have
that $g_{r_{j}}(\lambda)=0$, which is absurd.

Now, let $f_{i}$ be the immersion of $f_{i}^{\prime}$ into $\mathbb{R}^{N}$
such that $f_{i}|_{\mathcal{T}_{i}^{\prime}}=f_{i}^{\prime}$ and $f_{i}(w)=0$
for all $w\notin\mathcal{T}_{i}^{\prime}$. Define
$\Omega:=\mathrm{span}\\{f_{i}\\}_{i=1}^{k}$ the $k$-dimensional linear space
spanned by the $f_{i}$. The observations above together with Corollary 6.6
imply that if $f$ is an eigenfunction of $\mathcal{H}_{p}$ with eigenvalue
$\lambda$, then $f\in\Omega$. Starting from $\Omega$, we want to recover all
the possible eigenfunctions of $\mathcal{H}_{p}$ relative to $\lambda$. To
this end, we select among the functions $f\in\Omega$ all those functions that
satisfy the eigenvalue equation for $\mathcal{H}_{p}$ also in the removed
points $\\{u_{j}\\}_{j=1}^{h}$. For any node $u_{j}$, let $w_{i,j}$ be the
node in the neighborhood of $u_{j}$ such that
$w_{i,j}\in\mathcal{T}_{i}^{\prime}$. Then, the $\mathcal{H}_{p}$ eigenvalue
equation on a node $u_{j}$ reads

(30) $\displaystyle\Theta_{j}(f)$
$\displaystyle:=\sum_{i}\omega_{w_{i,j}u_{j}}\phi_{p}(\beta_{w_{i,j}})\phi_{p}(f_{i}(r_{i}))$
$\displaystyle=\sum_{i}\omega_{w_{i,j}u_{j}}\phi_{p}(f_{i}(w_{i,j}))=\Big{(}\lambda\varrho_{u_{j}}-\kappa_{u_{j}}\Big{)}\phi_{p}(f(u_{j})=0$
$\displaystyle\quad\forall j=1,\dots,h$

where we have used the fact that on any $\mathcal{T}_{i}^{\prime}$ the ratios
between the components of $f_{i}$ are fixed by the functions $g_{w}(\lambda)$,
$w\in\mathcal{T}_{i}^{\prime}$ and thus, for every
$w\in\mathcal{T}_{i}^{\prime}$ there exists $\beta_{w}\neq 0$ such that
$f_{i}(w)=\beta_{w}f_{i}(r_{i})$.

We continue by defining the set
$A=\\{f\,|\,\Theta_{j}(f)=0,\,\,\forall\,j=1,\dots,h\\}$. It is clear that $f$
is an eigenfunction of $\mathcal{H}_{p}$ relative to $\lambda$ if and only if
$f\in A\cap\Omega$. Thus, let us now study the genus of such a set. Observe
that $\gamma(A\setminus\\{0\\})=N-h$, since $A$ is diffeomorphic to a linear
subspace of dimension $N-h$ through the homeomorphism of $\mathbb{R}^{N}$
given by $x_{i}\mapsto\phi_{p}(x_{i})$, $i=1,\dots,N$ (the set of equations
$\\{\Theta_{j}(f)=0\\}$ is transformed into a set of $h$ linearly independent
equation by the change of variable $y_{i}:=\phi_{p}(f_{i}(r_{i}))$). Thus, if
$k>h$ then the intersection is always nonempty because of Lemma 5.1 and in
particular

$\gamma(A\cap\Omega\setminus\\{0\\})\geq\gamma(A\setminus\\{0\\})-(N-k)=N-h-N+k=k-h\,.$

Now we claim that it is possible to define a function $\widetilde{\psi}$ in
the set of Krasnoselskii test maps
$\Lambda_{k-h}(\Omega\,\cap\,A\setminus\\{0\\})$ such that
$0\not\in\widetilde{\psi}(\Omega\,\cap\,A\setminus\\{0\\})$. This implies
$\gamma(\Omega\,\cap\,A\setminus\\{0\\})\leq k-h$, from which the statement
follows. To construct such $\widetilde{\psi}$, consider the function
$\psi\in\Lambda_{k}(\Omega)$ given by:

(31) $\displaystyle
f=\sum_{i=1}^{k}\alpha_{i}f_{i}\mapsto\psi(f):=\Big{(}f(r_{1})\,,\dots,f(r_{k})\Big{)}=\Big{(}\alpha_{1}f_{1}(r_{1}),\dots,\alpha_{k}f_{k}(r_{k})\Big{)}\,.$

It is easy to verify that $0\not\in\psi(\Omega\setminus\\{0\\})$, as
$f_{i}(r_{i})\neq 0$, $\forall i$. Since we want to define the function
$\widetilde{\psi}$ on $A\cap\Omega$, we define $\widetilde{\psi}$ as the
restriction to $\mathbb{R}^{k-h}$ of $\psi$. To define such a restriction,
note that among the $\\{\mathcal{T}_{i}^{\prime}\\}$ it is possible to select
$h$ distinct subtrees $\\{\mathcal{T}_{i_{l}}^{\prime}\\}_{l=1}^{h}$ such that
any node $u_{j}$ is incident to some $\mathcal{T}_{i_{l}}^{\prime}$. As
before, let $w_{i_{l},j}$ be the neighbor of $u_{j}$ in
$\mathcal{T}_{i_{l}}^{\prime}$. Then consider the function
$\widetilde{\psi}:\Omega\,\cap\,A\to\mathbb{R}^{k-h}$, entrywise defined as

$\Big{(}\widetilde{\psi}(f)\Big{)}_{i}=\Big{(}\psi(f)\Big{)}_{i}\qquad i\neq
i_{l},\;\;l=1,\dots,h\,.$

It is easily proved that $\widetilde{\psi}\in\Lambda_{k-h}(\Omega\,\cap\,A)$.
Finally, we show that if $\widetilde{\psi}(f)=0$, for some
$f\in\Omega\cap\,A$, then necessarily $f=0$. To this end, write
$f=\sum_{i=1}^{k}\alpha_{i}f_{i}$. If $\widetilde{\psi}(f)=0$, then (up to a
reordering of the indices of the chosen subtrees)

$\alpha_{i}f_{i}(r_{i})=0\qquad\forall i\neq i_{l},\,l=1\dots,h\,.$

Thus, $f=\sum_{l=1}^{h}\alpha_{i_{l}}f_{i_{l}}$. Then, observe that, since
$f\in A$, we have

(32)
$\Theta_{j}(f)=\sum_{l}\omega_{w_{i_{l},j}u_{j}}\phi_{p}(\alpha_{i_{l}})\phi_{p}(\beta_{w_{i_{l},j}})\phi_{p}(f_{i_{l}}(r_{i_{l}}))=0\quad\forall
j=1,\dots,h\,.$

Consider a node $u_{j_{0}}$ that is incident only to one of the subtrees
$\\{\mathcal{T}_{i_{l}}^{\prime}\\}_{l=1}^{h}$, say
$\mathcal{T}_{i_{h}}^{\prime}$, observe that such a node necessarily exists
because there are no loops in a forest. Then (32) for $j=j_{0}$ reads (up to a
reordering of the indices)

(33)
$\Theta_{j_{0}}(f)=\omega_{u_{j_{0}}w_{i_{h},j_{0}}}\phi_{p}(\alpha_{i_{h}})\phi_{p}(\beta_{w_{i_{h}}})\phi_{p}(f_{i_{h}}(r_{i_{h}}))=0\,.$

This means that $\alpha_{i_{h}}=0$, i.e.
$f=\sum_{l=1}^{h-1}\alpha_{i_{l}}f_{i_{l}}$. Repeating this procedure for all
the $h$ nodes $u_{j}$, we obtain that all the $\alpha_{i}$ have to be zero. In
particular, this implies that, if $k=h$, then all the $\alpha_{i}$ are zero
and thus $A\cap\Omega=\\{0\\}$ i.e. $\lambda$ is not an eigenvalue, thus
concluding the proof. ∎

To conclude this preparatory section needed to tackle the proofs of Theorems
3.7 and 3.8, we show in the next result how the eigenvalues and the
corresponding $\gamma$-multiplicities change when moving from
$\mathcal{H}_{p}^{u}$ to $\mathcal{H}_{p}^{\widetilde{u}}$ (recall that
$\mathcal{H}_{p}^{u}$ is the operator obtained by removing all the nodes
different from $u$ and its descendants while $\mathcal{H}_{p}^{\widetilde{u}}$
is the one obtained by removing also the node $u$). We state this result as a
corollary of the previous lemma, recalling that $\lambda$ is not an eigenvalue
if and only if $\gamma\text{-}\mathrm{mult}(\lambda)=0$.

######  Corollary 6.9.

  1. (1)

Let $\lambda$ be such that $g_{u}(\lambda)=0$, then $\lambda$ is an eigenvalue
of $\mathcal{H}_{p}^{u}$ and
$\gamma\text{-}\mathrm{mult}_{\mathcal{H}_{p}^{u}}(\lambda)=\gamma\text{-}\mathrm{mult}_{\mathcal{H}_{p}^{\widetilde{u}}}(\lambda)+1$.

  2. (2)

Let $\lambda$ be an eigenvalue of $\mathcal{H}_{p}^{\widetilde{u}}$ such that
$g_{w}(\lambda)\neq 0$ for all $w\prec u$ and $g_{u}(\lambda)\neq 0$, then
$\lambda$ is an eigenvalue of $\mathcal{H}_{p}^{u}$ such that
$\gamma\text{-}\mathrm{mult}_{\mathcal{H}_{p}^{u}}(\lambda)=\gamma\text{-}\mathrm{mult}_{\mathcal{H}_{p}^{\widetilde{u}}}(\lambda)$.

  3. (3)

Let $\lambda$ be an eigenvalue of $\mathcal{H}_{p}^{\widetilde{u}}$ and assume
there exist $w_{1},\dots,w_{h}\prec u$ with $g_{w_{i}}(\lambda)=0$, then
$\gamma\text{-}\mathrm{mult}_{\mathcal{H}_{p}^{u}}(\lambda)=\gamma\text{-}\mathrm{mult}_{\mathcal{H}_{p}^{\widetilde{u}}}(\lambda)-1$.

###### Proof.

From Lemma 6.8 we know that $\lambda$ is an eigenvalue if and only if $k-h>0$,
where $k$ is the number of nodes $v$ such that $g_{v}(\lambda)=0$ and $h$ is
the number of their parents. In particular, we have that
$\gamma\text{-}\mathrm{mult}_{\mathcal{H}_{p}}(\lambda)=k-h$. To prove point
1, we observe that, since $u$ is the root of the subtree $\mathcal{T}_{u}$,
$u$ has no parents and thus necessarily $h<k$. Moreover, by Lemma 6.4,
$g_{v}(\lambda)\neq 0$, for all $v\prec u$ implying that $h$ does not change
when moving from $\mathcal{T}_{\widetilde{u}}$ to $\mathcal{T}_{u}$, while $k$
increases by one. This implies the statement. To prove point 2, it is enough
to observe that the number $k-h$ does not change going from
$\mathcal{T}_{\widetilde{u}}$ to $\mathcal{T}_{u}$. Finally, in order to prove
point 3 observe that in this case, when moving from
$\mathcal{T}_{\widetilde{u}}$ to $\mathcal{T}_{u}$, $k$ does not change while
$h$ increases by one. ∎

###  6.4. Proofs of Theorems 3.7 and 3.8

We are finally ready to prove the main Theorems 3.7 and 3.8.

###### Proof of Theorem 3.7.

We first observe that if the thesis holds for trees, then it holds as well for
forests. To prove this fact, we assume that all the eigenvalues on trees are
variational and the multiplicity matches the $\gamma$-multiplicity. Then, we
note that if $\mathcal{G}=\sqcup_{i}\mathcal{T}_{i}$, with
$\mathcal{T}_{i}=(V_{i},E_{i})$ trees, then
$\mathcal{H}_{p}=\oplus_{i}{\mathcal{H}_{p}}(\mathcal{T}_{i})$, where
${\mathcal{H}_{p}}(\mathcal{T}_{i})$ is a suitable generalized $p$-Laplacian
operator defined on $\mathcal{T}_{i}$, and hence
$\sigma(\mathcal{H}_{p})=\cup_{i}\sigma({\mathcal{H}_{p}}(\mathcal{T}_{i}))$.
In other words, the spectrum of $\mathcal{H}_{p}$ is the union of the spectra
of the operators defined on the trees forming $\mathcal{G}$. Next, we observe
that, by the same assumption on trees,
$\sigma(\mathcal{H}_{p}(\mathcal{T}_{i}))$ is formed only by variational
eigenvalues and thus it contains at most $|V_{i}|$ distinct elements, implying
that $\sigma(\mathcal{H}_{p})$ is formed by at most $N$ different eigenvalues.
Now, let $\lambda\in\sigma(\mathcal{H}_{p})$. By the previous assumption,
$\lambda$ is a variational eigenvalue of $\mathcal{H}_{p}(\mathcal{T}_{i})$,
for some $i\in\\{1,\dots,k\\}$ and
$\mathrm{mult}_{\mathcal{H}_{p}(\mathcal{T}_{i})}(\lambda)=\gamma\text{-}\mathrm{mult}_{\mathcal{H}_{p}(\mathcal{T}_{i})}(\lambda)=m_{i}(\lambda)$.
Then, for any $i\in\\{1,\dots,k\\}$ there exists
$\varphi_{i}\in\Lambda_{m_{i}(\lambda)}(A_{\lambda}^{i})$ s.t.
$0\not\in\varphi_{i}(A_{\lambda}^{i}\cap\mathcal{S}_{p})$, where

$A_{\lambda}^{i}=\\{f:V_{i}\rightarrow\mathbb{R}\,|\,\mathcal{H}_{p}(\mathcal{T}_{i})(f)=\lambda|f|^{p-2}f\\}\,.$

Let

$A_{\lambda}=\\{f:V\rightarrow\mathbb{R}\,|\mathcal{H}_{p}(f)=\lambda|f|^{p-2}f\\}\,.$

Then, we can consider the extensions of the functions $\varphi_{i}$ to
$A_{\lambda}$ and, given $m(\lambda)=\sum_{i}m_{i}(\lambda)$, define the
function $\varphi_{\lambda}\in\Lambda_{m(\lambda)}(A_{\lambda})$ as a linear
combination of $\varphi_{i}$ such that
$0\notin\varphi_{\lambda}(A_{\lambda}\cap\mathcal{S}_{p})$. This implies that
$\gamma\text{-}\mathrm{mult}_{\mathcal{H}_{p}}(\lambda)\leq m(\lambda)$.
Noting that $N=\sum_{\lambda}\sum_{i}m_{i}(\lambda)$, we have
$\sum_{\lambda}\gamma\text{-}\mathrm{mult}_{\mathcal{H}_{p}}(\lambda)\leq N$.
Thus, by Corollary 3.6 we conclude that all the eigenvalues of
$\mathcal{H}_{p}$ are variational and
$\mathrm{mult}_{\mathcal{H}_{p}}(\lambda)=\gamma\text{-}\mathrm{mult}_{\mathcal{H}_{p}}(\lambda)=\sum_{i=1}^{k}\mathrm{mult}_{\mathcal{H}_{p}(\mathcal{T}_{i})}(\lambda)$.

Now, we address the proof of the assumption and consider the case in which
$\mathcal{G}=\mathcal{T}$ is a tree. The proof proceeds by induction on the
number of nodes $N$. If $N=1$, from (19) and Proposition 6.7, we can conclude
that there exists only one eigenvalue, $\lambda_{1}$, with
$\gamma\text{-}\mathrm{mult}_{\mathcal{H}_{p}}(\lambda_{1})=\mathrm{mult}_{\mathcal{H}_{p}}(\lambda_{1})=1$.
Assume now that $N>1$ and that the theorem holds up to $N-1$. First note that
the inductive assumption and the result derived in the previous paragraph
imply that the thesis holds for any forest composed by trees, each one, with
less then $N$ nodes. Then, fix a root $r$ for $\mathcal{T}$ and consider
$\mathcal{T}_{\widetilde{r}}=\sqcup_{i=1}^{n}\mathcal{T}_{i}$ and
$\mathcal{H}_{p}^{\widetilde{r}}=\oplus_{i}\mathcal{H}_{p}(\mathcal{T}_{i})$.
Proceed by dividing the eigenvalues of $\mathcal{H}_{p}^{\widetilde{r}}$ into
two sets $\\{\nu_{j}\\}_{j=1}^{k}$ and $\\{\xi_{l}\\}_{l=1}^{h}$, where each
$\nu_{j}$ is a zero of some $g_{v}$ for some $v\prec r$, whereas $\xi_{l}$ is
not. By the inductive assumption, we have that

$\sum_{j=1}^{k}\gamma\text{-}\mathrm{mult}_{\mathcal{H}_{p}^{\widetilde{r}}}(\nu_{j})+\sum_{l=1}^{h}\gamma\text{-}\mathrm{mult}_{\mathcal{H}_{p}^{\widetilde{r}}}(\xi_{l})=N-1\,.$

Now, let us divide the eigenvalues of $\mathcal{H}_{p}$ in a similar way. Let
$\\{\mu_{i}\\}_{i=1}^{k+1}$ the eigenvalues that are zeros of $g_{r}$. By
Lemma 6.4 we know that they are exactly $k+1$. Lemma 6.8 ensures that all the
other eigenvalues of $\mathcal{H}_{p}$ are also eigenvalues of
$\mathcal{H}_{p}^{\widetilde{r}}$ and, in particular, they must be either in
the set $\\{\nu_{j}\\}_{j=1}^{k}$ or in the set $\\{\xi\\}_{l=1}^{h}$.
Moreover, from Lemma6.4 we deduce that
$\\{\nu_{j}\\}_{j=1}^{k}\cap\\{\mu_{i}\\}_{i=1}^{k+1}=\emptyset$ while
$\\{\xi_{l}\\}_{l=1}^{h}\cap\\{\mu_{i}\\}_{i=1}^{k+1}$ could be non empty. In
particular, let us set

$\\{\xi\\}_{l=1}^{h_{1}}=\\{\xi_{l}\\}_{l=1}^{h}\setminus\\{\xi_{l}\\}_{l=1}^{h}\cap\\{\mu_{i}\\}_{i=1}^{k+1}\,.$

Then,

(34)
$\displaystyle\sum_{i=1}^{k+1}\gamma\text{-}\mathrm{mult}_{\mathcal{H}_{p}}(\mu_{i})+\sum_{j=1}^{k}\gamma\text{-}\mathrm{mult}_{\mathcal{H}_{p}}(\nu_{j})+\sum_{l=1}^{h_{1}}\gamma\text{-}\mathrm{mult}_{\mathcal{H}_{p}}(\xi_{l})$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{k+1}\Big{(}\gamma\text{-}\mathrm{mult}_{\mathcal{H}_{p}^{\widetilde{r}}}(\mu_{i})+1\Big{)}+\sum_{j=1}^{k}\Big{(}\gamma\text{-}\mathrm{mult}_{\mathcal{H}_{p}^{\widetilde{r}}}(\nu_{j})-1\Big{)}+\sum_{l=1}^{h_{1}}\gamma\text{-}\mathrm{mult}_{\mathcal{H}_{p}^{\widetilde{r}}}(\xi_{l})$
$\displaystyle=$ $\displaystyle
k+1-k+\sum_{j=1}^{k}\gamma\text{-}\mathrm{mult}_{\mathcal{H}_{p}^{\widetilde{r}}}(\nu_{j})+\sum_{l=1}^{h}\gamma\text{-}\mathrm{mult}_{\mathcal{H}_{p}^{\widetilde{r}}}(\xi_{l})=N-1+1=N$

where we have used Corollary 6.9 and the fact that
$\\{\xi_{l}\\}_{l=1}^{h}\subseteq(\\{\xi_{l}\\}_{l=1}^{h_{1}}\cup\\{\mu_{i}\\}_{i=1}^{k+1})$,
with
$\gamma\text{-}\mathrm{mult}_{\mathcal{H}_{p}^{\widetilde{r}}}(\mu_{i})=0$ if
$\mu_{i}\not\in\\{\xi_{l}\\}_{l=1}^{h}$. Together with Corollary3.6, the
latter equality concludes the proof. ∎

Before moving on to the proof of Theorem 3.8, several observations are in
order.

######  Remark 6.10.

Suppose $\mathcal{G}=\sqcup_{i=1}^{m}\mathcal{T}_{i}$ is a forest and let
$\mathcal{H}_{p}=\mathop{\oplus}_{i=1}^{m}\mathcal{H}_{p}(\mathcal{T}_{i})$ as
before. If we consider an eigenfunction $f_{k}$ of $\mathcal{H}_{p}$ that is
everywhere nonzero Theorem 3.7 ensures that the corresponding eigenvalue
$\lambda_{k}$ has multiplicity exactly equal to $m$. Indeed, necessarily
$f_{k}|_{\mathcal{T}_{i}}$ is an eigenfunction of
$\mathcal{H}_{p}(\mathcal{T}_{i})$ and, since it is everywhere non-zero, its
corresponding eigenvalue is simple because of Proposition 6.7.

In addition, observe that $e_{0}=(u_{0},v_{0})$ is an edge of some
$\mathcal{T}_{i}$ such that $f_{k}(u_{0})f_{k}(v_{0})<0$ if and only if
$e_{0}$ separates two distinct nodal domains. This means that the number of
nodal domains induced by $f_{k}$ on $\mathcal{T}_{i}$ is equal to the number
of edges where $f_{k}|_{\mathcal{T}_{i}}$ changes sign, plus one. Thus the
total number of nodal domains induced by $f_{k}$ on $\mathcal{G}$ is equal to
$m$ plus the total number of edges where $f_{k}$ changes sign. Combining all
these observations, we eventually obtain the following proof.

###### Proof of Theorem 3.8.

We prove by induction on $k$ that, if $f_{k}$ is an eigenfunction everywhere
nonzero associated to the multiple eigenvalue
$\lambda_{k}=\dots=\lambda_{k+m-1}$, then $f_{k}$ changes sign on exactly
$k-1$ edges, implying that $f_{k}$ induces exactly $k-1+m$ nodal domains. If
$k=1$, $f_{1}|_{\mathcal{T}_{i}}$ is an eigenfunction related to the first
eigenvalue of each operator $\mathcal{H}_{p}(\mathcal{T}_{i})$, $i=1,\dots,m$.
Thus, as a consequence of Theorem 4.1, $f_{1}$ is strictly positive or
strictly negative on every tree $\mathcal{T}_{i}$ and overall it induces $m$
nodal domains. Moreover, it does not change sign on any edge. Now we assume
the statement to be true for every $h<k$ and prove it for $h=k$. If $k>1$,
then $f_{k}$ cannot be a first eigenfunction on every tree $\mathcal{T}_{i}$.
Then, by Theorem 4.1, there exists at least one edge $e_{0}=(u_{0},v_{0})$ in
some $\mathcal{T}_{i_{0}}$ such that $f_{k}(u_{0})f_{k}(v_{0})<0$. Thus, we
operate as in Section 5.1 and remove edge $e_{0}$ to disconnect
$\mathcal{T}_{i_{0}}$ into the two subtrees $\mathcal{T}_{i_{0}}^{\prime}$ and
$\mathcal{T}_{i_{0}}^{\prime\prime}$, so that the reduced graph
$\mathcal{G}^{\prime}$ is the union of the $m+1$ subtrees:

$\mathcal{G}^{\prime}=\Big{(}\mathop{\sqcup}_{\begin{subarray}{c}i=1\\\ i\neq
i_{0}\end{subarray}}^{m}\mathcal{T}_{i}\Big{)}\sqcup\mathcal{T}_{i_{0}}^{\prime}\sqcup\mathcal{T}_{i_{0}}^{\prime\prime}\,.$

Similarly, the new operator $\mathcal{H}_{p}^{\prime}$, obtained after
removing $e_{0}$, can be decomposed as:

$\mathcal{H}^{\prime}_{p}=\Big{(}\mathop{\oplus}_{\begin{subarray}{c}i=1\\\
i\neq
i_{0}\end{subarray}}^{m}\mathcal{H}_{p}(\mathcal{T}_{i})\Big{)}\oplus\mathcal{H}^{\prime}_{p}(\mathcal{T}_{i_{0}}^{\prime})\oplus\mathcal{H}^{\prime}_{p}(\mathcal{T}_{i_{0}}^{\prime\prime})\,.$

Now we can compare the eigenvalues $\\{\eta_{k}\\}$ of
$\mathcal{H}_{p}^{\prime}$ with the ones $\\{\lambda_{k}\\}$ of
$\mathcal{H}_{p}$. From Lemma 5.2 we have:

$\eta_{k-1}\leq\lambda_{k}\leq\eta_{k}\leq\dots\leq\lambda_{k+m-1}\leq\eta_{k+m-1}\leq\lambda_{k+m}\,.$

Due to Remark 6.10 and Theorem 3.7, the multiplicity of $\eta_{k}$ has to be
exactly $m+1$ and, by assumption,
$\lambda_{k-1}<\lambda_{k}=\dots=\lambda_{k+m-1}<\lambda_{k+m}$, i.e.
$\eta_{k-1}=\dots=\eta_{k+m-1}$. Moreover, by the inductive assumption,
$f_{k}$ changes sign on $k-1$ edges of the graph $\mathcal{G}^{\prime}$. Thus,
on the original graph $\mathcal{G}$, $f_{k}$ changes sign $k-1+1=k$ times,
concluding the proof. ∎

##  7\. Nodal domain count on generic graphs (proofs of Theorems 3.9 and 3.10)

In this final section we prove Theorems 3.9 and 3.10, providing upper and
lower bounds for the number of nodal domains of $f$ and for the number of
edges where $f$ changes sign. To this end, we need first a few preliminary
results.

Consider an eigenpair $(f,\lambda)$ of the generalized $p$-Laplacian operator
$\mathcal{H}_{p}$ on a generic graph $\mathcal{G}$. Suppose we remove from
$\mathcal{G}$ an edge $e_{0}=(u_{0},v_{0})$, obtaining the graph
$\mathcal{G}^{\prime}=\mathcal{G}\setminus\\{e_{0}\\}$. Modifying accordingly
the generalized $p$-Laplacian $\mathcal{H}_{p}$ as in Section 5.1, the new
operator $\mathcal{H}_{p}^{\prime}$ on $\mathcal{G}^{\prime}$ is such that the
pair $(f,\lambda)$, restricted to $\mathcal{G}^{\prime}$, remains an eigenpair
of $\mathcal{H}_{p}^{\prime}$.

Let us denote by $\Delta l(e_{0},f)$ the variation of the number of
independent loops of constant sign, namely the difference between the number
of loops of constant sign of $f$ in $\mathcal{G}^{\prime}$ minus the number of
those in $\mathcal{G}$. Similarly, let $\Delta\nu(e_{0},f)$ be the variation
between the number of nodal domains induced by $f$ on $\mathcal{G}^{\prime}$
and on $\mathcal{G}$. We can characterize the difference
$\Delta\nu(e_{0},f)-\Delta l(e_{0},f)$ in terms of
$\mathrm{sign}_{e_{0}}(f)=f(u_{0})f(v_{0})$, i.e. whether or not $f$ changes
sign over $e_{0}$. In fact, note that, by definition, if
$\mathrm{sign}_{e_{0}}(f)<0$, then neither the number of loops of constant
sign nor the number of nodal domains changes. If, instead,
$\mathrm{sign}_{e_{0}}(f)>0$, then either the number of independent loops
decreases by one ($\Delta(e_{0},f)=-1$) or the number of nodal domains
increases by one ($\Delta(e_{0},f)=+1$). Overall, we have

(35) $\Delta\nu(e_{0},f)-\Delta
l(e_{0},f)=\begin{cases}0\quad\mathrm{sign}_{e_{0}}(f)<0\\\
1\quad\mathrm{sign}_{e_{0}}(f)>0\end{cases}\,.$

Based on the above formula, the following lemma provides a relation between
the number of nodal domains induced by an eigenfunction and the number of
edges where the sign changes. It is a generalization of a result from [4],
which was proved for linear Laplacians and for the case of everywhere nonzero
functions.

######  Lemma 7.1.

Consider $f:V\rightarrow\mathbb{R}$, a function on the graph $\mathcal{G}$.
Denote by $\zeta(f)$ the number of edges where $f$ changes sign, by $z(f)$ he
number of nodes where $f$ is zero, by $l(f)$ the number of independent loops
in $\mathcal{G}$ where $f$ has constant sign, and by $|E_{z}|$ the number of
edges incident to the zero nodes. Then

$\zeta(f)=|E|-|E_{z}|+z(f)-|V|+{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\nu(f)-l(f)}\leq|E|-|V|+{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\nu(f)-l(f)}\,.$

###### Proof.

Operating as in Section 5.2, we start by removing from $\mathcal{G}$ all the
$z(f)$ nodes where $f$ is zero, thus obtaining a new graph
$\mathcal{G}^{\prime}$ with the corresponding new generalized $p$-Laplacian
$\mathcal{H}_{p}^{\prime}$. Since $|E_{z}|$ is the number of edges incident to
the zero nodes that have been removed, the number of edges in
$\mathcal{G}^{\prime}$ can be estimated as
$|E^{\prime}|=|E|-|E_{z}|\leq|E|-z(f)$. Moreover, the edges incident to the
zero nodes neither connect different nodal domains nor belong to constant sign
loops. Hence, the restriction of $f$ to $\mathcal{G}^{\prime}$ remains an
eigenfunction of $\mathcal{H}_{p}^{\prime}$ having the same number of nodal
domains and the same number of constant sign loops as $f$.

Next, we proceed by removing from $\mathcal{G}^{\prime}$ all the edges
$e_{1},\dots,e_{\tau(f)}$ where $f$ does not change sign (i.e., such that
$\mathrm{sign}_{e_{i}}(f)>0$) and modify consequently the operator
$\mathcal{H}^{\prime}_{p}$ as in Section 5.1. We obtain a new graph
$\mathcal{G}^{\prime\prime}$ and the corresponding new operator
$\mathcal{H}^{\prime\prime}_{p}$ in such a way that $(\lambda,f)$ remains an
eigenpair. Since the number of edges where $f$ does not change sign is
$\tau(f)=|E^{\prime}|-\zeta(f)$, thanks to (35), we have that

(36) $\sum_{i=1}^{h}\Big{(}\Delta\nu(e_{i},f)-\Delta
l(e_{i},f)\Big{)}=|E^{\prime}|-\zeta(f)\leq|E|-z(f)-\zeta(f)\,.$

In the final graph $\mathcal{G}^{\prime\prime}$, only edges connecting nodes
of different sign are present, so that each node is a nodal domain of $f$. As
a consequence, there are a total $|V|-z$ nodal domains of $f$ and no loops
with constant sign. Then:

$\sum_{i=1}^{h}\Delta\nu(e_{i},f)=|V|-z(f)-\nu(f)\qquad\text{and}\qquad\sum_{i=1}^{h}\Delta
l(e_{i},f)=-l(f)\,,$

and, by (35),
$\tau(f)=\sum_{i=1}^{h}\Delta\nu(e_{i},f)-\Delta\leavevmode\nobreak\
l(e_{i},f)=|V|-z(f)-\nu(f)+l(f)$. Hence, using (36) and the fact that
$\tau(f)=|E|-|E_{z}|-\zeta(f)$, we obtain

$\zeta(f)=|E|-|E_{z}|+z(f)-|V|+\nu(f)-l(f)\leq|E|-|V|+\nu(f)-l(f)$

thus concluding the proof. ∎

The above lemma allows us to prove our third and fourth main results given in
Theorems 3.9 and 3.10, which provide new upper and lower bounds for the number
of nodal domains of the eigenfunctions of the generalized $p$-Laplacian,
extending and generalizing previous results for the standard $p$-Laplacian and
the linear Schrödinger operators [40, 5, 41]. As the proof of the two claims
in Theorem 3.10 requires different arguments, we subdivide it into two parts,
each addressing one of the two points P1 and P2 in the statement.

###### Proof of Theorem 3.9.

For a connected graph $\mathcal{G}$, let $f$ be an eigenfunction of
$\mathcal{H}_{p}$ relative to $\lambda$. Let $\nu(f)$ denote the number of
nodal domains of $f$ and let $\mathcal{G}_{1},\dots,\mathcal{G}_{\nu(f)}$ be
such domains. Furthermore, let $e_{1},\dots,e_{\zeta}$ be the edges where $f$
changes sign and $v_{1},\dots,v_{z}$ the nodes where $f$ is zero, with
$z=z(f)$ the number of such nodes. The proof proceeds as follows.

According to Section 5.2, we start by removing the nodes $v_{1},\dots,v_{z}$
from $\mathcal{G}$ obtaining a new graph $\mathcal{G}^{\prime}$. Operator
$\mathcal{H}_{p}$ is then modified to form the operator
$\mathcal{H}^{\prime}_{p}$ in such a way that the restriction of $f$ to
$\mathcal{G}^{\prime}$ is an eigenfunction of $\mathcal{H}^{\prime}_{p}$ with
the same eigenvalue $\lambda$. Moreover, as all the zero nodes that are not
part of any nodal domain are now removed, we observe that $f$ restricted to
$\mathcal{G}^{\prime}$ has no zeros and induces the same nodal domains that
$f$ induces on $\mathcal{G}$. From Lemma 5.4, we conclude that
$\lambda<\lambda_{k}\leq\lambda_{k}^{\prime}$, where $\lambda^{\prime}_{k}$
denotes the $k$-th variational eigenvalue of $\mathcal{H}^{\prime}_{p}$.

Then, operating as in Section 5.1, we remove from $\mathcal{G}^{\prime}$ all
the edges $e_{1},\dots,e_{\zeta}$ obtaining a new graph
$\mathcal{G}^{\prime\prime}$ and the new operator
$\mathcal{H}_{p}^{\prime\prime}$ such that $f$ restricted to
$\mathcal{G}^{\prime\prime}$ is an eigenfunction of
$\mathcal{H}_{p}^{\prime\prime}$ with the same eigenvalue $\lambda$. Notice
that, since we removed only nodes where $f$ is zero and edges where $f$
changes sign, then $\mathcal{G}^{\prime\prime}$ can be written as the disjoint
union of the nodal domains, namely
$\mathcal{G}^{\prime\prime}=\sqcup_{i=1}^{\nu(f)}\mathcal{G}_{i}$ and, as a
consequence, we have

$\mathcal{H}_{p}^{\prime\prime}=\mathop{\oplus}_{i=1}^{\nu(f)}\mathcal{H}^{\prime\prime}_{p}(\mathcal{G}_{i})$

where $\mathcal{H}^{\prime\prime}_{p}(\mathcal{G}_{i})$ is the restriction of
the generalized $p$-Laplacian operator onto $\mathcal{G}_{i}$. Hence, from
Lemma 5.2 we have

(37) $\lambda<\lambda_{k}^{\prime}\leq\lambda_{k}^{\prime\prime}\,.$

where $\lambda_{k}^{\prime\prime}$ denotes the $k$-th variational eigenvalue
of $\mathcal{H}_{p}^{\prime\prime}$. Note that the restriction
$f|_{\mathcal{G}_{i}}$ to each of the nodal domains $\mathcal{G}_{i}$ of $f$
has constant sign and it is then necessarily the first eigenpair of
$\mathcal{H}^{\prime\prime}_{p}(\mathcal{G}_{i})$ corresponding to $\lambda$
(see Theorem 4.1) and Corollary 4.2). Hence, $\lambda$ is also the first
eigenvalue of $\mathcal{H}_{p}^{\prime\prime}$ and, as an eigenvalue of
$\mathcal{H}_{p}^{\prime\prime}$ , has multiplicity exactly equal to $\nu(f)$.
We deduce that
$\lambda=\lambda_{1}^{\prime\prime}=\dots=\lambda_{\nu(f)}^{\prime\prime}$
which, combined with (37), implies $k>\nu(f)$, thus concluding the proof. ∎

###### Proof of P1 in Theorem 3.10.

Using the same notation of the proof of Theorem 3.9 above, suppose that
$\lambda>\lambda_{k}$. Then Lemmas 5.2 and 5.4 imply that

$\lambda>\lambda_{k}\geq\lambda^{\prime}_{k-z}\geq\lambda_{k-z-\zeta}^{\prime\prime}$

where we define $\lambda_{h}^{\prime}=\lambda_{h}^{\prime\prime}=-\infty$ for
$h\leq 0$ and $\lambda_{h}^{\prime}=\lambda_{h}^{\prime\prime}=+\infty$ for
$h\geq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}N}-z{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(f)}+1$.
As observed above, $\lambda$ is also the first eigenvalue of
$\mathcal{H}_{p}^{\prime\prime}$. Thus, the above inequality can hold only if
$k-z{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(f)}-\zeta\leq
0$. Using Lemma 7.1 we obtain
$k-z{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(f)}-|E|+|E_{z}|-z{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(f)}+|V|-\nu(f)+l(f)\leq
0$, with $l(f)$ being the number of independent loops in $\mathcal{G}$ where
$f$ has constant sign. This implies

(38) $\nu(f)\geq
k-z(f)-(|E|-|E_{z}|)+(|V|-z(f))+l(f)=k+l(f)-\beta^{\prime}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(f)}-z(f)+c{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(f)}$

where
$c{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(f)}$
is the number of connected components of $\mathcal{G}^{\prime}$ and
$\beta^{\prime}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(f)}:=(|E|-|E_{z}|)-(|V|-z{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(f)})+c{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(f)}$
the number of independent loops in $\mathcal{G}^{\prime}$ . ∎

Next, we provide a proof for P2, Theorem 3.10. The idea is similar to the one
used in the proof of P1. In the latter, we reduced the starting graph to the
disjoint union of the nodal domains of an eigenfunction and doing so we knew
that the corresponding eigenvalue would become the first variational one on
the reduced graph. Now, instead, we reduce the graph to a forest where we know
from Theorem 3.7 that our eigenvalue becomes a variational one and we know by
Theorem 3.8 how to relate the nodal domains induced by the eigenfunction to
the index of the eigenvalue.

###### Proof of P2 in Theorem 3.10.

Let $\mathcal{H}_{p}$ be a generalized $p$-Laplacian operator defined on a
connected graph, $\mathcal{G}$ and assume

$\lambda_{1}\leq\lambda_{2}\leq\dots\leq\lambda_{k-1}<\lambda_{k}=\dots=\lambda_{k+m-1}<\lambda_{k+m}\leq\dots\leq\lambda_{N}\,,$

to be the variational spectrum of $\mathcal{H}_{p}$ and $f$ to be an
eigenfunction relative to
$\lambda=\lambda_{k}=\dots=\lambda_{k+{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}m}-1}$.
Additionally, denote by $\nu(f)$ the number of nodal domains of $f$, by $l(f)$
the number of independent loops where $f$ has constant sign, and by
$v_{1},\dots,v_{z}$ the nodes where $f$ is zero, with $z=z(f)$ the number of
such nodes.

Using the results of Section 5.2, we start by removing the nodes
$v_{1},\dots,v_{z}$ from $\mathcal{G}$ and accordingly modifying the operator
$\mathcal{H}_{p}$, obtaining a graph $\mathcal{G}^{\prime}$ and an operator
$\mathcal{H}^{\prime}_{p}$, such that the restriction of $f$ to
$\mathcal{G}^{\prime}$ is an eigenfunction of $\mathcal{H}^{\prime}_{p}$ with
the same eigenvalue $\lambda$. Observe that, since we have removed all and
only the nodes of $\mathcal{G}$ where $f$ is zero, $f$ restricted to
$\mathcal{G}^{\prime}$ has no zeros and induces the same nodal domains and
constant sign loops induced on $\mathcal{G}$. From Lemma 5.4, we have that

(39)
$\lambda^{\prime}_{k+{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}m}-1-z}\leq\lambda\leq\lambda_{k+{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}m}-1}^{\prime}\,,$

where $\\{\lambda^{\prime}_{k}\\}$ denote the variational eigenvalues of
$\mathcal{H}^{\prime}_{p}$.  In particular $\lambda$ is an eigenvalue of
$\mathcal{H}_{p}^{\prime}$ i.e.
$\lambda\in[\lambda_{1}^{\prime},\lambda_{N-z(f)}^{\prime}]$ ($N-z(f)$ the
number of nodes of $\mathcal{G}^{\prime}$). Thus, since the variational
eigenvalues of $\mathcal{H}_{p}^{\prime}$ split its spectrum in intervals,
there has to exist and index, $h$ with
$\lambda^{\prime}_{h}<\lambda^{\prime}_{h+1}$ such that
$\lambda\in[\lambda^{\prime}_{h},\lambda^{\prime}_{h+1})$ where
$\lambda^{\prime}_{h}=\infty$ if $h>N-z(f)$. Morover from (39) we can state

(40) $h\geq k+m-z(f)-1\,.$

Now observe that if $c(f)$ is the number of connected componets of
$\mathcal{G}^{\prime}$ and $\beta^{\prime}(f)=|E^{\prime}|-|V^{\prime}|+c(f)$
the number of independent loops of $\mathcal{G}^{\prime}$, we can remove
$\beta^{\prime}(f)$ edges from $\mathcal{G}^{\prime}$ to obtain a forest
$\mathcal{T}$ with the same number of connected components of
$\mathcal{G}^{\prime}$.  Every time we remove an edge, we modify the operator
$\mathcal{H}_{p}^{\prime}$ as in Section 5.1 so that the pair $(f,\lambda)$
remains an eigenpair of the resulting operator. At each step, denote by
$e_{0}$ the edge we are removing, and by $\widetilde{\mathcal{G}}^{\prime}$,
$\widetilde{\mathcal{H}}_{p}^{\prime}$ and
$\widetilde{\mathcal{G}}^{\prime\prime}$,
$\widetilde{\mathcal{H}}_{p}^{\prime\prime}$ the graph and the corresponding
generalized $p$-Laplace operator before and after cutting $e_{0}$. Denote by
$\\{\widetilde{\lambda}^{\prime}_{k}\\}$ and
$\\{\widetilde{\lambda}^{\prime\prime}_{k}\\}$ the variational spectra of
$\widetilde{\mathcal{H}}^{\prime}_{p}$ and
$\widetilde{\mathcal{H}}^{\prime\prime}_{p}$. Letting
$\lambda\in[\widetilde{\lambda}^{\prime}_{\ell},\widetilde{\lambda}^{\prime}_{\ell+1})$
(always with the assumption $\widetilde{\lambda}^{\prime}_{\ell}=\infty$ if
$\ell>|V(\widetilde{\mathcal{G}}^{\prime})|$), due to Lemma 5.2, we can bound
$\lambda$ in terms of the spectrum of the new operator as:

$\widetilde{\lambda}^{\prime\prime}_{\ell-1}\leq\lambda<\widetilde{\lambda}_{\ell+2}^{\prime\prime}\,.$

Now, define the two counting functions $\Delta n(e_{0},f)$ and $M(e_{0},f)$.
The first one counts how the variational interval in which $\lambda$ is
contained changes when moving from $\widetilde{\mathcal{G}}^{\prime}$ to
$\widetilde{\mathcal{G}}^{\prime\prime}$, namely:

$\Delta
n(e_{0},f)=\begin{cases}-1&\lambda<\widetilde{\lambda}_{\ell}^{\prime\prime}\\\
+1&\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\lambda\geq\widetilde{\lambda}_{\ell+1}^{\prime\prime}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\\\
0&\text{otherwise.}\end{cases}$

Observe that $\Delta n(e_{0},f)=-1$ implies that
$\lambda\in[\widetilde{\lambda}_{\ell-1}^{\prime\prime},\widetilde{\lambda}_{\ell}^{\prime\prime})$,
$\Delta n(e_{0},f)=1$ implies that
$\lambda\in[\widetilde{\lambda}_{\ell+1}^{\prime\prime},\widetilde{\lambda}_{\ell+2}^{\prime\prime})$,
and $\Delta n(e_{0},f)=0$ implies that
$\lambda\in[\widetilde{\lambda}_{\ell}^{\prime\prime},\widetilde{\lambda}_{\ell+1}^{\prime\prime})$.

The second counting function, $M(e_{0},f)$, takes into account the sign of $f$
on the removed edge $e_{0}$. Recall that, if $\mathrm{sign}_{e_{0}}(f)<0$ then
from Section 5.1 it follows that
$\lambda\in[\widetilde{\lambda}^{\prime\prime}_{\ell-1},\widetilde{\lambda}^{\prime\prime}_{\ell+1})$,
otherwise we have
$\lambda\in[\widetilde{\lambda}^{\prime\prime}_{\ell},\widetilde{\lambda}^{\prime\prime}_{\ell+2})$.
Thus, we define

$M(e_{0},f):=\begin{cases}\begin{cases}-1&\lambda<\widetilde{\lambda}_{\ell}^{\prime\prime}\\\
0&\text{otherwise}\end{cases}\qquad&\text{if}\quad\mathrm{sign}_{e_{0}}(f)<0\,,\\\\[15.00002pt]
\begin{cases}0&\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\lambda\geq\widetilde{\lambda}_{\ell+1}^{\prime\prime}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\\\
-1&\text{otherwise}\end{cases}\qquad&\text{if}\quad\mathrm{sign}_{e_{0}}(f)>0\,.\end{cases}$

It follows by their definition and from Lemma 5.2 that

$\Delta n(e_{0},f)-M(e_{0},f)=\begin{cases}0&\mathrm{sign}_{e_{0}}(f)<0\\\
1&\mathrm{sign}_{e_{0}}(f)>0\end{cases}\,.$

Thus, thanks to (35), every time we cut an edge $e_{0}$ and modify
consequently the operator $\mathcal{H}_{p}^{\prime}$, we have the following
identity

(41) $\Delta n(e_{0},f)-M(e_{0},f)=\Delta\nu(e_{0},f)-\Delta l(e_{0},f)\,,$

where $\Delta\nu(e_{0},f)$ and $\Delta l(e_{0},f)$ are the difference between
the number of nodal domains and the number of constant sign loops induced by
$f$ in $\widetilde{\mathcal{G}}^{\prime}$ and in
$\widetilde{\mathcal{G}}^{\prime\prime}$, respectively.

After $\beta^{\prime}$ steps, $(f,\lambda)$ will be an eigenpair of a
generalized $p$-Laplacian operator $\mathcal{H}_{p}^{\prime\prime}$ defined on
the forest $\mathcal{T}$, such that $f(u)\neq 0\;\forall
u\in\mathcal{G}^{\prime\prime}$. We have proved in Theorem 3.7 that
$\mathcal{H}_{p}^{\prime\prime}$ has only variational eigenvalues, so,
w.l.o.g., we can assume that $\lambda$ has became the $s$-th variational
eigenvalue of $\mathcal{H}_{p}^{\prime\prime}$.  Note that, thanks to Theorem
3.7 and Remark 6.10 we have that
$\mathrm{mult}_{\mathcal{H}_{p}^{\prime\prime}}(\lambda)=c(f)$, that is

$\lambda_{s-c(f)}^{\prime\prime}<\lambda=\lambda_{s-c(f)+1}^{\prime\prime}=\dots=\lambda_{s}^{\prime\prime}<\lambda_{s+1}^{\prime\prime}.$

Moreover, because of Theorem 3.8, we know that $f$ induces $s$ nodal domains
on the forest $\mathcal{T}$. Thus, using (41) and the equality
$\sum_{i=1}^{\beta^{\prime}}\Delta\nu(e_{i},f)=s-\nu(f)$, the number of nodal
domains, $\nu(f)$, induced on the original graph $\mathcal{G}$ by $f$ (which
is the same as the one induced on $\mathcal{G}^{\prime}$), can be written as

$\nu(f)={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}s}-\sum_{i=1}^{\beta^{\prime}}\Delta\nu(e_{i},f)={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}s}-\sum_{i=1}^{\beta^{\prime}}\Delta
n(e_{i},f)-\sum_{i=1}^{\beta^{\prime}}\Delta
l(e_{i},f)+\sum_{i=1}^{\beta^{\prime}}M(e_{i},f)\,.$

Finally, observe that, by definition of $\Delta n$, it holds

$\sum_{i=1}^{\beta^{\prime}}\Delta
n(e_{i},f)={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}s}-h,\qquad\text{and}\qquad\sum_{i=1}^{\beta^{\prime}}\Delta
l(e_{i},f)=-l(f)$

because we have removed all the loops, while
$\sum_{i=1}^{\beta^{\prime}}M(e_{i},f)\geq-\beta^{\prime}(f)$ (note that the
equality holds if and only if $M(e_{i},f)=-1$, $\forall i$). Hence, using
inequality (40), we obtain

$\nu(f)\geq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}s}-{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}s}+h+l(f)-\beta^{\prime}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(f)}=h+l(f)-\beta^{\prime}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(f)}\geq
k+{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}m}-1-z(f)+l(f)-\beta^{\prime}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(f)}\,,$

which concludes the proof. ∎

##  Appendix A A technical lemma

We devote this appendix to the following technical lemma, which is helpful to
prove several of our main results.

######  Lemma A.1.

Consider the function

(42)
$R(\beta_{1},\beta_{2})=\Big{(}\frac{|\beta_{1}|^{p}}{\phi_{p}\big{(}\alpha_{1}\big{)}}-\frac{|\beta_{2}|^{p}}{\phi_{p}\big{(}\alpha_{2}\big{)}}\Big{)}\phi_{p}\big{(}\alpha_{1}-\alpha_{2}\big{)}-\big{(}\beta_{1}-\beta_{2}\big{)}\phi_{p}\Big{(}\beta_{1}-\beta_{2}\Big{)}\,,$

where $\phi_{p}(x)=|x|^{p-2}x$, $\alpha_{1},\alpha_{2},\beta_{1},\beta_{2}$
are real numbers, and ${\alpha={\alpha_{2}}/{\alpha_{1}}}$. Then
$R(\beta_{1},\beta_{2})$ is positive if $\alpha$ is negative and negative if
$\alpha$ is positive. Moreover $R(\beta_{1},\beta_{2})=0$ if and only if
${\beta={\beta_{1}}/{\beta_{2}}={\alpha_{1}}/{\alpha_{2}}}$.

###### Proof.

We first consider the special cases where either $\beta_{1}$ or $\beta_{2}$
are zero or $\alpha=1$. When $\beta_{2}=0$ (42) becomes

$\displaystyle
R(\beta_{1},0)=|\beta_{1}|^{p}\Big{(}\phi_{p}\big{(}1-\alpha\big{)}-1\Big{)},$

and a simple computation shows that $\big{(}\phi_{p}(1-\alpha)-1\big{)}\geq 0$
if and only if $\alpha<0$. The case with $\beta_{1}=0$ is similar, since
$R(0,\beta_{2})=|\beta_{2}|^{p}\Big{(}\phi_{p}\big{(}1-\frac{1}{\alpha}\big{)}-1\Big{)}$.
Next, consider the case $\alpha=1$. In this case (42) simplifies to
$R(\beta_{1},\beta_{2})=-|\beta_{1}-\beta_{2}|^{p}\leq 0$ and one easily sees
that the equality holds if and only if $\beta_{1}=\beta_{2}$.

Consider now the case where both $\beta_{1}$ and $\beta_{2}$ are different
from zero and $\alpha\neq 1$. Equation (42) can be written as

(43) $\displaystyle
R(\beta_{1},\beta_{2})=|\beta_{1}|^{p}\bigg{(}\phi_{p}(1-\alpha)-\phi_{p}\Big{(}1-\frac{\beta_{2}}{\beta_{1}}\Big{)}\bigg{)}+|\beta_{2}|^{p}\bigg{(}\phi_{p}\Big{(}1-\frac{1}{\alpha}\Big{)}-\phi_{p}\Big{(}1-\frac{\beta_{1}}{\beta_{2}}\Big{)}\bigg{)}.$

Dividing (43) by $|\beta_{2}|^{p}$ and letting $\beta=\beta_{1}/\beta_{2}$ we
get the chain of inequalities

$\displaystyle|\beta|^{p}\phi_{p}(1-\alpha)+\phi_{p}\Big{(}1-\frac{1}{\alpha}\Big{)}\geq|\beta|^{p}\phi_{p}\Big{(}1-\frac{1}{\beta}\Big{)}+\phi_{p}\Big{(}1-\beta\Big{)}$
$\displaystyle\iff\quad$
$\displaystyle\frac{|\beta(1-\alpha)|^{p}}{(1-\alpha)}+\frac{|1-\frac{1}{\alpha}|^{p}}{1-\frac{1}{\alpha}}\geq|\beta-1|^{p-2}(\beta^{2}-\beta)+|\beta-1|^{p-2}(1-\beta)$
(44) $\displaystyle\iff\quad$
$\displaystyle\frac{|\beta(1-\alpha)|^{p}}{(1-\alpha)}+\frac{|1-\frac{1}{\alpha}|^{p}}{1-\frac{1}{\alpha}}\geq|\beta-1|^{p}\,.$

Now, if $1<\alpha<0$, then ${0\\!<\\!\frac{1}{(1-\alpha)}\\!<\\!1}$ and
${\frac{1}{(1-\alpha)}+\frac{1}{1-\frac{1}{\alpha}}=1}$, so we can use the
convexity of $x\mapsto|x|^{p}$ to obtain

$\frac{|\beta(1-\alpha)|^{p}}{(1-\alpha)}+\frac{|1-\frac{1}{\alpha}|^{p}}{1-\frac{1}{\alpha}}\geq|\beta-1|^{p}\,.$

Since $x\mapsto|x|^{p}$ is strictly convex for $p>1$, the equality in the
expression above holds if and only if $\beta(1-\alpha)=\frac{1}{\alpha}-1$
showing that $R(\beta_{1},\beta_{2})$ is positive if $\alpha$ is negative.

To face the case $\alpha>0$, consider again equation (43). We can assume
without loss of generality that $0<\alpha<1$. Indeed, if $\alpha>1$, we can
divide (43) by $|\beta_{1}|^{p}$ to obtain an equation like (44) where
$1/\alpha$ is used in place of $\alpha$ and the proof would follow from the
argument above. Returning to the case $0<\alpha<1$, from (43) and the
following sequence of inequalities can be obtained following the same steps as
above:

$\displaystyle|\beta|^{p}\phi_{p}(1-\alpha)+\phi_{p}\Big{(}1-\frac{1}{\alpha}\Big{)}\leq|\beta-1|^{p}$
$\displaystyle\iff\quad$
$\displaystyle|\beta|^{p}\leq\frac{|\beta-1|^{p}}{\phi_{p}(1-\alpha)}+\frac{\phi_{p}\Big{(}\frac{1-\alpha}{\alpha}\Big{)}}{\phi_{p}(1-\alpha)}$
$\displaystyle\iff\quad$
$\displaystyle|\beta|^{p}\leq\Big{|}\frac{\beta-1}{(1-\alpha)}\Big{|}^{p}(1-\alpha)+\Big{|}\frac{1}{\alpha}\Big{|}^{p}\alpha$

Note that, as before, the last inequality holds due to the convexity of
$x\mapsto|x|^{p}$ and thus equality holds if and only if
$\frac{\beta-1}{(1-\alpha)}=\frac{1}{\alpha}$ which implies
$\beta=\frac{1}{\alpha}$, concluding the proof. ∎

## Acknowledgements

We are indebted to Shiping Liu and Chuanyuan Ge for their careful reading of
the first version of this work and their precious comments. We would also like
to thank two anonymous referees for their very useful observations. All their
feedback greatly helped us improve the quality of the presentation of the main
results as well as some of their proofs.

## References

  * Alon [1986] N. Alon.  Eigenvalues and expanders.  _Combinatorica_ , 6(2):83–96, 1986.  doi: 10.1007/BF02579166.
  * Amghibech [2003] S. Amghibech.  Eigenvalues of the discrete p-Laplacian for graphs.  _Ars Combinatoria_ , 67:283–302, 04 2003.
  * Amghibech [2006] S. Amghibech.  Bounds for the largest p-Laplacian eigenvalue for graphs.  _Discr. Math._ , 306:2762–2771, 2006.  doi: 10.1016/j.disc.2006.05.012.
  * Band et al. [2007] R. Band, I. Oren, and U. Smilansky.  Nodal domains on graphs - how to count them and why?  In _Proc. Sympos. Pure Math., Providence, RI: Amer. Math. Soc_ , volume 77, 11 2007.  doi: 10.1090/pspum/077/2459862.
  * Berkolaiko [2008] G. Berkolaiko.  A lower bound for nodal count on discrete and metric graphs.  _Comm. Math. Phys._ , 278(3):803–819, 2008.  doi: 10.1007/s00220-007-0391-3.
  * Berkolaiko et al. [2011] G. Berkolaiko, H. Raz, and U. Smilansky.  Stability of nodal structures in graph eigenfunctions and its relation to the nodal domain count.  _J. Phys. A_ , 45, 10 2011.  doi: 10.1088/1751-8113/45/16/165203.
  * Biyikoğlu [2003] T. Biyikoğlu.  A discrete nodal domain theorem for trees.  _Linear Algebra Appl._ , 360:197–205, 2003.  doi: 10.1016/S0024-3795(02)00451-2.
  * Biyikoğlu et al. [2005] T. Biyikoğlu, J. Leydold, and P. Stadler.  Nodal domain theorems and bipartite subgraphs.  _Electron. J. Lin. Alg._ , 13:344–351, 01 2005.  doi: 10.13001/1081-3810.1167.
  * Blum et al. [2002] G. Blum, S. Gnutzmann, and U. Smilansky.  Nodal domains statistics: A criterion for quantum chaos.  _Phys. Rev. Let._ , 88, 04 2002.  doi: 10.1103/PhysRevLett.88.114101.
  * Bresson et al. [2013] X. Bresson, T. Laurent, D. Uminsky, and J. H. v. Brecht.  Multiclass total variation clustering.  In _Proceedings of the 26th International Conference on Neural Information Processing Systems-Volume 1_ , pages 1421–1429, 2013.
  * Bresson et al. [2014] X. Bresson, X.-C. Tai, T. F. Chan, and A. Szlam.  Multi-class transductive learning based on $\ell^{1}$ relaxations of Cheeger cut and Mumford-Shah-Potts model.  _J. Math. Imaging Vis._ , 49(1):191–201, 2014\.  doi: 10.1007/s10851-013-0452-5.
  * Bühler and Hein [2009] T. Bühler and M. Hein.  Spectral clustering based on the graph p-laplacian.  In _Proceedings of the 26th Annual International Conference on Machine Learning_ , page 81–88, 2009.  doi: 10.1145/1553374.1553385.
  * Calder [2018] J. Calder.  The game theoretic $p$-laplacian and semi-supervised learning with few labels.  _Nonlinearity_ , 32(1):301–330, dec 2018.  doi: 10.1088/1361-6544/aae949.
  * Chang et al. [2017] K.-C. Chang, S. Shao, and D. Zhang.  Nodal domains of eigenvectors for 1-Laplacian on graphs.  _Adv. Math._ , 308:529–574, 2017.  doi: 10.1016/j.aim.2016.12.020.
  * Courant and Hilbert [1953] R. Courant and D. Hilbert.  _Methods of Mathematical Physics_ , volume 1.  Interscience, New York, 1953.  doi: 10.1002/9783527617210.
  * Daneshgar et al. [2012] A. Daneshgar, R. Javadi, and L. Miclo.  On nodal domains and higher-order Cheeger inequalities of finite reversible markov processes.  _Stoch. Proc. Appl._ , 122(4):1748–1776, 2012\.  doi: 10.1016/j.spa.2012.02.009.
  * Davies et al. [2001] E. B. Davies, G. Gladwell, J. Leydold, and P. Stadler.  Discrete nodal domain theorems.  _Linear Algebra Appl._ , 336(1):51–60, 2001.  doi: 10.1016/S0024-3795(01)00313-5.
  * Drábek and Robinson [2002] P. Drábek and S. B. Robinson.  On the generalization of the Courant nodal domain theorem.  _J. Differ. Equ._ , 181(1):58–71, 2002.  doi: 10.1006/jdeq.2001.4070.
  * Duval and Reiner [1999] A. Duval and V. Reiner.  Perron–Frobenius type results and discrete versions of nodal domain theorems.  _Linear Algebra Appl._ , 294(1):259–268, 1999\.  doi: 10.1016/S0024-3795(99)00090-7.
  * El Alaoui et al. [2016] A. El Alaoui, X. Cheng, A. Ramdas, M. J. Wainwright, and M. I. Jordan.  Asymptotic behavior of $\ell_{p}$-based Laplacian regularization in semi-supervised learning.  In _29th Annual Conference on Learning Theory_ , volume 49 of _Proceedings of Machine Learning Research_ , pages 879–906. PMLR, 23–26 Jun 2016.
  * Elmoataz et al. [2015] A. Elmoataz, M. Toutain, and D. Tenbrinck.  On the p-Laplacian and $\infty$-Laplacian on graphs with applications in image and data processing.  _SIAM J. Imaging Sci._ , 8:2412–2451, 11 2015.  doi: 10.1137/15M1022793.
  * Fasino and Tudisco [2014] D. Fasino and F. Tudisco.  An algebraic analysis of the graph modularity.  _SIAM J. Matrix Anal. and Appl._ , 35(3):997–1018, 2014.  doi: 10.1137/130943455.
  * Fiedler [1975] M. Fiedler.  Eigenvectors of acyclic matrices.  _Czechoslovak Mathematical Journal_ , 25(4):607–618, 1975.
  * Flores et al. [2022] M. Flores, J. Calder, and G. Lerman.  Analysis and algorithms for $\ell_{p}$-based semi-supervised learning on graphs.  _Applied and Computational Harmonic Analysis_ , 60:77–122, 2022.  ISSN 1063-5203.  doi: 10.1016/j.acha.2022.01.004.
  * Friedman [1993] J. Friedman.  Some geometric aspects of graphs and their eigenfunctions.  _Duke Math. J._ , 69(3), 1993.  ISSN 00127094.  doi: 10.1215/S0012-7094-93-06921-9.
  * Gnutzmann et al. [2005] S. Gnutzmann, U. Smilansky, and N. Søndergaard.  Resolving isospectral “drums” by counting nodal domains.  _J. Phys. A Gen._ , 38:8921–8933, 04 2005.  doi: 10.1088/0305-4470/38/41/006.
  * Gnutzmann et al. [2006] S. Gnutzmann, P. Karageorge, and U. Smilansky.  Can one count the shape of a drum?  _Phys. Rev. Let._ , 97:090201, 10 2006.  doi: 10.1103/PhysRevLett.97.090201.
  * Hua and Wang [2020] B. Hua and L. Wang.  Dirichlet p-laplacian eigenvalues and cheeger constants on symmetric graphs.  _Advances in Mathematics_ , 364:106997, 04 2020.  doi: 10.1016/j.aim.2020.106997.
  * Kyritsi-Yiallourou and Papageorgiou [2009] S. T. Kyritsi-Yiallourou and N. S. Papageorgiou.  _Handbook of Applied Analysis_.  Springer US, 2009.  doi: 10.1007/b120946.
  * Lawler and Sokal [1988] G. F. Lawler and A. D. Sokal.  Bounds on the $\ell^{2}$ spectrum for Markov chains and Markov processes: a generalization of Cheeger’s inequality.  _Trans. Amer. Math. Soc._ , 309(2):557–580, 1988\.  doi: 10.2307/2000925.
  * Lindqvist [1990] P. Lindqvist.  On the equation $\mathrm{div}(|\nabla u|^{p-2}\nabla u)+\lambda|u|^{p-2}u=0$.  _Proc. Amer. Math. Soc._ , 109:157–164, 5 1990.  doi: 10.2307/2048375.
  * Lindqvist [1993] P. Lindqvist.  Note on a nonlinear eigenvalue problem.  _Rocky Mountain J. Math._ , 1:281–288, 3 1993.  doi: 10.1216/rmjm/1181072623.
  * Oren [2007] I. Oren.  Nodal domain counts and the chromatic number of graphs.  _J. Phys. A_ , 40:9825–9832, 07 2007.  doi: 10.1088/1751-8113/40/32/008.