# Deletion-contraction for a unified Laplacian
and applications

Farid Aliniaeifard  Department of Mathematics, University of British Columbia,
Vancouver BC V6T 1Z2, Canada<EMAIL_ADDRESS>,  Victor Wang  Department of
Mathematics, University of British Columbia, Vancouver BC V6T 1Z2, Canada
<EMAIL_ADDRESS>and  Stephanie van Willigenburg  Department of
Mathematics, University of British Columbia, Vancouver BC V6T 1Z2, Canada
<EMAIL_ADDRESS>
###### Abstract.

We define a graph Laplacian with vertex weights in addition to the more
classical edge weights, which unifies the combinatorial Laplacian and the
normalised Laplacian. Moreover, we give a combinatorial interpretation for the
coefficients of the weighted Laplacian characteristic polynomial in terms of
weighted spanning forests and use this to prove a deletion-contraction
relation. We prove various interlacing theorems relating to deletion and
contraction, as well as to rectangular tilings, drawing on the work of Brooks,
Smith, Stone and Tutte on square tilings. Additionally, we show that the
weighted Laplacian also satisfies a vertex analogue of deletion-contraction.
We give applications of weighted Laplacian eigenvalues to sparse cuts,
independent sets and graph colouring, and establish new cases of a conjecture
of Stanley on distinguishing nonisomorphic trees.

###### Key words and phrases:

deletion-contraction, interlacing, Laplacian matrix, spanning forest, weighted
graph

###### 2010 Mathematics Subject Classification:

05C22, 05C31, 05C50, 05C60

All authors were supported in part by the National Sciences and Engineering
Research Council of Canada.

###### Contents

  1. 1 Introduction
  2. 2 Background
  3. 3 Discrete vector calculus and the weighted Laplacian
  4. 4 Deletion-contraction from weighted spanning forests
  5. 5 Interlacing theorems
  6. 6 Addition-reduction from equivalent electrical networks
  7. 7 Weighted spectral bounds
  8. 8 New families of trees distinguished by the chromatic symmetric function
  9. 9 Acknowledgments

##  1\. Introduction

The combinatorial Laplacian matrix $L_{G}=D_{G}-A_{G}$ of a graph $G$, defined
by the difference between the degree and adjacency matrices of $G$, was
perhaps first studied by Kirchhoff [27] in his 1847 paper on electrical
networks. In the same paper, Kirchhoff discovered the celebrated matrix-tree
theorem, which states that the number of spanning trees of a graph $G$ is
equal to any cofactor of $L_{G}$. Intriguingly, the matrix-tree theorem also
arises in the work of Brooks, Smith, Stone and Tutte [8] on square tilings,
which they also found were related to electrical circuits.

In the 1990’s, Chung [17] popularised the normalised Laplacian matrix,
sometimes defined by $\mathcal{L}_{G}=D_{G}^{-1}L_{G}$, which has connections
to random walks as $\mathcal{L}_{G}=I-D_{G}^{-1}A_{G}$ where $D_{G}^{-1}A_{G}$
is the random walk matrix. The combinatorial and normalised Laplacians may be
viewed as discrete analogues of the (negative) Laplace-Beltrami operator on
Riemannian manifolds, defined by the negative divergence of the gradient, and
this connection has been used to relate the second combinatorial and
normalised Laplacian eigenvalues of a graph to sparse (normalised) cuts [17,
22], giving a discrete analogue of Cheeger’s isoperimetric inequality in
Riemannian geometry [15]. In addition, combinatorial and normalised Laplacian
eigenvalues can be used to obtain bounds on various parameters of a graph,
including its chromatic number [17, 19], diameter [17, 34] and independence
number [25].

Another topic of interest in graph theory is the notion of deletion-
contraction. Many graph polynomials and invariants, including number of
acyclic orientations [42], spanning trees and spanning forests, as well as a
graph’s chromatic and flow polynomials [45], satisfy a recursive formula
relating a graph and the two graphs obtained by deleting and contracting an
edge. The combinatorial and normalised Laplacian characteristic polynomials,
however, are not known to satisfy a deletion-contraction recursion. The
effects of edge deletion, contraction and related operations on combinatorial
and normalised Laplacian eigenvalues are studied across [11, 14, 24].

The definitions of the combinatorial and normalised Laplacians can be
naturally extended to edge-weighted graphs $(G,\varepsilon)$, and these have
been studied by several authors, including by Kirchhoff in his original paper
[27], where the edge weights represent the conductances of wires. In contrast,
graph Laplacians with vertex weights are not so commonly studied, and there
exist competing definitions for such a matrix [18, 23, 29]. Vertex-weighted
graphs appear in the work of Noble and Welsh [35], in which they define a
polynomial associated to integer vertex-weighted graphs satisfying a deletion-
contraction rule, motivated by the study of Vassiliev invariants of knots
[16]. Vertex weights also arise in graph theory applications; when studying
independent sets in job scheduling, the weight of a vertex can be used to
represent the relative reward for the completion of each job.

Our paper defines a weighted Laplacian for graphs with both vertex and edge
weights, which specialises to the combinatorial and normalised Laplacians for
certain choices of vertex weights, unifying the discussion of the two
Laplacian matrices. Moreover, the incorporation of vertex weights gives rise
to a deletion-contraction recursion for the weighted Laplacian characteristic
polynomial. Our paper is more precisely structured as follows.

We cover the necessary background in Section 2. In Section 3 we introduce the
inner product spaces $L^{2}(V,\upsilon)$ and $L^{2}(E,\varepsilon)$ of scalar
fields and vector fields, respectively, associated with a weighted graph
$(G,\upsilon,\varepsilon)$, and define discrete analogues of negative
divergence and gradient. We use these to define the weighted Laplacian
$L_{(G,\upsilon,\varepsilon)}$ and edge Laplacian
$K_{(G,\upsilon,\varepsilon)}$ in Definitions 3.6 and 3.9, and briefly develop
their theory. Then in Section 4 we give a combinatorial interpretation of
weighted Laplacian characteristic polynomial coefficients in terms of weighted
spanning forests in Theorem 4.2, and deduce a deletion-contraction recurrence
in Theorem 4.4. In Section 5 we use deletion-contraction to obtain an
interlacing theorem relating the weighted Laplacian eigenvalues of a weighted
graph and those obtained by deleting and contracting an edge in Theorem 5.4.
We then apply our techniques to obtain various interlacing results on
combinatorial and normalised Laplacian eigenvalues of quotient graphs in
Corollaries 5.8 and 5.9, as well as graphs obtained by subgraph deletion in
Corollaries 5.11 and 5.13. In Section 6 we study interlacing theorems arising
from rectangular tilings and Kron reduction in Theorems 6.3 and 6.7, and prove
a vertex analogue of deletion-contraction in Theorem 6.8, which we call
addition-reduction. We give applications of weighted Laplacian eigenvalues in
Section 7, proving an isoperimetric inequality in Corollary 7.2 and bounds on
independent sets and the chromatic number in Theorems 7.3 and 7.7. Finally, in
Section 8 we use deletion-contraction to relate the weighted Laplacian
characteristic polynomial to the chromatic symmetric function and other graph
polynomials, and use this to establish new cases of Stanley’s tree isomorphism
conjecture in Corollary 8.7.

##  2\. Background

A graph $G$ consists of a vertex set $V(G)$ and an edge set $E(G)$
representing connections between pairs of vertices. When the underlying graph
$G$ is clear, we may denote the vertex and edge sets of a graph simply by $V$
and $E$, respectively. All graphs in this paper will be finite multigraphs,
with finite vertex and edge sets, the latter of which may include loops (edges
connecting some vertex to itself) or multiple edges (two or more edges
incident to the same pair of vertices). A graph is simple if it has no loops
or multiple edges.

For $u,v\in V$, we write $uv$ to mean an edge connecting $u$ and $v$. A
directed edge consists of an edge together with a choice of one of two
orientations; an edge $uv$ may either be oriented from $u$ to $v$, with
corresponding directed edge written $\vec{uv}$, or from $v$ to $u$, with
corresponding directed edge written $\vec{vu}$. The set of directed edges of a
graph $G$ is denoted $\vec{E}(G)$, or $\vec{E}$ when the underlying graph $G$
is clear.

If $e$ is an edge not in $E$, we write $G+e$ to denote the graph obtained by
adding $e$ to the edge set of $G$. We write $G-S$ for $S\subseteq V$ to denote
the graph obtained from $G$ by removing all vertices in $S$ and any incident
edges. Similarly, for $R\subseteq E$, we write $G-R$ to denote the graph
obtained from $G$ by removing the edges in $R$. When $R=\\{e\\}$, we may also
denote this by $G-e$. Additionally, we write $G[R]$ for $R\subseteq E$ to
denote the subgraph of $G$ induced by $R$, consisting of the edges in $R$ and
all incident vertices.

A weighted graph $(G,\upsilon,\varepsilon)$ consists of a graph $G$ together
with vertex weights and edge weights given by weight functions
$\upsilon:V\to\mathbb{R}_{>0}$ and $\varepsilon:E\to\mathbb{R}_{>0}$,
respectively. An edge-weighted graph $(G,\varepsilon)$ is a weighted graph in
which vertex weights are negligible and taken to equal $1$. Similarly, a
vertex-weighted graph $(G,\upsilon)$ is a weighted graph in which edge weights
are negligible and taken to equal $1$. We may also write $G$ to denote an
unweighted graph, in which all vertex and edge weights are taken to equal $1$.

If $G$ and $G^{\prime}$ are two graphs, we write $G\oplus G^{\prime}$ to
denote their disjoint union. Similarly, if $(G,\upsilon,\varepsilon)$ and
$(G^{\prime},\upsilon^{\prime},\varepsilon^{\prime})$ are two weighted graphs,
we denote their disjoint union by
$(G,\upsilon,\varepsilon)\oplus(G^{\prime},\upsilon^{\prime},\varepsilon^{\prime})$.

Given a graph $G$ and an equivalence relation $\sim$ on its vertex set $V$,
the quotient graph $G/\sim$ is the graph obtained by formally identifying the
vertices in each equivalence class of $\sim$. If $(G,\upsilon,\varepsilon)$ is
a weighted graph, the quotient weighted graph $(G,\upsilon,\varepsilon)/\sim$
is $(G/\sim,\upsilon/\sim,\varepsilon)$, where the weight under
$\upsilon/\sim$ of an element of $V/\sim$ is the sum of the weights under
$\upsilon$ of the vertices in the equivalence class of $V$. For $S\subseteq
V$, we write $S^{c}$ to denote its complement $V\setminus S$.

Given an edge-weighted graph $(G,\varepsilon)$ and two vertices $u,v$, we
write $\varepsilon(u,v)$ to denote the total edge weight between $u$ and $v$,
with loops counted twice. The degree $d_{(G,\varepsilon)}(u)$ of a vertex $u$
is given by the sum $\sum_{v\in V}\varepsilon(u,v)$. An isolated vertex is a
vertex of degree zero. If $(G,\varepsilon)$ is an edge-weighted graph with
vertices arbitrarily ordered as $v_{1},\dots,v_{n}$, the adjacency matrix of
$(G,\varepsilon)$ is the $n\times n$ matrix $(a_{ij})$, where each
$a_{ij}=\varepsilon(v_{i},v_{j})$, and the degree matrix $D_{(G,\varepsilon)}$
is the $n\times n$ diagonal matrix with $i$th diagonal entry given by
$d_{(G,\varepsilon)}(v_{i})$.

The study of spectral graph theory relates the eigenvalues of matrices
associated to graphs and weighted graphs to graph parameters. Two important
matrices associated to an edge-weighted graph are the combinatorial Laplacian
and the normalised Laplacian.

######  Definition 2.1.

The combinatorial Laplacian of an edge-weighted multigraph $(G,\varepsilon)$
with vertex set $\\{v_{1},\dots,v_{n}\\}$ is

$L_{(G,\varepsilon)}=D_{(G,\varepsilon)}-A_{(G,\varepsilon)}.$

One application of the combinatorial Laplacian is the celebrated matrix-tree
theorem. We state a version on principal minors of the combinatorial Laplacian
for edge-weighted graphs, which may be deduced from the all minors matrix-tree
theorem in [13]. We will see that each principal minor of
$L_{(G,\varepsilon)}$ has a combinatorial interpretation in terms of rooted
spanning forests, which consist of a spanning forest of $G$, together with a
choice of a vertex from each connected component of the spanning forest,
constituting the roots. A spanning forest is $k$-rooted if it has $k$ roots,
and $S$-rooted for $S\subseteq V$ if its roots are given by $S$.

######  Theorem 2.2 (Principal minors matrix-tree theorem).

Let $(G,\varepsilon)$ be an edge-weighted multigraph and let $S\subseteq V$.
Let $L_{(G,\varepsilon)}^{\hat{S}}$ denote the principal submatrix of
$L_{(G,\varepsilon)}$ obtained by deleting the rows and columns corresponding
to $S$. Then

$\det L^{\hat{S}}_{(G,\varepsilon)}=\sum_{F}\prod_{e\in E(F)}\varepsilon(e),$

where the sum is over all $S$-rooted spanning forests $F$ of $G$.

######  Definition 2.3.

The normalised Laplacian of an edge-weighted multigraph $(G,\varepsilon)$ with
no isolated vertices and vertex set $\\{v_{1},\dots,v_{n}\\}$ is

$\mathcal{L}_{(G,\varepsilon)}=D_{(G,\varepsilon)}^{-1}L_{(G,\varepsilon)}.$

Many authors define the normalised Laplacian instead by
$D_{(G,\varepsilon)}^{-1/2}L_{(G,\varepsilon)}D_{(G,\varepsilon)}^{-1/2}$,
which is a real symmetric matrix. However, the two possible definitions of the
normalised Laplacian give similar matrices, as
$D_{(G,\varepsilon)}^{-1/2}L_{(G,\varepsilon)}D_{(G,\varepsilon)}^{-1/2}=D_{(G,\varepsilon)}^{1/2}\mathcal{L}_{(G,\varepsilon)}D_{(G,\varepsilon)}^{-1/2}$.
In particular, the two matrices share the same eigenvalues, and the
eigenvectors of one may be recovered from the eigenvectors of the other by the
change of basis matrix $D_{(G,\varepsilon)}^{1/2}$. The motivation for having
the normalised Laplacian be symmetric is given by the spectral theorem on
self-adjoint operators.

If $A:V\to W$ is a linear map between two finite-dimensional inner product
spaces, then its adjoint is the unique linear map $A^{*}:W\to V$ satisfying
$\langle Ax,y\rangle=\langle x,A^{*}y\rangle$ for all $x\in V$ and $y\in W$. A
linear map $A:V\to V$ is self-adjoint if it is equal to its own adjoint. Note
that when the inner product space $V$ is given by $\mathbb{R}^{n}$ with the
Euclidean inner product, the self-adjoint maps $V\to V$ are exactly the
$n\times n$ real symmetric matrices.

######  Theorem 2.4 (Spectral theorem).

Let $V$ be an $n$-dimensional inner product space, and let $A:V\to V$ be a
self-adjoint linear map. Then $A$ has $n$ real eigenvalues, and there exists
an orthonormal basis of $V$ consisting of eigenvectors of $A$.

In particular, for any edge-weighted graph $(G,\varepsilon)$ on $n$ vertices,
$L_{(G,\varepsilon)}$ has $n$ real eigenvalues and there exists an orthonormal
basis of $\mathbb{R}^{n}$ consisting of eigenvectors of $L_{(G,\varepsilon)}$.
Since $\mathcal{L}_{(G,\varepsilon)}$ is similar to symmetric
$D_{(G,\varepsilon)}^{-1/2}L_{(G,\varepsilon)}D_{(G,\varepsilon)}^{-1/2}$, it
also has $n$ real eigenvalues.

Given a self-adjoint linear map $A:V\to V$, where $V$ is a finite-dimensional
inner product space, the Rayleigh quotient of nonzero $x\in V$ is the value
$\frac{\langle Ax,x\rangle}{\langle x,x\rangle}$. Note when $x$ is an
eigenvector of $A$, the Rayleigh quotient of $x$ is the corresponding
eigenvalue. Rayleigh quotients can be used to bound the extreme eigenvalues of
a self-adjoint operator.

######  Lemma 2.5.

Let $V$ be an $n$-dimensional inner product space, and let $A:V\to V$ be a
self-adjoint linear map. Let $\lambda_{1}$ and $\lambda_{n}$ denote the
smallest and largest eigenvalues of $A$, respectively. Then for any nonzero
$x\in V$, we have

$\lambda_{1}\leq\frac{\langle Ax,x\rangle}{\langle
x,x\rangle}\leq\lambda_{n}.$

An isometry $\iota:V\to W$ between finite-dimensional inner product spaces $V$
and $W$ is a linear map satisfying $\langle x,y\rangle=\langle\iota x,\iota
y\rangle$ for all $x,y\in V$. Note that an isometry is necessarily injective.

######  Theorem 2.6 (Cauchy interlacing theorem).

Let $V$ and $W$ be finite-dimensional inner product spaces, and let
$\iota:V\to W$ be an isometry. Let $\lambda_{1}\leq\dots\leq\lambda_{n}$ and
$\mu_{1}\leq\dots\leq\mu_{n-k}$ denote the eigenvalues of $A$ and
$\iota^{*}A\iota$, respectively, where $A:W\to W$ is a self-adjoint linear
map. Then

$\lambda_{i}\leq\mu_{i}\leq\lambda_{i+k}$

for all $1\leq i\leq n-k$.

######  Remark 2.7.

Under the hypotheses of the theorem, in order for a linear map $B:V\to V$ to
be equal to $\iota^{*}A\iota$, it is sufficient that $B$ be self-adjoint and
preserve quadratic form. To see this, note if

$\langle Bx,x\rangle=\langle A\iota x,\iota x\rangle$

for all $x\in V$, then $B-\iota^{*}A\iota$ is self-adjoint and satisfies
$\langle(B-\iota^{*}A\iota)x,x\rangle=0$ for all $x\in V$, implying that
$B-\iota^{*}A\iota$ is the zero matrix, having all eigenvalues zero.

One common application of the Cauchy interlacing theorem is when $V$ and $W$
are given by $\mathbb{R}^{n-k}$ and $\mathbb{R}^{n}$ with the usual Euclidean
inner product. If $A$ is an $n\times n$ real symmetric matrix and $B$ is an
$(n-k)\times(n-k)$ principal submatrix, then there is an isometry
$\iota:\mathbb{R}^{n-k}\to\mathbb{R}^{n}$ for which $B=\iota^{*}A\iota$. Note
that the Cauchy interlacing theorem also applies when taking a principal
submatrix of the matrix of a self-adjoint map in an orthogonal, and not
necessarily orthonormal, basis.

Finally, we will also write $[n]$ for $n\in\mathbb{Z}_{>0}$ to denote the set
$\\{1,\dots,n\\}$.

##  3\. Discrete vector calculus and the weighted Laplacian

In this section, we will introduce important inner product spaces and linear
maps associated with a weighted graph $(G,\upsilon,\varepsilon)$, and describe
analogies to concepts from classical vector calculus.

Since $\upsilon$ is a map $V\to\mathbb{R}_{>0}$, it can be extended to define
a measure on $V$. We define $L^{2}(V,\upsilon)$ to be the real inner product
space of scalar fields $f:V\to\mathbb{R}$, with inner product given by

$\langle f,g\rangle=\int_{V}fgd\upsilon=\sum_{v\in V}f(v)g(v)\upsilon(v).$

Similarly, $\varepsilon:E\to\mathbb{R}_{>0}$ can also be extended to define a
measure on $E$. We next define the real inner product space
$L^{2}(E,\varepsilon)$ of vector fields on our graph. If we make an arbitrary
choice of orientation for each edge of our graph, then to a first
approximation we can think of vector fields $\mathbf{F}\in
L^{2}(E,\varepsilon)$ as real-valued functions $\mathbf{F}:E\to\mathbb{R}$.
Then the definition of $L^{2}(E,\varepsilon)$ and its inner product coincides
with the usual definitions for the $L^{2}$ space associated with a measure
space.

However, it is more natural to think of elements of $L^{2}(E,\varepsilon)$ as
vector-valued functions on $E$. To each edge $uv\in E$, we associate a unique
real inner product space spanned by the unit vector

$\mathbf{v}_{\vec{uv}}=-\mathbf{v}_{\vec{vu}},$

where we think of $\mathbf{v}_{\vec{uv}}$ as a vector pointing towards $v$ and
away from $u$, and of $\mathbf{v}_{\vec{vu}}$ as a vector pointing towards $u$
and away from $v$. Then a vector field $\mathbf{F}\in L^{2}(E,\varepsilon)$ is
a choice for each edge $e\in E$ of a vector $\mathbf{F}(e)$ in the space
associated to $e$, and the inner product on $L^{2}(E,\varepsilon)$ is given by

$\langle\mathbf{F},\mathbf{G}\rangle=\int_{E}\mathbf{F}\cdot\mathbf{G}d\varepsilon=\sum_{e\in
E}\mathbf{F}(e)\cdot\mathbf{G}(e)\varepsilon(e).$

We will next introduce two important linear maps between the spaces defined.
The first map is defined by

$\displaystyle\partial:L^{2}(E,\varepsilon)$ $\displaystyle\to
L^{2}(V,\upsilon)$ $\displaystyle\partial\mathbf{F}(v)$
$\displaystyle=\sum_{\begin{subarray}{c}uv\in E\\\ u\neq
v\end{subarray}}\frac{\varepsilon(uv)}{\upsilon(v)}\mathbf{F}(uv)\cdot\mathbf{v}_{\vec{uv}}.$

Applying $\partial$ to a vector field gives a measure of the net flow into
each vertex per unit vertex weight, so $\partial$ is the discrete analogue of
negative divergence from vector calculus.

######  Example 3.1.

Let $(G,\upsilon,\varepsilon)$ be the weighted graph depicted on the left, and
let $\mathbf{F}\in L^{2}(E,\varepsilon)$ be the vector field depicted in the
centre. Then $\partial\mathbf{F}\in L^{2}(V,\upsilon)$ is the scalar field
depicted on the right. The value of $\partial\mathbf{F}$ at, for example, the
vertex of weight $2$ in $(G,\upsilon,\varepsilon)$ is obtained by computing
$\frac{-2-6-2+3}{2}=-\frac{7}{2}$.

12131123213$(G,\upsilon,\varepsilon)$0212132$\mathbf{F}$$\frac{4}{3}$$-1$$-\frac{7}{2}$$4$$\partial\mathbf{F}$

The second map is defined by

$\displaystyle\nabla:L^{2}(V,\upsilon)$ $\displaystyle\to
L^{2}(E,\varepsilon)$ $\displaystyle\nabla f(uv)$
$\displaystyle=(f(v)-f(u))\mathbf{v}_{\vec{uv}}.$

Applying $\nabla$ to a scalar field gives at each edge a vector pointing in
the direction of steepest ascent, so $\nabla$ is the discrete analogue of
gradient from vector calculus.

######  Example 3.2.

Let $(G,\upsilon,\varepsilon)$ be the weighted graph in Example 3.1, and let
$f\in L^{2}(V,\upsilon)$ be the scalar field depicted on the left. Then
$\nabla f\in L^{2}(E,\varepsilon)$ is the vector field depicted on the right.
The value of $\nabla f$ on, for example, the edge between the vertex $u$ of
weight $3$ and the vertex $v$ of weight $2$ in $(G,\upsilon,\varepsilon)$ is
obtained by computing $(1+2)\mathbf{v}_{\vec{uv}}=3\mathbf{v}_{\vec{uv}}.$

$-2$$2$$1$$1$$f$4330110$\nabla f$

######  Proposition 3.3.

The maps $\partial:L^{2}(E,\varepsilon)\to L^{2}(V,\upsilon)$ and
$\nabla:L^{2}(V,\upsilon)\to L^{2}(E,\varepsilon)$ are adjoint.

###### Proof.

For $\mathbf{F}\in L^{2}(E,\varepsilon)$ and $g\in L^{2}(V,\upsilon)$, we have

$\displaystyle\langle\partial\mathbf{F},g\rangle=\int_{V}\partial\mathbf{F}gd\upsilon$
$\displaystyle=\sum_{v\in V}\sum_{\begin{subarray}{c}uv\in E\\\ u\neq
v\end{subarray}}\frac{\varepsilon(uv)}{\upsilon(v)}\mathbf{F}(uv)\cdot\mathbf{v}_{\vec{uv}}g(v)\upsilon(v)$
$\displaystyle=\sum_{\begin{subarray}{c}uv\in E\\\ u\neq
v\end{subarray}}\mathbf{F}(uv)\cdot(g(u)\mathbf{v}_{\vec{vu}}+g(v)\mathbf{v}_{\vec{uv}})\varepsilon(uv)$
$\displaystyle=\sum_{uv\in
E}\mathbf{F}(uv)\cdot(g(v)-g(u))\mathbf{v}_{\vec{uv}}\varepsilon(uv)=\int_{E}\mathbf{F}\cdot\nabla
gd\varepsilon=\langle\mathbf{F},\nabla g\rangle,$

so $\partial$ and $\nabla$ are adjoint. ∎

Given a linear combination $S=\sum_{i=1}^{k}c_{i}v_{i}$ of vertices in $V$, we
define the characteristic function of $S$ to be
$1_{S}=\sum_{i=1}^{k}c_{i}1_{v_{i}}\in L^{2}(V,\upsilon)$, where each
$1_{v}\in L^{2}(V,\upsilon)$ is the scalar field evaluating to $1$ on $v$ and
zero on every other vertex. Then, we can define integration on $S$ by

$\int_{S}fd\upsilon=\int_{V}f1_{S}d\upsilon$

for $f\in L^{2}(V,\upsilon)$. We also identify $S\subseteq V$ with the linear
combination $\sum_{v\in S}v$.

Similarly, given a linear combination $R=\sum_{i=1}^{k}c_{i}\vec{e}_{i}$ of
directed edges in $\vec{E}$, its characteristic function is
$\mathbf{1}_{R}=\sum_{i=1}^{k}c_{i}\mathbf{1}_{\vec{e}_{i}}\in
L^{2}(E,\varepsilon)$, where each $\mathbf{1}_{\vec{uv}}\in
L^{2}(E,\varepsilon)$ is the vector field evaluating to
$\mathbf{v}_{\vec{uv}}$ on $uv$ and zero on every other edge. We can define
integration on $R$ by

$\int_{R}\mathbf{F}\cdot
d\varepsilon=\int_{E}\mathbf{F}\cdot\mathbf{1}_{R}d\varepsilon$

for $\mathbf{F}\in L^{2}(E,\varepsilon)$. We also identify $R\subseteq\vec{E}$
with the linear combination $\sum_{\vec{e}\in R}\vec{e}$.

A walk $C$ from $u$ to $v$ for vertices $u,v\in V$ is a sequence of directed
edges $(\vec{e}_{i})_{i=1}^{k}$ for which there exists a sequence of vertices
$(v_{i})_{i=0}^{k}$ so that $u=v_{0}$, $v=v_{k}$, and each $\vec{e_{i}}$ is a
directed edge from $v_{i-1}$ to $v_{i}$. Note for every vertex $v\in V$ there
exists the empty walk from $v$ to itself. Given a walk
$C=(\vec{e}_{i})_{i=1}^{k}$ from $u$ to $v$, the (oriented) curve
$\frac{C}{\varepsilon}$ from $u$ to $v$ is the linear combination
$\sum_{i=1}^{k}\frac{\vec{e}_{i}}{\varepsilon(e_{i})}$. A curve
$\frac{C}{\varepsilon}$ is closed if $v_{0}=v_{k}$, and a closed curve is
simple if the sequence $(v_{i})_{i=0}^{k}$ has repeated vertex $v_{0}=v_{k}$
(in particular, $k>0$), and otherwise no other repeated vertices.

Given a curve $\frac{C}{\varepsilon}$ from $u$ to $v$, its boundary
$\partial\frac{C}{\varepsilon}$ is the linear combination
$\frac{v}{\upsilon(v)}-\frac{u}{\upsilon(u)}$. For $S\subseteq V$, we let
$\nabla S\subseteq\vec{E}$ denote the set of all directed edges $\vec{uv}$
satisfying $u\not\in S$ and $v\in S$. The boundary of $S$ is the linear
combination $-\nabla S$. Note these are defined exactly so that for any curve
$\frac{C}{\varepsilon}$ and any $S\subseteq V$ that

$\partial\mathbf{1}_{\frac{C}{\varepsilon}}=1_{\partial\frac{C}{\varepsilon}}\quad\text{and}\quad\nabla
1_{S}=\mathbf{1}_{\nabla S}.$

From these definitions and Proposition 3.3, we obtain discrete analogues of
the divergence and gradient theorems of vector calculus.

######  Proposition 3.4 (Discrete divergence theorem).

Let $\mathbf{F}\in L^{2}(E,\varepsilon)$ and let $S\subseteq V$. Then

$\int_{S}-\partial\mathbf{F}d\upsilon=\int_{-\nabla S}\mathbf{F}\cdot
d\varepsilon=\sum_{\begin{subarray}{c}uv\in E\\\ u\in S,v\not\in
S\end{subarray}}\mathbf{F}(uv)\cdot\mathbf{v}_{\vec{uv}}\varepsilon(uv).$

######  Proposition 3.5 (Discrete gradient theorem).

Let $f\in L^{2}(V,\upsilon)$ and let $\frac{C}{\varepsilon}$ be a curve from
$u$ to $v$. Then

$\int_{\frac{C}{\varepsilon}}\nabla f\cdot
d\varepsilon=\int_{\partial\frac{C}{\varepsilon}}fd\upsilon=f(v)-f(u).$

In analogy with the (negative) Laplacian from vector calculus and the
(negative) Laplace-Beltrami operator on Riemannian manifolds, we will define
the Laplacian on a weighted graph to be the negative divergence of the
gradient.

######  Definition 3.6.

The weighted Laplacian $L_{(G,\upsilon,\varepsilon)}:L^{2}(V,\upsilon)\to
L^{2}(V,\upsilon)$ of a weighted multigraph $(G,\upsilon,\varepsilon)$ is

$L_{(G,\upsilon,\varepsilon)}=\partial\nabla.$

Whenever we want to think of $L_{(G,\upsilon,\varepsilon)}$ as a matrix, we
will consider the matrix of $L_{(G,\upsilon,\varepsilon)}$ in the basis of
characteristic functions of vertices. Then the matrix of
$L_{(G,\upsilon,\varepsilon)}$ can be computed to find that

$L_{(G,\upsilon,\varepsilon)}=W_{\upsilon}^{-1}L_{(G,\varepsilon)},$

where $W_{\upsilon}$ is the diagonal matrix with vertex weights as its
diagonal entries. Therefore, the combinatorial Laplacian $L_{(G,\varepsilon)}$
can be thought of as the special case where $\upsilon$ is the counting measure
$\\#_{V}$, i.e. all vertex weights are $1$, and the normalised Laplacian
$\mathcal{L}_{(G,\varepsilon)}$ can be thought of as the special case where
$\upsilon$ coincides with the measure obtained by extending the degree map
$d_{(G,\varepsilon)}:V\to\mathbb{R}_{\geq 0}$ to a measure on $V$.

######  Remark 3.7.

The same weighted Laplacian matrix has been studied in [7], as well as a
symmetric version in [12, 49]. The Laplace operator
$L_{(G,\upsilon,\varepsilon)}$ coincides with the Laplacian studied by
Friedman and Tillich [23], who also considered graphs with general vertex and
edge measures, and the operator of Horak and Jost [26], who defined a
Laplacian for weighted simplicial complexes, for graphs.

Since $\partial$ and $\nabla$ are adjoint by Proposition 3.3, we have for
$f,g\in L^{2}(V,\upsilon)$ that

$\langle L_{(G,\upsilon,\varepsilon)}f,g\rangle=\langle\nabla f,\nabla
g\rangle=\langle f,L_{(G,\upsilon,\varepsilon)}g\rangle,$

and so the weighted Laplacian is self-adjoint. Therefore,
$L_{(G,\upsilon,\varepsilon)}$ has all real eigenvalues, and there exists an
orthonormal basis for $L^{2}(V,\upsilon)$ consisting of eigenfunctions of
$L_{(G,\upsilon,\varepsilon)}$.

The weighted Laplacian Rayleigh quotient of nonzero $f\in L^{2}(V,\upsilon)$
is given by

$\frac{\langle L_{(G,\upsilon,\varepsilon)}f,f\rangle}{\langle
f,f\rangle}=\frac{\langle\nabla f,\nabla f\rangle}{\langle
f,f\rangle}=\frac{\int_{E}\lVert\nabla
f\rVert^{2}d\varepsilon}{\int_{V}|f|^{2}d\upsilon},$

which is always nonnegative, and is zero if and only if $f$ is constant on
every connected component of $G$. Thus all eigenvalues of
$L_{(G,\upsilon,\varepsilon)}$ are nonnegative, and a basis for $\ker
L_{(G,\upsilon,\varepsilon)}$ is given by the characteristic functions of the
connected components of $G$.

Because the matrix of the weighted Laplacian is given by
$L_{(G,\upsilon,\varepsilon)}=W_{\upsilon}^{-1}(D_{(G,\varepsilon)}-A_{(G,\varepsilon)}),$
we deduce the following.

######  Lemma 3.8.

Let $(G,\upsilon,\varepsilon)$ be a weighted multigraph. Then

  * (i)

$L_{(G,\upsilon,\varepsilon)\oplus(G^{\prime},\upsilon^{\prime},\varepsilon^{\prime})}=L_{(G,\upsilon,\varepsilon)}\oplus
L_{(G^{\prime},\upsilon^{\prime},\varepsilon^{\prime})}$ whenever
$(G^{\prime},\upsilon^{\prime},\varepsilon^{\prime})$ is another weighted
graph,

  * (ii)

$L_{(G-e,\upsilon,\varepsilon)}=L_{(G,\upsilon,\varepsilon)}$ whenever $e$ is
a loop,

  * (iii)

$L_{(G-e_{1}-e_{2}+e,\upsilon,\varepsilon^{\prime})}=L_{(G,\upsilon,\varepsilon)}$
whenever $e_{1},e_{2}$ and $e$ have the same endpoints, $\varepsilon^{\prime}$
inherits edge weights from $\varepsilon$ and satisfies
$\varepsilon^{\prime}(e)=\varepsilon(e_{1})+\varepsilon(e_{2})$,

  * (iv)

$L_{(G,c\upsilon,\varepsilon)}=\frac{1}{c}L_{(G,\upsilon,\varepsilon)}$
whenever $c\in\mathbb{R}_{>0}$, and

  * (v)

$L_{(G,\upsilon,c\varepsilon)}={c}L_{(G,\upsilon,\varepsilon)}$ whenever
$c\in\mathbb{R}_{>0}$.

Another operator we will be interested in is the edge Laplacian, which we
define next.

######  Definition 3.9.

The edge Laplacian $K_{(G,\upsilon,\varepsilon)}:L^{2}(E,\varepsilon)\to
L^{2}(E,\varepsilon)$ of a weighted multigraph $(G,\upsilon,\varepsilon)$ is

$K_{(G,\upsilon,\varepsilon)}=\nabla\partial.$

Note that $K_{(G,\upsilon,\varepsilon)}$ is also self-adjoint. Moreover,
because $L_{(G,\upsilon,\varepsilon)}=\partial\nabla$ and
$K_{(G,\upsilon,\varepsilon)}=\nabla\partial$, they share the same nonzero
spectrum. The edge Laplacian Rayleigh quotient of $\mathbf{F}\in
L^{2}(E,\varepsilon)$ is given by

$\frac{\langle
K_{(G,\upsilon,\varepsilon)}\mathbf{F},\mathbf{F}\rangle}{\langle\mathbf{F},\mathbf{F}\rangle}=\frac{\langle\partial\mathbf{F},\partial\mathbf{F}\rangle}{\langle\mathbf{F},\mathbf{F}\rangle}=\frac{\int_{V}|\partial\mathbf{F}|^{2}d\upsilon}{\int_{E}\lVert\mathbf{F}\rVert^{2}d\varepsilon}.$

We next define two important subspaces of $L^{2}(E,\varepsilon)$. Given a
weighted graph $(G,\upsilon,\varepsilon)$, the cycle space is
$\operatorname{Cyc}(E,\varepsilon)=\ker\partial$ and the cut space is
$\operatorname{Cut}(E,\varepsilon)=\operatorname{im}\nabla$. See [5, Section
II.3] for a treatment of these spaces in the unweighted case. Since $\partial$
and $\nabla$ are adjoint by Proposition 3.3, the cycle space and the cut space
are orthogonal complements.

Moreover, $\ker
K_{(G,\upsilon,\varepsilon)}=\operatorname{Cyc}(E,\varepsilon)$, noting that
$\ker K_{(G,\upsilon,\varepsilon)}\supseteq\operatorname{Cyc}(E,\varepsilon)$
since $K_{(G,\upsilon,\varepsilon)}=\nabla\partial$, and $\ker
K_{(G,\upsilon,\varepsilon)}\subseteq\operatorname{Cyc}(E,\varepsilon)$ since

$\langle
K_{(G,\upsilon,\varepsilon)}\mathbf{F},\mathbf{F}\rangle=\langle\partial\mathbf{F},\partial\mathbf{F}\rangle$

is zero if and only if $\mathbf{F}\in\operatorname{Cyc}(E,\varepsilon)$. Since
$K_{(G,\upsilon,\varepsilon)}$ is self-adjoint,
$\operatorname{im}K_{(G,\upsilon,\varepsilon)}$ is the orthogonal complement
of $\ker K_{(G,\upsilon,\varepsilon)}=\operatorname{Cyc}(E,\varepsilon)$, and
so
$\operatorname{im}K_{(G,\upsilon,\varepsilon)}=\operatorname{Cut}(E,\varepsilon)$.
If $G$ has $n$ vertices, $m$ edges and $k$ components, then the dimension of
$\operatorname{Cut}(E,\varepsilon)$ is $n-k$, the number of nonzero
eigenvalues of $L_{(G,\upsilon,\varepsilon)}$, and the dimension of
$\operatorname{Cyc}(E,\varepsilon)$ is $m-n+k$. The former is zero if and only
if $G$ has no nonloop edges, and the latter is zero if and only if $G$ is a
forest.

The following proposition, which is known in the unweighted case, states that
$\operatorname{Cyc}(E,\varepsilon)$ and $\operatorname{Cut}(E,\varepsilon)$
are spanned by certain vector fields known as cycles and cuts, respectively,
explaining their names. We include a proof here for completeness, which
interestingly uses deletion and contraction.

######  Proposition 3.10.

Let $(G,\upsilon,\varepsilon)$ be a weighted graph. Then

  * (i)

$\operatorname{Cyc}(E,\varepsilon)$ is equal to the subspace of
$L^{2}(E,\varepsilon)$ spanned by vector fields of the form
$\mathbf{1}_{\frac{C}{\varepsilon}}$ for simple closed curves
$\frac{C}{\varepsilon}$, and

  * (ii)

$\operatorname{Cut}(E,\varepsilon)$ is equal to the subspace of
$L^{2}(E,\varepsilon)$ spanned by vector fields of the form
$\mathbf{1}_{\nabla S}$ for vertex subsets $S\subseteq V$.

###### Proof.

We first note that every vector field of the form
$\mathbf{1}_{\frac{C}{\varepsilon}}$ for some simple closed curve
$\frac{C}{\varepsilon}$ lies in $\operatorname{Cyc}(E,\varepsilon)$, as

$\partial\mathbf{1}_{\frac{C}{\varepsilon}}=1_{\partial\frac{C}{\varepsilon}}=0.$

Additionally, every vector field of the form $\mathbf{1}_{\nabla S}$ for some
$S\subseteq V$ satisfies

$\mathbf{1}_{\nabla S}=\nabla 1_{S}\in\operatorname{Cut}(E,\varepsilon).$

It remains to prove that such vector fields span their respective subspaces.

To prove (i), we will proceed by induction on the dimension of
$\operatorname{Cyc}(E,\varepsilon)$. The base case when
$\operatorname{Cyc}(E,\varepsilon)$ has dimension zero is immediate.

For the inductive step, if $\operatorname{Cyc}(E,\varepsilon)$ has nonzero
dimension, then $G$ is not a forest. Then there exists some closed walk $C$
directed along a cycle of $G$. Let $e$ be an edge in $C$. Note
$\operatorname{Cyc}(E-e,\varepsilon)$ is naturally isomorphic to the subspace
of $\operatorname{Cyc}(E,\varepsilon)$ evaluating at $e$ to the zero vector.
Then a cycle basis for $\operatorname{Cyc}(E,\varepsilon)$ can be found by
taking a cycle basis of $\operatorname{Cyc}(E-e,\varepsilon)$, which exists by
the inductive hypothesis, together with $\mathbf{1}_{\frac{C}{\varepsilon}}$.

To prove (ii), we will similarly proceed by induction on the dimension of
$\operatorname{Cut}(E,\varepsilon)$. The base case when
$\operatorname{Cut}(E,\varepsilon)$ has dimension zero is immediate.

For the inductive step, if $\operatorname{Cut}(E,\varepsilon)$ has nonzero
dimension, then $G$ has some nonloop edge $e$. Note
$\operatorname{Cut}(E/e,\varepsilon)$, where $E/e$ is the edge set of $G/e$,
is naturally isomorphic to the subspace of $\operatorname{Cut}(E,\varepsilon)$
evaluating at $e$ to the zero vector. Moreover, cuts in
$\operatorname{Cut}(E/e,\varepsilon)$ are mapped to under this isomorphism by
the cuts in $\operatorname{Cut}(E,\varepsilon)$ not separating the endpoints
of $e$. Then a cut basis for $\operatorname{Cut}(E,\varepsilon)$ can be found
by taking a cut basis of $\operatorname{Cut}(E/e,\varepsilon)$, which exists
by the inductive hypothesis, together with $\mathbf{1}_{\nabla S}$, where
$S\subseteq V$ is chosen to contain exactly one of the two endpoints of $e$. ∎

We conclude this section with a proposition giving some equivalent
characterisations of the cut space. We will also call vector fields in
$\operatorname{Cut}(E,\varepsilon)$ conservative, noting that Proposition 3.11
is analogous to a theorem on conservative vector fields in classical vector
calculus.

######  Proposition 3.11.

Let $(G,\upsilon,\varepsilon)$ be a weighted graph and let $\mathbf{F}\in
L^{2}(E,\varepsilon)$. Then the following are equivalent:

  * (i)

$\mathbf{F}\in\operatorname{Cut}(E,\varepsilon)$.

  * (ii)

$\int_{\frac{C_{1}}{\varepsilon}}\mathbf{F}\cdot
d\varepsilon=\int_{\frac{C_{2}}{\varepsilon}}\mathbf{F}\cdot d\varepsilon$
whenever $\frac{C_{1}}{\varepsilon},\frac{C_{2}}{\varepsilon}$ are two curves
starting at the same vertex $u$ and ending at the same vertex $v$.

  * (iii)

$\int_{\frac{C}{\varepsilon}}\mathbf{F}\cdot d\varepsilon=0$ for all simple
closed curves $\frac{C}{\varepsilon}$.

###### Proof.

We will show that (i) implies (ii), (ii) implies (iii) and (iii) implies (i).

If $\mathbf{F}\in\operatorname{Cut}(E,\varepsilon)$, then $\mathbf{F}=\nabla
f$ for some $f\in L^{2}(V,\upsilon)$. If $u,v\in V$ and
$\frac{C_{1}}{\varepsilon}$ and $\frac{C_{2}}{\varepsilon}$ are two curves
starting at $u$ and ending at $v$, then by Proposition 3.5,

$\int_{\frac{C_{1}}{\varepsilon}}\mathbf{F}\cdot
d\varepsilon=f(v)-f(u)=\int_{\frac{C_{2}}{\varepsilon}}\mathbf{F}\cdot
d\varepsilon,$

and so (i) implies (ii).

If (ii) held, then for any simple closed curve $\frac{C}{\varepsilon}$ from
$v$ to $v$, we have

$\int_{\frac{C}{\varepsilon}}\mathbf{F}\cdot
d\varepsilon=\int_{0}\mathbf{F}\cdot d\varepsilon=0,$

where $0$ is used to denote the curve from $v$ to $v$ obtained from the empty
walk. So (ii) would imply (iii).

Finally, if

$\int_{\frac{C}{\varepsilon}}\mathbf{F}\cdot
d\varepsilon=\int_{E}\mathbf{F}\cdot\mathbf{1}_{\frac{C}{\varepsilon}}d\varepsilon=0$

for all simple closed curves $\frac{C}{\varepsilon}$, then $\mathbf{F}$ lies
in the orthogonal complement of $\operatorname{Cyc}(E,\varepsilon)$, recalling
by Proposition 3.10 that $\operatorname{Cyc}(E,\varepsilon)$ is spanned by the
characteristic functions of simple closed curves. Since
$\operatorname{Cut}(E,\varepsilon)$ is the orthogonal complement of
$\operatorname{Cyc}(E,\varepsilon)$, it follows that (iii) implies (i). ∎

##  4\. Deletion-contraction from weighted spanning forests

In this section we will prove a deletion-contraction relation for the weighted
Laplacian characteristic polynomial. It will be helpful to consider the
weighted Laplacian characteristic polynomial scaled by the product of vertex
weights.

######  Definition 4.1.

For a weighted multigraph $(G,\upsilon,\varepsilon)$, define the polynomial

$P_{(G,\upsilon,\varepsilon)}(t)=\det(tW_{\upsilon}-L_{(G,\varepsilon)})=\left(\prod_{v\in
V}\upsilon(v)\right)\det(tI-L_{(G,\upsilon,\varepsilon)}).$

We will give a combinatorial interpretation for the coefficients of
$P_{(G,\upsilon,\varepsilon)}(t)$ in terms of the spanning forests of $G$.
Given a spanning forest $F$ of $G$, define its weight to be

$w(F)=\prod_{T\in F}\left(\sum_{v\in V(T)}\upsilon(v)\prod_{e\in
E(T)}\varepsilon(e)\right),$

where the product is over all connected components $T$ of $F$. Then the
following theorem holds.

######  Theorem 4.2 (Weighted matrix-forest theorem).

Let $(G,\upsilon,\varepsilon)$ be a weighted multigraph on $n$ vertices with

$P_{(G,\upsilon,\varepsilon)}(t)=\sum_{k=1}^{n}(-1)^{n-k}c_{k}t^{k}.$

Then

$c_{k}=\sum_{F}w(F),$

where the sum is over all $k$-component spanning forests $F$.

###### Proof.

It is known that the coefficient of $t^{k}$ in the characteristic polynomial
of $L_{(G,\upsilon,\varepsilon)}$ multiplied by $(-1)^{n-k}$ is the sum of all
$(n-k)\times(n-k)$ principal minors of $L_{(G,\upsilon,\varepsilon)}$, e.g. by
considering the Laplace expansion of $\det(tI-L_{(G,\upsilon,\varepsilon)})$.

For $S\subseteq V$ of cardinality $k$, the $(n-k)\times(n-k)$ principal
submatrix of $L_{(G,\upsilon,\varepsilon)}$ obtained by deleting the rows and
columns indexed by $S$ is equal to the corresponding principal submatrix of
$L_{(G,\varepsilon)}$ with each row corresponding to $v\in S^{c}$ divided by
$\upsilon(v)$. It follows then that the associated $(n-k)\times(n-k)$
principal minor of $L_{(G,\upsilon,\varepsilon)}$ is equal to the
corresponding principal minor of $L_{(G,\varepsilon)}$ divided by $\prod_{v\in
S^{c}}\upsilon(v)$.

Therefore,

$c_{k}=\left(\prod_{v\in
V}\upsilon(v)\right)\sum_{\begin{subarray}{c}S\subseteq V\\\
|S|=k\end{subarray}}\frac{\det L_{(G,\varepsilon)}^{\hat{S}}}{\prod_{v\in
S^{c}}\upsilon(v)}=\sum_{\begin{subarray}{c}S\subseteq V\\\
|S|=k\end{subarray}}\left(\prod_{v\in S}\upsilon(v)\right)\det
L_{(G,\varepsilon)}^{\hat{S}}.$

By Theorem 2.2, the principal minors matrix-tree theorem, this is equal to the
sum over all $k$-rooted spanning forests of $G$ of the product of root weights
and edge weights.

For a $k$-component spanning forest $F$ of $G$, a choice of roots is made by
choosing a single vertex $v$ of each component $T$ of $G$. The sum over all
choices of roots for $F$ of the product of root weights is equal to
$\prod_{T\in F}\sum_{v\in V(T)}\upsilon(v)$.

Putting this all together, we find that

$c_{k}=\sum_{F}\left(\left(\prod_{T\in F}\sum_{v\in
V(T)}\upsilon(v)\right)\prod_{e\in E(F)}\varepsilon(e)\right)=\sum_{F}w(F),$

where the sum is over all $k$-component spanning forests $F$ of $G$, as
desired. ∎

Various polynomials and invariants associated with a graph satisfy a
recurrence involving the deletion and contraction of an edge. For example, the
number of spanning trees $\tau(G)$ of a graph $G$ satisfies for every nonloop
edge $e$

$\tau(G)=\tau(G-e)+\tau(G/e),$

where $G-e$ is the graph obtained from $G$ by removing the edge $e$, and $G/e$
is the graph obtained from $G$ by removing $e$ and formally identifying its
endpoints as a single vertex in $G/e$. The deletion-contraction formula for
$\tau(G)$ follows from the existence of a bijection between the spanning trees
of $G$ not containing $e$ and the spanning trees of $G-e$, together with a
bijection between the spanning trees of $G$ containing $e$ and the spanning
trees of $G/e$.

The combinatorial Laplacian and normalised Laplacian characteristic
polynomials are not known to satisfy a deletion-contraction recurrence. The
introduction of vertex weights, however, gives a deletion-contraction
recurrence for the weighted Laplacian characteristic polynomial. If $\upsilon$
is a weight function on the vertices of $G$, then $\upsilon/e$ is the weight
function on the vertices of $G/e$ where the weight of the new vertex obtained
by contracting $e$ is equal to the sum of the weights of its constituents
under $\upsilon$, and the weights of the other vertices are given by their
original weights under $\upsilon$.

######  Example 4.3.

Let $(G,\upsilon,\varepsilon)$ the the weighted graph depicted on the left,
and let $e$ be the edge of weight $3$ in $(G,\upsilon,\varepsilon)$. Then
$(G/e,\upsilon/e,\varepsilon)$, obtained from $(G,\upsilon,\varepsilon)$ by
contracting the edge $e$, is the weighted graph depicted on the right. Note
that the endpoints of $e$, which had weights $2$ and $1$ in
$(G,\upsilon,\varepsilon)$, are replaced by a single vertex of weight $2+1=3$
in $(G/e,\upsilon/e,\varepsilon)$.

3212$1$$3$$1$$4$$(G,\upsilon,\varepsilon)$323$1$$1$$4$$(G/e,\upsilon/e,\varepsilon)$

With these definitions in mind, we will show the following.

######  Theorem 4.4.

Let $(G,\upsilon,\varepsilon)$ be a weighted multigraph and let $e$ be a
nonloop edge. Then

$P_{(G,\upsilon,\varepsilon)}(t)=P_{(G-e,\upsilon,\varepsilon)}(t)-\varepsilon(e)P_{(G/e,\upsilon/e,\varepsilon)}(t).$

###### Proof.

We first note that there exists a bijection between the $k$-component spanning
forests of $G$ not containing $e$ and the $k$-component spanning forests of
$G-e$, by sending a spanning forest $F$ to its image in $G-e$. Since vertex
weights and edge weights are preserved, this bijection preserves the weight of
each spanning forest.

Additionally, since $e$ is not a loop, there is a bijection between the
$k$-component spanning forests of $G$ containing $e$ and the $k$-component
spanning forests of $G/e$, by sending a spanning forest $F$ to its contraction
$F/e$. The vertex and edge weights of each component of $F$ not containing $e$
are preserved.

As for the component $T$ of $F$ containing $e$, its image $T/e$ under
contraction has vertex weights preserved, except the image of the endpoints of
$e$ are replaced with a single vertex whose weight is the sum of the weights
of the pair of endpoints. All edges of $T$ except $e$ appear in $T/e$ with
edge weights preserved. Therefore, we have

$\sum_{v\in V(T)}\upsilon(v)\prod_{e^{\prime}\in
E(T)}\varepsilon(e^{\prime})=\varepsilon(e)\left(\sum_{v\in
V(T/e)}\upsilon(v)\prod_{e^{\prime}\in E(T/e)}\varepsilon(e^{\prime})\right).$

It follows then that for all $k$-component spanning forests $F$ of $G$
containing $e$,

$w(F)=\varepsilon(e)w(F/e).$

Let $G$ have $n$ vertices, and let
$(-1)^{n-k}c_{k}^{(G,\upsilon,\varepsilon)}$,
$(-1)^{n-k}c_{k}^{(G-e,\upsilon,\varepsilon)}$ and
$(-1)^{n-k-1}c_{k}^{(G/e,\upsilon/e,\varepsilon)}$ denote the coefficients of
$t^{k}$ in $P_{(G,\upsilon,\varepsilon)}(t)$,
$P_{(G-e,\upsilon,\varepsilon)}(t)$ and $P_{(G/e,\upsilon/e,\varepsilon)}(t)$,
respectively. From the bijections constructed together with Theorem 4.2, it
follows that

$c_{k}^{(G,\upsilon,\varepsilon)}=c_{k}^{(G-e,\upsilon,\varepsilon)}+\varepsilon(e)c_{k}^{(G/e,\upsilon/e,\varepsilon)}.$

Since this holds for all $k$, we conclude that

$P_{(G,\upsilon,\varepsilon)}(t)=P_{(G-e,\upsilon,\varepsilon)}(t)-\varepsilon(e)P_{(G/e,\upsilon/e,\varepsilon)}(t).$

∎

##  5\. Interlacing theorems

In this section, we will prove interlacing theorems relating to deletion and
contraction for weighted graphs, and then apply these to obtain interlacing
results for combinatorial and normalised Laplacian eigenvalues.

We begin by proving a lemma relating the weighted Laplacian eigenvalues of a
weighted graph $(G,\upsilon,\varepsilon)$ and those of
$(G-e,\upsilon,\varepsilon)$. We follow the proof of Grone, Merris and Sunder
in [24, Theorem 4.1], which is the special case when the graph is unweighted.

######  Lemma 5.1.

Let $(G,\upsilon,\varepsilon)$ be a weighted multigraph and let $e$ be an
edge. Let $\lambda_{1}\leq\dots\leq\lambda_{n}$ and
$\mu_{1}\leq\dots\leq\mu_{n}$ denote the weighted Laplacian eigenvalues of
$(G,\upsilon,\varepsilon)$ and $(G-e,\upsilon,\varepsilon)$, respectively.
Then

$\mu_{1}\leq\lambda_{1}\leq\dots\leq\mu_{n}\leq\lambda_{n}.$

###### Proof.

It suffices to prove the inequalities for the nonzero eigenvalues, so we will
prove the interlacing for the eigenvalues of the edge Laplacian.

Let $\iota:L^{2}(E-e,\varepsilon)\to L^{2}(E,\varepsilon)$ be the isometric
natural inclusion, where $E-e$ denotes the edge set of $G-e$. Then

$K_{(G-e,\upsilon,\varepsilon)}=\iota^{*}K_{(G,\upsilon,\varepsilon)}\iota,$

since the matrix of $K_{(G,\upsilon,\varepsilon)}$ with respect to the
orthogonal basis of vector fields of the form $\mathbf{1}_{\vec{uv}}$ (after
arbitrarily orienting each edge) has the matrix of
$K_{(G-e,\upsilon,\varepsilon)}$ as a principal submatrix.

By Theorem 2.6, the eigenvalues of $K_{(G,\upsilon,\varepsilon)}$ interlace
the eigenvalues of $K_{(G-e,\upsilon,\varepsilon)}$. Since
$K_{(G,\upsilon,\varepsilon)}$ has one more eigenvalue than
$K_{(G-e,\upsilon,\varepsilon)}$, we conclude that

$\mu_{1}\leq\lambda_{1}\leq\dots\leq\mu_{n}\leq\lambda_{n}.$

∎

######  Remark 5.2.

By Lemma 3.8, the interlacing result in Lemma 5.1 also applies whenever we
reduce the weight of an edge, even though its proof required that an edge be
deleted.

We will prove many interlacing results in this section. However, beyond the
proof of Lemma 5.1, we will not require any applications of Lemma 2.5 or
Theorem 2.6. We will also not require the use of Rayleigh quotients or any
computations.

The following lemma on interlacing roots of real-rooted polynomials will help
us prove an interlacing theorem relating the eigenvalues of a weighted graph
and the eigenvalues of the weighted graphs obtained by deleting and
contracting an edge.

######  Lemma 5.3.

Let

$\mu_{1}\leq\lambda_{1}\leq\dots\leq\mu_{n}\leq\lambda_{n}$

be real numbers and suppose

$f(t)=\prod_{i=1}^{n}(t-\lambda_{i})-\prod_{i=1}^{n}(t-\mu_{i})$

is nonzero. Then $f(t)$ has $n-1$ real roots $\nu_{1}\leq\dots\leq\nu_{n-1}$
satisfying

$\mu_{1}\leq\lambda_{1}\leq\nu_{1}\leq\cdots\leq\nu_{n-1}\leq\mu_{n}\leq\lambda_{n}.$

###### Proof.

We will proceed by induction.

For the base case, suppose

$\mu_{1}<\lambda_{1}<\dots<\mu_{n}<\lambda_{n}.$

Note

$\operatorname{sgn}(f(\lambda_{j}))=-\prod_{i=1}^{n}\operatorname{sgn}(\lambda_{j}-\mu_{i})=(-1)^{n-j+1}$

and similarly

$\operatorname{sgn}(f(\mu_{j}))=\prod_{i=1}^{n}\operatorname{sgn}(\mu_{j}-\lambda_{i})=(-1)^{n-j+1}.$

By the intermediate value theorem, $f(t)$ has a real root in each of the open
intervals $(\lambda_{j},\mu_{j+1})$. Since nonzero $f(t)$ has degree at most
$n-1$ and since there are $n-1$ disjoint intervals of the form
$(\lambda_{j},\mu_{j+1})$, it follows that $f(t)$ has $n-1$ real roots
$\nu_{1}\leq\dots\leq\nu_{n-1}$ satisfying

$\mu_{1}<\lambda_{1}<\nu_{1}<\dots<\nu_{n-1}<\mu_{n}<\lambda_{n}.$

For the inductive step, suppose there is some $\mu_{j}=\lambda_{j}$ or
$\lambda_{j}=\mu_{j+1}$. Let $\xi$ be the shared value, and denote the
remaining numbers by

$\mu_{1}^{\prime}\leq\lambda_{1}^{\prime}\leq\dots\leq\mu_{n-1}^{\prime}\leq\lambda_{n-1}^{\prime}.$

Since $f(t)$ is a nonzero polynomial with $\xi$ as a root,
$\frac{f(t)}{t-\xi}$ is a nonzero polynomial. Applying the inductive
hypothesis to

$\frac{f(t)}{t-\xi}=\prod_{i=1}^{n-1}(t-\lambda_{i}^{\prime})-\prod_{i=1}^{n-1}(t-\mu_{i}^{\prime}),$

it follows that $\frac{f(t)}{t-\xi}$ has $n-2$ roots
$\nu_{1}^{\prime}\leq\dots\leq\nu_{n-2}^{\prime}$ satisfying

$\mu_{1}^{\prime}\leq\lambda_{1}^{\prime}\leq\nu_{1}^{\prime}\leq\dots\leq\nu_{n-2}^{\prime}\leq\mu_{n-1}^{\prime}\leq\lambda_{n-1}^{\prime}.$

Inserting $\xi\leq\xi\leq\xi$ into the above chain of inequalities completes
the proof of the inductive step. ∎

We are now ready to prove the following theorem.

######  Theorem 5.4.

Let $(G,\upsilon,\varepsilon)$ be a weighted multigraph and let $e$ be a
nonloop edge. Let $\lambda_{1}\leq\dots\leq\lambda_{n}$,
$\mu_{1}\leq\dots\leq\mu_{n}$, and $\nu_{1}\leq\dots\leq\nu_{n-1}$ denote the
weighted Laplacian eigenvalues of $(G,\upsilon,\varepsilon)$,
$(G-e,\upsilon,\varepsilon)$ and $(G/e,\upsilon/e,\varepsilon)$, respectively.
Then

$\mu_{1}\leq\lambda_{1}\leq\nu_{1}\leq\dots\leq\nu_{n-1}\leq\mu_{n}\leq\lambda_{n}.$

###### Proof.

By Theorem 4.4,

$P_{(G,\upsilon,\varepsilon)}(t)=P_{(G-e,\upsilon,\varepsilon)}(t)-\varepsilon(e)P_{(G/e,\upsilon/e,\varepsilon)}(t).$

Note that the Laplacian eigenvalues $\nu_{1}\leq\dots\leq\nu_{n-1}$ of
$(G/e,\upsilon/e,\varepsilon)$ are exactly the roots of the nonzero polynomial

$-\frac{\varepsilon(e)P_{(G/e,\upsilon/e,\varepsilon)}(t)}{\prod_{v\in
V}\upsilon(v)}=\prod_{i=1}^{n}(t-\lambda_{i})-\prod_{i=1}^{n}(t-\mu_{i}).$

By Lemma 5.1, the Laplacian eigenvalues of $(G,\upsilon,\varepsilon)$ and
$(G-e,\upsilon,\varepsilon)$ satisfy

$\mu_{1}\leq\lambda_{1}\leq\dots\leq\mu_{n}\leq\lambda_{n}.$

Applying Lemma 5.3, we conclude that

$\mu_{1}\leq\lambda_{1}\leq\nu_{1}\leq\dots\leq\nu_{n-1}\leq\mu_{n}\leq\lambda_{n}.$

∎

Note $(G/e,\upsilon/e,\varepsilon)=(G-e,\upsilon,\varepsilon)/\sim$, where
$\sim$ is the equivalence relation with the endpoints of $e$ in the same
equivalence class and no other relations. Thus the interlacing between the
weighted Laplacian eigenvalues of $(G-e,\upsilon,\varepsilon)$ and
$(G/e,\upsilon/e,\varepsilon)$ in Theorem 5.4 really describes an interlacing
result between the weighted Laplacian eigenvalues of a weighted graph and its
quotient weighted graph under an equivalence relation with only two distinct
vertices related under $\sim$. Repeated applications of this interlacing
theorem then immediately gives us the following.

######  Corollary 5.5.

Let $(G,\upsilon,\varepsilon)$ be a weighted multigraph and let $\sim$ be an
equivalence relation on its vertices. Let
$\lambda_{1}\leq\dots\leq\lambda_{n}$ and
$\mu_{1}\leq\dots\leq\dots\leq\mu_{n-k}$ denote the weighted Laplacian
eigenvalues of $(G,\upsilon,\varepsilon)$ and $(G,\upsilon,\varepsilon)/\sim$,
respectively. Then

$\lambda_{i}\leq\mu_{i}\leq\lambda_{i+k}$

for all $1\leq i\leq n-k$.

######  Remark 5.6.

Corollary 5.5 could have alternatively been proved by an application of
Theorem 2.6, the Cauchy interlacing theorem, with the isometry
$\iota:L^{2}(V/\sim,\upsilon)\to L^{2}(V,\upsilon)$ sending the characteristic
function of a vertex in $V/\sim$ to the characteristic function of the
corresponding equivalence class of vertices in $V$.

######  Corollary 5.7.

Let $(G,\upsilon,\varepsilon)$ be a weighted multigraph and let
$\upsilon^{\prime}:V\to\mathbb{R}_{>0}$ be obtained from $\upsilon$ by
decreasing the weight of a single vertex. Let
$\lambda_{1}\leq\dots\leq\lambda_{n}$ and $\mu_{1}\leq\dots\leq\mu_{n}$ denote
the weighted Laplacian eigenvalues of $(G,\upsilon,\varepsilon)$ and
$(G,\upsilon^{\prime},\varepsilon)$, respectively. Then

$\lambda_{1}\leq\mu_{1}\leq\dots\leq\lambda_{n}\leq\mu_{n}.$

###### Proof.

Let $v\in V$ be the vertex satisfying $\upsilon^{\prime}(v)<\upsilon(v)$.

Consider the weighted graph with a single vertex of weight
$\upsilon(v)-\upsilon^{\prime}(v)$ and no edges, which has a zero as its sole
weighted Laplacian eigenvalue. The disjoint union of this weighted graph and
$(G,\upsilon^{\prime},\varepsilon)$ has $(G,\upsilon,\varepsilon)$ as a
quotient weighted graph, under the equivalence relation $\sim$ relating the
isolated vertex and $v$.

By Corollary 5.5, the weighted Laplacian eigenvalues of the disjoint union
interlace those of $(G,\upsilon,\varepsilon)$. By Lemma 3.8(i), the weighted
Laplacian eigenvalues of the disjoint union are exactly the weighted Laplacian
eigenvalues of $(G,\upsilon^{\prime},\varepsilon)$ together with an additional
zero. We conclude that

$\lambda_{1}\leq\mu_{1}\leq\dots\leq\lambda_{n}\leq\mu_{n}.$

∎

To state some of the results in this section, we will let the statement

$\lambda_{i-a}\leq\mu_{i}\leq\lambda_{i+b}$

be shorthand to mean that both $\lambda_{i-a}\leq\mu_{i}$ if $\lambda_{i-a}$
is defined and $\mu_{i}\leq\lambda_{i+b}$ if $\lambda_{i+b}$ is defined.

Grone, Merris and Sunder also studied the effect of edge contraction on
Laplacian eigenvalues. Specifically, they gave an interlacing result for the
combinatorial Laplacian eigenvalues of unweighted simple graphs before and
after edge contraction. The following result recovers their [24, Theorem 4.9]
as a special case.

######  Corollary 5.8.

Let $(G,\varepsilon)$ be an edge-weighted multigraph and let $\sim$ be an
equivalence relation on its vertices. Let
$\lambda_{1}\leq\dots\leq\lambda_{n}$ and $\mu_{1}\leq\dots\leq\mu_{n-k}$
denote the combinatorial Laplacian eigenvalues of $(G,\varepsilon)$ and
$(G/\sim,\varepsilon)$, respectively. Then

$\lambda_{i}\leq\mu_{i}\leq\lambda_{i+q+k}$

for all $1\leq i\leq n-k$, where $q$ is the number of equivalence classes of
$\sim$ with more than one element.

###### Proof.

Let $\mu_{1}^{\prime}\leq\dots\leq\mu_{n-k}^{\prime}$ denote the weighted
Laplacian eigenvalues of $(G,\\#_{V},\varepsilon)/\sim$. By Corollary 5.5, we
have

$\lambda_{i}\leq\mu_{i}^{\prime}\leq\lambda_{i+k}$

for all $1\leq i\leq n-k$. After applying Corollary 5.7 multiple times in
succession, once for each of the $q$ vertices $G/\sim$ with weight $>1$ under
$\\#_{V}/\sim$, it also follows that

$\mu_{i+q}\leq\mu_{i+q}^{\prime}\leq\lambda_{i+q+k}$

for all $1\leq i\leq n-q-k$, as desired. ∎

We can also deduce from our work Butler’s [11, Theorem 3.2], which improved a
result of Chen, Davis, Hall, Li, Patel and Stewart in [14, Theorem 2.7]
relating normalised Laplacian eigenvalues before and after identifying two
vertices of a graph.

######  Corollary 5.9.

[11, Theorem 3.2] Let $(G,\varepsilon)$ be an edge-weighted multigraph with no
isolated vertices and let $\sim$ be an equivalence relation on its vertices.
Let $\lambda_{1}\leq\dots\leq\lambda_{n}$ and $\mu_{1}\leq\dots\leq\mu_{n-k}$
denote the normalised Laplacian eigenvalues of $(G,\varepsilon)$ and
$(G/\sim,\varepsilon)$, respectively. Then

$\lambda_{i}\leq\mu_{i}\leq\lambda_{i+k}$

for all $1\leq i\leq n-k$.

###### Proof.

Recall that the normalised Laplacian eigenvalues of $(G,\varepsilon)$ are
exactly the weighted Laplacian eigenvalues of
$(G,d_{(G,\varepsilon)},\varepsilon)$ and, similarly, the normalised Laplacian
eigenvalues of $(G/\sim,\varepsilon)$ are the weighted Laplacian eigenvalues
of $(G/\sim,d_{(G/\sim,\varepsilon)},\varepsilon)$.

The result then follows by applying Corollary 5.5 to the weighted graph
$(G,d_{(G,\varepsilon)},\varepsilon)$ and the equivalence relation $\sim$,
while noting that the vertex measure $d_{(G,\varepsilon)}/\sim$ coincides with
the measure $d_{(G/\sim,\varepsilon)}$. ∎

Given two graphs $G=(V,E)$ and $G^{\prime}=(V^{\prime},E^{\prime})$, we define
$G+G^{\prime}$ to be the graph $(V\cup V^{\prime},E\cup E^{\prime})$. Note we
do not require $V$ and $V^{\prime}$ are disjoint, nor $E$ and $E^{\prime}$.
The merge of weighted graphs $(G,\upsilon,\varepsilon)$ and
$(G^{\prime},\upsilon^{\prime},\varepsilon^{\prime})$ is the weighted graph
$(G+G^{\prime},\upsilon+\upsilon^{\prime},\varepsilon+\varepsilon^{\prime})$,
where if a weight function is not defined on a vertex or an edge, we take it
to be zero in the sum.

Our next theorem describes an interlacing relationship between the weighted
Laplacian eigenvalues of $(G,\upsilon,\varepsilon)$ and
$(G+G^{\prime},\upsilon+\upsilon^{\prime},\varepsilon+\varepsilon^{\prime})$.
We will assume without loss of generality that $E$ and $E^{\prime}$ are
disjoint, as doing so does not change the weighted Laplacian eigenvalues of
$(G+G^{\prime},\upsilon+\upsilon^{\prime},\varepsilon+\varepsilon^{\prime})$
by Lemma 3.8(iii).

######  Theorem 5.10.

Let $(G,\upsilon,\varepsilon)$ and
$(G^{\prime},\upsilon^{\prime},\varepsilon^{\prime})$ be weighted multigraphs.
Let $\lambda_{1}\leq\dots\leq\lambda_{n}$ and $\mu_{1}\leq\dots\leq\mu_{n+k}$
denote the weighted Laplacian eigenvalues of $(G,\upsilon,\varepsilon)$ and
$(G+G^{\prime},\upsilon+\upsilon^{\prime},\varepsilon+\varepsilon^{\prime})$,
respectively. Then

$\mu_{i-s+c+k}\leq\lambda_{i}\leq\mu_{i+s-b}$

for all $1\leq i\leq n$, where $G^{\prime}$ has $s$ vertices and $c$
components, and $b$ weighted Laplacian eigenvalues of
$(G^{\prime},\upsilon^{\prime},\varepsilon^{\prime})$ are $\geq\lambda_{n}$.

###### Proof.

Note
$(G+G^{\prime},\upsilon+\upsilon^{\prime},\varepsilon+\varepsilon^{\prime})$
is the quotient weighted graph of
$(G,\upsilon,\varepsilon)\oplus(G^{\prime},\upsilon^{\prime},\varepsilon^{\prime})$
over $\sim$, where $\sim$ identifies the shared vertices in $V$ and
$V^{\prime}$. By Lemma 3.8(i), the weighted Laplacian eigenvalues of
$(G,\upsilon,\varepsilon)\oplus(G^{\prime},\upsilon^{\prime},\varepsilon^{\prime})$
are exactly the disjoint union of those of $(G,\upsilon,\varepsilon)$ and
$(G^{\prime},\upsilon^{\prime},\varepsilon^{\prime})$.

By Corollary 5.5, each $\mu_{i}$ is greater than or equal to the $i$th
smallest eigenvalue among the weighted Laplacian eigenvalues of
$(G,\upsilon,\varepsilon)$ and
$(G^{\prime},\upsilon^{\prime},\varepsilon^{\prime})$. When $1\leq i\leq
n+s-b$, this is equal to the $i$th smallest eigenvalue among the weighted
Laplacian eigenvalues of $(G,\upsilon,\varepsilon)$ and the $s-b$ of those of
$(G^{\prime},\upsilon^{\prime},\varepsilon^{\prime})$, after excluding the $b$
weighted Laplacian eigenvalues that are $\geq\lambda_{n}$. A lower bound for
this when $1+s-b\leq i\leq n+s-b$ is $\lambda_{i-s+b}$. Therefore, we have

$\lambda_{i}\leq\mu_{i+s-b}$

for all $1\leq i\leq\min\\{n,n-s+b+k\\}$.

Similarly, by Corollary 5.5, each $\mu_{n-i+k}$ is less than or equal to the
$i$th largest eigenvalue among the weighted Laplacian eigenvalues of
$(G,\upsilon,\varepsilon)$ and
$(G^{\prime},\upsilon^{\prime},\varepsilon^{\prime})$. Since
$(G^{\prime},\upsilon^{\prime},\varepsilon^{\prime})$ has $c$ zero
eigenvalues, this is equal to the $i$th largest eigenvalue among the weighted
Laplacian eigenvalues of $(G,\upsilon,\varepsilon)$ and the $s-c$ nonzero
weighted Laplacian eigenvalues of
$(G^{\prime},\upsilon^{\prime},\varepsilon^{\prime})$ when $1\leq i\leq
n+s-c$. This is upper bounded by $\lambda_{n-i+s-c}$ when $1+s-c\leq i\leq
n+s-c$. Therefore,

$\mu_{i-s+c+k}\leq\lambda_{i}$

for all $\max\\{1,1+s-c-k\\}\leq i\leq n$, completing the proof of the
theorem. ∎

We next prove an interlacing result on weighted Laplacian eigenvalues relating
to subgraph deletion.

######  Corollary 5.11.

Let $(G,\upsilon,\varepsilon)$ be a weighted multigraph. Let $R\subseteq E$
and let $S\subseteq V$ be a subset of the isolated vertices of $G-R$. Let
$\lambda_{1}\leq\dots\leq\lambda_{n}$ and $\mu_{1}\leq\dots\leq\mu_{n-k}$
denote the weighted Laplacian eigenvalues of $(G,\upsilon,\varepsilon)$ and
$(G-R-S,\upsilon,\varepsilon)$, respectively. Then

$\lambda_{i-s+c+k}\leq\mu_{i}\leq\lambda_{i+k}$

for all $1\leq i\leq n-k$, where $G[R]$ has $s$ vertices and $c$ components.

###### Proof.

We will assume without loss of generality that $S=\emptyset$. This is
sufficient to prove the general case, since the weighted Laplacian eigenvalues
of $(G-R,\upsilon,\varepsilon)$ are exactly those of
$(G-R-S,\upsilon,\varepsilon)$ together with $k$ additional zero eigenvalues.

By applying Lemma 5.1 to each edge in $R$, we find that

$\mu_{i}\leq\lambda_{i}$

for all $1\leq i\leq n$. This proves one direction of the interlacing
inequalities. The other direction requires a little more work.

For $0<\delta<\min_{v\in V(G[R])}\upsilon(v)$, we will define the measure
$\upsilon_{\delta}$ on the vertices of $G[R]$ to send each vertex to $\delta$.
Then, $(G,\upsilon,\varepsilon)$ can be seen as the merge of
$(G-R,\upsilon-\upsilon_{\delta},\varepsilon)$ and
$(G[R],\upsilon_{\delta},\varepsilon)$. Let
$\mu_{1}^{\delta}\leq\dots\leq\mu_{n}^{\delta}$ denote the weighted Laplacian
eigenvalues of $(G-R,\upsilon-\upsilon_{\delta},\varepsilon)$. By Theorem
5.10, each

$\lambda_{i-s+c}\leq\mu_{i}^{\delta}$

for all $1+s-c\leq i\leq n$. Since

$\lim_{\delta\to
0}L_{(G-R,\upsilon-\upsilon_{\delta},\varepsilon)}=L_{(G-R,\upsilon,\varepsilon)}$

as matrices, it also follows that

$\lambda_{i-s+c}\leq\lim_{\delta\to 0}\mu_{i}^{\delta}=\mu_{i}$

for all $1+s-c\leq i\leq n$, completing the proof of the second direction. ∎

######  Remark 5.12.

Because vertex weights are unmodified, the statement of Corollary 5.11 also
applies directly to the combinatorial Laplacian eigenvalues of edge-weighted
multigraphs.

Butler proved an interlacing theorem on the normalised Laplacian eigenvalues
of an edge-weighted graph before and after deleting a subgraph in [11, Theorem
1.2], which generalised a version for edge deletion by Chen, Davis, Hall, Li,
Patel and Stewart in [14, Theorem 2.3]. Our techniques recover Butler’s result
and improves it whenever one or more vertices are removed in deleting the
subgraph.

######  Corollary 5.13.

Let $(G,\varepsilon)$ be an edge-weighted multigraph with no isolated
vertices. Let $R\subseteq E$ and let $S\subseteq V$ consist of all isolated
vertices of $G-R$. Let $\lambda_{1}\leq\dots\leq\lambda_{n}$ and
$\mu_{1}\leq\dots\leq\mu_{n-k}$ denote the normalised Laplacian eigenvalues of
$(G,\varepsilon)$ and $(G-R-S,\varepsilon)$, respectively. Then

$\lambda_{i-s+c+k}\leq\mu_{i}\leq\lambda_{i+s-b}$

for all $1\leq i\leq n-k$, where $G[R]$ has $s$ vertices and $c$ components,
$b$ of which are bipartite.

###### Proof.

Note that $(G,d_{(G,\varepsilon)},\varepsilon)$ is the merge of
$(G-R-S,d_{(G-R-S,\varepsilon)},\varepsilon)$ and
$(G[R],d_{(G[R],\varepsilon)},\varepsilon)$. It is also known that the
normalised Laplacian eigenvalues of an edge-weighted multigraph all lie in the
interval $[0,2]$, and the multiplicity of $2$ is equal to the number of
bipartite components. Therefore, at least $b$ normalised Laplacian eigenvalues
of $(G[R],\varepsilon)$ are $\geq\mu_{n-k}$. By Theorem 5.10,

$\lambda_{i-s+c+k}\leq\mu_{i}\leq\lambda_{i+s-b}$

for all $1\leq i\leq n-k$. ∎

##  6\. Addition-reduction from equivalent electrical networks

In Section 3, we defined conservative vector fields on weighted graphs.
Classical conservative vector fields often arise naturally from physical
forces satisfying conservation of energy. One instance of conservative vector
fields on graphs can be found in Brooks, Smith, Stone and Tutte’s work on
square tilings of rectangles, in which they show such tilings can be
associated to electrical circuits [8, Section 1]. Each electrical circuit may
be realised as a conservative vector field on a graph. We will give a version
of their result for rectangular tilings of rectangles.

All rectangles in this paper are assumed to exist in the plane and have
positive dimensions, with two sides parallel to the horizontal axis, and two
sides parallel to the vertical axis. Hence, the height $h(r)$ and width $w(r)$
of a rectangle $r$ are well-defined.

A rectangular tiling of a rectangle $R$ is a subdivision of $R$ into finitely
many interior-disjoint rectangles $r$. Given a rectangular tiling, we can
associate an edge-weighted graph $(G,\varepsilon)$, constructed as follows.
The vertex set of $G$ consists of all horizontal lines in the plane which
cover some horizontal side of a rectangle in the tiling, and the edge set of
$G$ consists of the rectangles used in the subdivision. Each edge connects the
vertices corresponding to the top and bottom sides of the rectangle. The edge
weight of a rectangle $r$ is given by

$\varepsilon(r)=\frac{w(r)}{h(r)}.$

Moreover, there is a natural vector field $\mathbf{F}$ on $(G,\varepsilon)$
associated with the tiling, where for each rectangle $r=uv$ in the subdivision
with bottom side corresponding to vertex $u$ and top side corresponding to
vertex $v$, we have

$\mathbf{F}(r)=h(r)\mathbf{v}_{\vec{u}v}.$

######  Example 6.1.

Consider the rectangular tiling of the rectangle $R$ of height $3$ and width
$6$, embedded in the plane, as depicted on the left. It is associated with the
edge-weighted graph $(G,\varepsilon)$ depicted in the centre and the vector
field $\mathbf{F}\in L^{2}(E,\varepsilon)$ depicted on the right.

$R$$\frac{2}{3}$$1$$\frac{1}{2}$$\frac{3}{2}$$3$$(G,\varepsilon)$$3$$1$$2$$2$$1$$\mathbf{F}$

######  Lemma 6.2.

Let $(G,\varepsilon)$ and $\mathbf{F}$ be the edge-weighted multigraph and
vector field, respectively, associated with a rectangular tiling of a
rectangle $R$. Let $a$ and $b$ denote the vertices associated with the bottom
and top sides of $R$, respectively, and let $\upsilon:V\to\mathbb{R}_{>0}$ be
arbitrary. Then $\mathbf{F}$ satisfies Kirchhoff’s laws with poles $a,b$. That
is,

  1. (i)

$\partial\mathbf{F}(v)=0$ for all $v\in\\{a,b\\}^{c}$, and

  2. (ii)

$\int_{\frac{C}{\varepsilon}}\mathbf{F}\cdot d\varepsilon=0$ for all simple
closed curves $\frac{C}{\varepsilon}$.

###### Proof.

For $v\in V$, the contribution of a rectangle $r$ with top side on $v$ to
$\partial\mathbf{F}(v)$ is

$\frac{1}{\upsilon(v)}h(r)\frac{w(r)}{h(r)}=\frac{1}{\upsilon(v)}w(r),$

which is the width of the rectangle $r$ divided by the weight of $v$. When
$v\neq a$, summing this over all rectangles with top side on $v$ gives the
total length of the horizontal segments on $v$, divided by $\upsilon(v)$.
Similarly, the contribution of a rectangle $r$ with bottom side on $v$ to
$\partial\mathbf{F}(v)$ is

$-\frac{1}{\upsilon(v)}h(r)\frac{w(r)}{h(r)}=-\frac{1}{\upsilon(v)}w(r).$

When $v\neq b$, summing this over all rectangles with bottom side on $v$ gives
the negative of the total length of the horizontal segments on $v$, divided by
$\upsilon(v)$. Therefore, for all $v\in\\{a,b\\}^{c}$, we have
$\partial\mathbf{F}(v)=0$, proving part (i).

To show part (ii), note by Proposition 3.11 that it is equivalent to show that
$\mathbf{F}$ lies in $\operatorname{Cut}(E,\varepsilon)$. The latter follows
because $\mathbf{F}=\nabla y$, where $y\in L^{2}(V,\upsilon)$ describes the
$y$-coordinates of the horizontal lines in the plane. ∎

The next theorem gives an interlacing result using rectangular tilings and the
edge Laplacian.

######  Theorem 6.3.

Let $(G,\upsilon,\varepsilon)$ be a weighted multigraph and let $e=ab$ be an
edge. Let $R$ be a rectangle satisfying $\varepsilon(e)=\frac{w(R)}{h(R)}$,
and consider any rectangular tiling of $R$. Define
$(G^{\prime},\upsilon^{\prime},\varepsilon^{\prime})$ to be the weighted graph
obtained by replacing the weighted edge $e$ with the edge-weighted graph
associated with the tiling, identifying $a$ and $b$ with the vertices
corresponding to the bottom and top sides of $R$, respectively, and letting
the weights of the new vertices be arbitrary. Let
$\lambda_{1}\leq\dots\leq\lambda_{n}$ and $\mu_{1}\leq\dots\leq\mu_{n+k}$
denote the weighted Laplacian eigenvalues of $(G,\upsilon,\varepsilon)$ and
$(G^{\prime},\upsilon^{\prime},\varepsilon^{\prime})$, respectively. Then

$\mu_{i}\leq\lambda_{i}\leq\mu_{i+k}$

for all $1\leq i\leq n$.

###### Proof.

It suffices to prove the inequalities for the nonzero eigenvalues, so we will
prove the interlacing for the eigenvalues of the edge Laplacian. Let
$G^{\prime}=(V^{\prime},E^{\prime})$ and write $E^{\prime}=E_{1}\cup E_{2}$,
where $E_{1}$ consists of the edges of $E^{\prime}$ from $E$, and $E_{2}$
consists of the edges of the graph associated with the tiling of $R$.

Define $\iota:L^{2}(E,\varepsilon)\to L^{2}(E^{\prime},\varepsilon^{\prime})$
by

$\iota\mathbf{F}(uv)=\mathbf{F}(uv)$

if $uv\in E_{1}$, and

$\iota\mathbf{F}(r)=\frac{\mathbf{F}(ab)\cdot\mathbf{v}_{\vec{ab}}}{h(R)}h(r)\mathbf{v}_{\vec{uv}}$

if $r=uv\in E_{2}$ with $u$ and $v$ corresponding to the bottom and top sides
of $r$, respectively.

First, we will check that $\iota$ is an isometry. Note that it sends an
orthogonal basis for $L^{2}(E,\varepsilon)$ of characteristic functions of
directed edges to orthogonal functions in
$L^{2}(E^{\prime},\varepsilon^{\prime})$. It also preserves squared norms of
characteristic functions of directed edges in $\vec{E}_{1}$. It remains to
show that the squared norm of $\mathbf{1}_{\vec{ab}}$ in
$L^{2}(E,\varepsilon)$ is equal to the squared norm of
$\iota\mathbf{1}_{\vec{ab}}$ in $L^{2}(E^{\prime},\varepsilon^{\prime})$,
which follows because

$\int_{E}\lVert\mathbf{1}_{\vec{ab}}\rVert^{2}d\varepsilon=\frac{w(R)}{h(R)}=\frac{1}{h(R)^{2}}\sum_{r\in
E_{2}}h(r)^{2}\frac{w(r)}{h(r)}=\int_{E^{\prime}}\lVert\iota\mathbf{1}_{\vec{ab}}\rVert^{2}d\varepsilon^{\prime},$

where the second equality holds because the left expression is equal to
$\frac{1}{h(R)^{2}}$ of the area of $R$, while the right expression is equal
to $\frac{1}{h(R)^{2}}$ of the sum of the areas of the rectangles $r$ used to
tile $R$. So $\iota$ is an isometry.

Moreover, by Lemma 6.2(i) and its proof, we have

$\partial\iota\mathbf{1}_{\vec{ab}}(v)=0$

for all vertices $v\neq a,b$, while

$\partial\iota\mathbf{1}_{\vec{ab}}(a)=-\frac{1}{\upsilon(a)h(R)}w(R)=\partial\mathbf{1}_{\vec{ab}}(a)$

and

$\partial\iota\mathbf{1}_{\vec{ab}}(b)=\frac{1}{\upsilon(b)h(R)}w(R)=\partial\mathbf{1}_{\vec{ab}}(b),$

since $w(R)$ is the total length of the horizontal segments on the line
corresponding to $a$ and on the line corresponding to $b$. It follows that for
all $\mathbf{F}\in L^{2}(E,\varepsilon)$ and all $v\in V$, we have

$\partial\iota\mathbf{F}(v)=\partial\mathbf{F}(v)$

and for all $v\in V^{\prime}\setminus V$,

$\partial\iota\mathbf{F}(v)=0.$

Next, we will show that $\iota$ restricts to a well-defined map
$\operatorname{Cut}(E,\varepsilon)\to\operatorname{Cut}(E^{\prime},\varepsilon^{\prime})$.
To see that $\iota\mathbf{F}$ lies in
$\operatorname{Cut}(E^{\prime},\varepsilon^{\prime})$ whenever
$\mathbf{F}\in\operatorname{Cut}(E,\varepsilon)$, we first note that the
restriction of $\iota\mathbf{F}$ on
$(G^{\prime}[E_{1}],\upsilon^{\prime},\varepsilon^{\prime})$ is the
restriction of $\mathbf{F}$ on $(G[E_{1}],\upsilon,\varepsilon)$, which is
conservative as $\mathbf{F}$ is conservative on $(G,\upsilon,\varepsilon)$.
The restriction of $\iota\mathbf{F}$ on
$(G^{\prime}[E_{2}],\upsilon^{\prime},\varepsilon^{\prime})$ is also
conservative, being a scaled multiple of a vector field shown to be
conservative in Lemma 6.2(ii). In particular,
$\iota\mathbf{F}=\frac{\mathbf{F}(ab)\cdot\mathbf{v}_{\vec{ab}}}{h(R)}\nabla
y$ on $E_{2}$, where $y$ gives the $y$-coordinate of horizontal lines in the
plane.

Let $\frac{C}{\varepsilon^{\prime}}$ be a simple closed curve on
$(G^{\prime},\upsilon^{\prime},\varepsilon^{\prime})$. If $C$ uses only edges
in $E_{1}$ or only edges in $E_{2}$, then

$\int_{\frac{C}{\varepsilon^{\prime}}}\iota\mathbf{F}\cdot
d\varepsilon^{\prime}=0,$

since $\iota\mathbf{F}$ is conservative when restricted to either
$(G^{\prime}[E_{1}],\upsilon^{\prime},\varepsilon^{\prime})$ or
$(G^{\prime}[E_{2}],\upsilon^{\prime},\varepsilon^{\prime})$. Otherwise, if
$\frac{C}{\varepsilon^{\prime}}$ uses edges in both $E_{1}$ and $E_{2}$, then
its edges can be split into those of two curves,
$\frac{C_{1}}{\varepsilon^{\prime}}$ and $\frac{C_{2}}{\varepsilon^{\prime}}$
from $a$ to $b$ and from $b$ to $a$, respectively, each using only edges from
one of $E_{1}$ or $E_{2}$.

If $\frac{C_{1}}{\varepsilon^{\prime}}$ uses only edges in $E_{1}$, then

$\int_{\frac{C_{1}}{\varepsilon^{\prime}}}\iota\mathbf{F}\cdot
d\varepsilon^{\prime}=\int_{\frac{C_{1}}{\varepsilon}}\mathbf{F}\cdot
d\varepsilon=\int_{\frac{\vec{ab}}{\varepsilon}}\mathbf{F}\cdot
d\varepsilon=\mathbf{F}(ab)\cdot\mathbf{v}_{\vec{ab}},$

where $\frac{\vec{ab}}{\varepsilon}$ denotes the curve from $a$ to $b$ in
$(G,\upsilon,\varepsilon)$ via the directed edge $\vec{ab}$, and the second
equality is by Proposition 3.11. Otherwise, if
$\frac{C_{1}}{\varepsilon^{\prime}}$ uses only edges in $E_{2}$, then

$\int_{\frac{C_{1}}{\varepsilon^{\prime}}}\iota\mathbf{F}\cdot
d\varepsilon^{\prime}=\int_{\frac{C_{1}}{\varepsilon^{\prime}}}\frac{\mathbf{F}(ab)\cdot\mathbf{v}_{\vec{ab}}}{h(R)}\nabla
y\cdot
d\varepsilon^{\prime}=\frac{\mathbf{F}(ab)\cdot\mathbf{v}_{\vec{ab}}}{h(R)}(y(b)-y(a))=\mathbf{F}(ab)\cdot\mathbf{v}_{\vec{ab}},$

with the second equality by Proposition 3.5 and the third equality because the
difference between the $y$-coordinates of the top and bottom sides of $R$ is
the height of $R$. Similarly,
$\int_{\frac{C_{2}}{\varepsilon^{\prime}}}\iota\mathbf{F}\cdot
d\varepsilon^{\prime}=-\mathbf{F}(ab)\cdot\mathbf{v}_{\vec{ab}},$ regardless
of whether $\frac{C_{2}}{\varepsilon}$ only uses edges in $E_{1}$ or in
$E_{2}$. Hence, $\int_{\frac{C}{\varepsilon^{\prime}}}\iota\mathbf{F}\cdot
d\varepsilon^{\prime}=0$ for all simple closed curves
$\frac{C}{\varepsilon^{\prime}}$, and so
$\iota\mathbf{F}\in\operatorname{Cut}(E^{\prime},\varepsilon^{\prime})$ by
Proposition 3.11.

Now consider the restrictions of the edge Laplacians to the cut spaces, i.e.
$K_{(G,\upsilon,\varepsilon)}:\operatorname{Cut}(E,\varepsilon)\to\operatorname{Cut}(E,\varepsilon)$
and
$K_{(G^{\prime},\upsilon^{\prime},\varepsilon^{\prime})}:\operatorname{Cut}(E^{\prime},\varepsilon^{\prime})\to\operatorname{Cut}(E^{\prime},\varepsilon^{\prime})$,
which are well-defined and self-adjoint since the cut space is the image of
the edge Laplacian, which is the span of its eigenfunctions with nonzero
eigenvalues. By Remark 2.7, since

$\langle
K_{(G,\upsilon,\varepsilon)}\mathbf{F},\mathbf{F}\rangle=\langle\partial\mathbf{F},\partial\mathbf{F}\rangle=\langle\partial\iota\mathbf{F},\partial\iota\mathbf{F}\rangle=\langle
K_{(G^{\prime},\upsilon^{\prime},\varepsilon^{\prime})}\iota\mathbf{F},\iota\mathbf{F}\rangle$

for all $\mathbf{F}\in\operatorname{Cut}(E,\varepsilon)$, it follows that
$K_{(G,\upsilon,\varepsilon)}=\iota^{*}K_{(G^{\prime},\upsilon^{\prime},\varepsilon^{\prime})}\iota$.
Then Theorem 2.6, the Cauchy interlacing theorem, gives a series of
interlacing inequalities for the nonzero eigenvalues of the edge Laplacians.
Since $G$ and $G^{\prime}$ have the same number of connected components,
$(G^{\prime},\upsilon^{\prime},\varepsilon^{\prime})$ has $k$ more nonzero
edge Laplacian eigenvalues than $(G,\upsilon,\varepsilon)$, and so

$\mu_{i}\leq\lambda_{i}\leq\mu_{i+k}$

for all $1\leq i\leq n$. ∎

######  Remark 6.4.

Brooks, Smith, Stone and Tutte [8] were primarily interested in square tilings
of squares, especially perfect squarings, where only squares of distinct side
lengths are used. When Theorem 6.3 is applied with a square tiling of a square
and all edge weights of $(G,\upsilon,\varepsilon)$ are $1$, then all edge
weights of $(G^{\prime},\upsilon^{\prime},\varepsilon^{\prime})$ are also $1$.
If moreover the squaring is perfect and $G$ is simple, then $G^{\prime}$ is
guaranteed to also be simple (as multiple edges between a pair of vertices
would require two squares of equal height in the tiling).

######  Remark 6.5.

Given a rectangular tiling, there may be multiple edge-weighted graphs which
can be constructed from the tiling that satisfy Kirchhoff’s laws as in Lemma
6.2. For example, one can alternatively take the vertex set to be the set of
horizontal segments, as is done in [8]. Then a version of Theorem 6.3 still
holds, as the proof follows through, although the bounds on the weighted
Laplacian eigenvalues of $(G,\upsilon,\varepsilon)$ are looser, as the
interlacing result can also be deduced by applying Theorem 5.5 and the stated
version of Theorem 6.3.

Continuing the analogy with electrical networks, we give the following
definition from the theory of network reduction. A Kron reduction of a
weighted graph $(G,\upsilon,\varepsilon)$ over $S\subseteq V$ not containing
any connected components is a weighted graph $(G/S,\upsilon,\varepsilon/S)$
with vertex set $S^{c}$ and vertex weights given by $\upsilon$, so that for
any $f\in L^{2}(S^{c},\upsilon)$ and $u\in S^{c}$, we have

$L_{(G/S,\upsilon,\varepsilon/S)}f(u)=L_{(G,\upsilon,\varepsilon)}\tilde{f}(u),$

where $\tilde{f}\in L^{2}(V,\upsilon)$ is an extension of $f$ satisfying

$L_{(G,\upsilon,\varepsilon)}\tilde{f}(v)=0$

for all $v\in S$.

If we write the matrix of $L_{(G,\upsilon,\varepsilon)}$ in the basis of
characteristic functions of vertices as the block matrix

$L_{(G,\upsilon,\varepsilon)}=\begin{pmatrix}L_{(G,\upsilon,\varepsilon)}^{\hat{S}}&B\\\
C&D\end{pmatrix},$

where the first rows and columns are ordered to correspond to $S^{c}$, we can
derive the matrix of $L_{(G/S,\upsilon,\varepsilon/S)}$. Note that the values
of $D\tilde{f}$ on $S$ must sum with $Cf$ to equal zero. Since $S$ does not
contain any connected component, there is a path from each vertex in $V$ to a
vertex of $S^{c}$, and so there exists an $S^{c}$-rooted spanning forest of
$G$. By Theorem 2.2, the matrix $D$ is invertible, and the values of
$\tilde{f}$ on $S$ are given exactly by $-D^{-1}Cf$. Then

$L_{(G/S,\upsilon,\varepsilon/S)}f=\begin{pmatrix}L_{(G,\upsilon,\varepsilon)}^{\hat{S}}&B\end{pmatrix}\begin{pmatrix}f\\\
-D^{-1}Cf\end{pmatrix}=L_{(G,\upsilon,\varepsilon)}^{\hat{S}}f-BD^{-1}Cf$

for all $f\in L^{2}(S^{c},\upsilon)$, and so
$L_{(G/S,\upsilon,\varepsilon/S)}$ must identically equal
$L_{(G,\upsilon,\varepsilon)}^{\hat{S}}-BD^{-1}C$. For general matrices, this
is also known as a Schur complement.

Since vertex weights are given by $\upsilon$, from the matrix of
$L_{(G/S,\upsilon,\varepsilon/S)}$, we can also deduce the total edge weight
between any pair of distinct vertices. Therefore, if a Kron reduction
$(G/S,\upsilon,\varepsilon/S)$ exists, it is unique up to the operations in
Lemma 3.8(ii) and (iii).

One special case of a Kron reduction is known as the star-mesh transform in
circuit analysis. Given a loopless nonisolated vertex $v$, the weighted graph
$(G/v,\upsilon,\varepsilon/v)$ is obtained by deleting $v$ and all incident
edges, and adding for each pair of edges $u_{1}v$ and $u_{2}v$ with $u_{1}\neq
u_{2}$ a new edge $u_{1}u_{2}$ with weight given by

$(\varepsilon/v)(u_{1}u_{2})=\frac{\varepsilon(u_{1}v)\varepsilon(u_{2}v)}{d_{(G,\varepsilon)}(v)}.$

The matrix of $L_{(G/v,\upsilon,\varepsilon/v)}$ can be checked to coincide
with our formula for the Kron reduction over $v$. Note then that the existence
of a Kron reduction over $S\subseteq V$ containing no connected components can
be deduced by repeated applications of the star-mesh transform, and that the
number of connected components remains constant after a Kron reduction.

######  Example 6.6.

Let $(G,\upsilon,\varepsilon)$ be the weighted graph depicted on the left, and
let $v$ be the vertex of weight $5$ in $(G,\upsilon,\varepsilon)$. Then
$(G/v,\upsilon,\varepsilon/v)$, obtained from $(G,\upsilon,\varepsilon)$ by
applying the star-mesh transform at vertex $v$, is the weighted graph depicted
on the right.

23512321$(G,\upsilon,\varepsilon)$231$\frac{1}{4}$$\frac{3}{8}$$\frac{3}{4}$$\frac{1}{2}$$\frac{1}{4}$$(G/v,\upsilon,\varepsilon/v)$

We will now prove an interlacing result on the weighted Laplacian eigenvalues
of a weighted graph and its Kron reduction. It is also known more generally
that the eigenvalues of a semidefinite real symmetric matrix interlace those
of a Schur complement [39, Theorem 5], which can be extended to apply to the
weighted Laplacian, despite it not necessarily being symmetric. We offer a
different proof using the edge Laplacian. Note that Theorem 6.3 is a special
case of the following theorem in which the Kron reduction has a geometric
interpretation and is easy to compute.

######  Theorem 6.7.

Let $(G,\upsilon,\varepsilon)$ be a weighted multigraph and let $S\subseteq V$
not contain any connected components. Let
$\lambda_{1}\leq\dots\leq\lambda_{n}$ and $\mu_{1}\leq\dots\leq\mu_{n-k}$
denote the weighted Laplacian eigenvalues of $(G,\upsilon,\varepsilon)$ and
its Kron reduction $(G/S,\upsilon,\varepsilon/S)$, respectively. Then

$\lambda_{i}\leq\mu_{i}\leq\lambda_{i+k}$

for all $1\leq i\leq n-k$.

###### Proof.

We will consider the restrictions
$K_{(G,\upsilon,\varepsilon)}:\operatorname{Cut}(E,\varepsilon)\to\operatorname{Cut}(E,\varepsilon)$
and
$K_{(G/S,\upsilon,\varepsilon/S)}:\operatorname{Cut}(E/S,\varepsilon/S)\to\operatorname{Cut}(E/S,\varepsilon/S)$,
where $E/S$ denotes the edge set of $G/S$, of the edge Laplacians to the
relevant cut spaces.

Define
$\iota:\operatorname{Cut}(E/S,\varepsilon/S)\to\operatorname{Cut}(E,\varepsilon)$
to be the linear map sending $\nabla f\mapsto\nabla\tilde{f}$ for each $f\in
L^{2}(S^{c},\upsilon)$. Then $\iota$ is an isometry, since for each $f,g\in
L^{2}(S^{c},\upsilon)$, we have

$\langle\nabla f,\nabla g\rangle=\langle
L_{(G/S,\upsilon,\varepsilon/S)}f,g\rangle=\langle
L_{(G,\upsilon,\varepsilon)}\tilde{f},\tilde{g}\rangle=\langle\nabla\tilde{f},\nabla\tilde{g}\rangle,$

recalling that $L_{(G,\upsilon,\varepsilon)}\tilde{f}$ coincides with
$L_{(G/S,\upsilon,\varepsilon/S)}f$ on $S^{c}$, and otherwise equals zero on
$S$, and that $\tilde{g}$ coincides with $g$ on $S^{c}$.

Note $\iota$ also preserves quadratic form, since for all $f,g\in
L^{2}(S^{c},\upsilon)$,

$\langle K_{(G/S,\upsilon,\varepsilon/S)}\nabla f,\nabla g\rangle=\langle
L_{(G/S,\upsilon,\varepsilon/S)}f,L_{(G/S,\upsilon,\varepsilon/S)}g\rangle=\langle
L_{(G,\upsilon,\varepsilon)}\tilde{f},L_{(G,\upsilon,\varepsilon)}\tilde{g}\rangle=\langle
K_{(G,\upsilon,\varepsilon)}\nabla\tilde{f},\nabla\tilde{g}\rangle,$

as $L_{(G,\upsilon,\varepsilon)}\tilde{f}$ and
$L_{(G,\upsilon,\varepsilon)}\tilde{g}$ coincide with
$L_{(G/S,\upsilon,\varepsilon/S)}f$ and $L_{(G/S,\upsilon,\varepsilon/S)}g$,
respectively, on $S^{c}$, and otherwise equal zero on $S$. By Remark 2.7,
$K_{(G/S,\upsilon,\varepsilon/S)}=\iota^{*}K_{(G,\upsilon,\varepsilon)}\iota$.

The Cauchy interlacing theorem, Theorem 2.6, gives interlacing inequalities on
the nonzero eigenvalues of the edge Laplacians. Since $G/S$ has the same
number of connected components as $G$, we conclude that

$\lambda_{i}\leq\mu_{i}\leq\lambda_{i+k}$

for all $1\leq i\leq n-k$. ∎

Interestingly, vertex reduction by the star-mesh transform appears to be
analogous to edge contraction. In the former, the weighted Laplacian Rayleigh
quotients for conservative vector fields on the reduced weighted graph may be
realised as the weighted Laplacian Rayleigh quotients for conservative vector
fields with zero divergence at the reduced vertex in the original weighted
graph. In the latter, the weighted Laplacian Rayleigh quotients for scalar
fields on the contracted weighted graph may be realised as the weighted
Laplacian Rayleigh quotients for scalar fields with zero gradient at the
contracted edge in the original weighted graph. It is natural to ask, then, if
there exists a vertex analogue of the deletion-contraction relation in Theorem
4.4.

Note in edge deletion that the total amount of edge weight between the
endpoints of the deleted edge is modified. The vertex analogue then is to
modify the weight of the relevant vertex. We now prove a vertex analogue of
deletion-contraction, which we call addition-reduction.

######  Theorem 6.8.

Let $(G,\upsilon,\varepsilon)$ be a weighted multigraph and let $v$ be a
loopless nonisolated vertex. Let $\eta(v)\in\mathbb{R}_{>0}$. Then

$P_{(G,\upsilon,\varepsilon)}(t)=\frac{\upsilon(v)}{\upsilon(v)+\eta(v)}P_{(G,\upsilon+\eta,\varepsilon)}(t)-\frac{\eta(v)}{\upsilon(v)+\eta(v)}d_{(G,\varepsilon)}(v)P_{(G/v,\upsilon,\varepsilon/v)}(t).$

###### Proof.

Note that the polynomial $P_{(G,\upsilon,\varepsilon)}(t)$, after fixing $G$
and all vertex and edge weights other than the weight of $v$, may be thought
of as a degree $1$ polynomial in $\upsilon(v)$, with coefficients in
$\mathbb{R}[t]$. Therefore, we can write

$P_{(G,\upsilon,\varepsilon)}(t)=\upsilon(v)P^{v}_{(G,\upsilon,\varepsilon)}(t)+P^{/v}_{(G,\upsilon,\varepsilon)}(t),$

where $P^{/v}_{(G,\upsilon,\varepsilon)}(t)$ is
$P_{(G,\upsilon,\varepsilon)}(t)$, thought of as a polynomial in
$\upsilon(v)$, evaluated at $\upsilon(v)=0$. Since
$(G,\upsilon+\eta,\varepsilon)$ differs from $(G,\upsilon,\varepsilon)$ only
on the weight of $v$, we also have

$P_{(G,\upsilon+\eta,\varepsilon)}(t)=(\upsilon(v)+\eta(v))P^{v}_{(G,\upsilon,\varepsilon)}(t)+P^{/v}_{(G,\upsilon,\varepsilon)}(t).$

Therefore, to prove the theorem statement, it is sufficient to show that

$P^{/v}_{(G,\upsilon,\varepsilon)}(t)=-d_{(G,\varepsilon)}(v)P_{(G/v,\upsilon,\varepsilon/v)}(t).$

Writing $L_{(G,\varepsilon)}$ as the block matrix

$L_{(G,\varepsilon)}=\begin{pmatrix}L_{(G,\varepsilon)}^{\hat{v}}&B\\\
C&d_{(G,\varepsilon)}(v)\end{pmatrix},$

we find that

$L_{(G/v,\varepsilon/v)}=W_{\upsilon}^{\hat{v}}L_{(G/v,\upsilon,\varepsilon/v)}=L_{(G,\varepsilon)}^{\hat{v}}-\frac{1}{d_{(G,\varepsilon)}(v)}BC,$

where $W_{\upsilon}^{\hat{v}}$ denotes the principal submatrix of
$W_{\upsilon}$ obtained by deleting the row and column corresponding to $v$.

The result then follows, as

$\displaystyle P^{/v}_{(G,\upsilon,\varepsilon)}(t)$
$\displaystyle=\det\left(\begin{pmatrix}tW_{\upsilon}^{\hat{v}}-L_{(G,\varepsilon)}^{\hat{v}}&-B\\\
-C&-d_{(G,\varepsilon)}(v)\end{pmatrix}\begin{pmatrix}I&0\\\
-\frac{1}{d_{(G,\varepsilon)}(v)}C&1\end{pmatrix}\right)$
$\displaystyle=\det\begin{pmatrix}tW_{\upsilon}^{\hat{v}}-L_{(G/v,\varepsilon/v)}&-B\\\
0&-d_{(G,\varepsilon)}(v)\end{pmatrix}=-d_{(G,\varepsilon)}(v)P_{(G/v,\upsilon,\varepsilon/v)}(t).$

∎

######  Remark 6.9.

More generally, the proof of Theorem 6.8 can be extended to show that for any
square matrix and any row with nonzero diagonal entry, there is a nontrivial
linear relation between its characteristic polynomial and the characteristic
polynomials of the matrices obtained by scaling the row and taking the Schur
complement over the row. Another way to recover the deletion-contraction
relation in Theorem 4.4, then, is by showing that the edge Laplacian of the
contracted weighted graph may be realised as a Schur complement of the edge
Laplacian of the original weighted graph.

##  7\. Weighted spectral bounds

In this section, we will give applications of weighted Laplacian eigenvalues
to bounding various properties of a weighted graph. We will see that various
results on combinatorial and normalised Laplacian eigenvalues can be proved
through a unified approach using weighted Laplacian eigenvalues.

Given a weighted graph $(G,\upsilon,\varepsilon)$ and $\emptyset\subsetneq
S\subsetneq V$, define the isoperimetric ratio of $S$ to be

$\theta(S)=\frac{\varepsilon(\nabla
S)}{\min\\{\upsilon(S),\upsilon(S^{c})\\}},$

which measures the quality of a weighted cut. Note that here we think of
$\nabla S$ as a set of undirected edges in $E$, in order for its measure under
$\varepsilon$ to be well-defined. The sparsest weighted cut attains an
isoperimetric ratio of

$\theta_{(G,\upsilon,\varepsilon)}=\min_{\emptyset\subsetneq S\subsetneq
V}\theta(S),$

which we call the isoperimetric constant of $(G,\upsilon,\varepsilon)$ and is
analogous to the Cheeger isoperimetric constant from Riemannian geometry.

The following theorem shows that given a scalar field in $L^{2}(V,\upsilon)$
orthogonal to $1_{V}$ with small Rayleigh quotient, one can construct a good
cut. We adapt the proof in [17, Theorem 2.2].

######  Theorem 7.1.

Let $(G,\upsilon,\varepsilon)$ be a weighted multigraph with at least two
vertices and let nonzero $f\in L^{2}(V,\upsilon)$ satisfy
$\int_{V}fd\upsilon=0$. Then there exists some $t\in\mathbb{R}$ for which
$\emptyset\subsetneq S_{t}\subsetneq V$ and

$\frac{\theta(S_{t})^{2}}{2}\leq\frac{\langle
L_{(G,\upsilon,\varepsilon)}f,f\rangle}{\langle f,f\rangle}\max_{v\in
V}\frac{d_{(G,\varepsilon)}(v)}{{\upsilon}(v)},$

where $S_{t}=\\{v\in V\mid f(v)\leq t\\}.$

###### Proof.

Let $r$ denote the least real number such that
$\upsilon(S_{r})\geq\frac{\upsilon(V)}{2}.$ Since $\int_{V}fd\upsilon=0$, we
have

$\int_{V}|f|^{2}d\upsilon\leq\int_{V}|f|^{2}d\upsilon+r^{2}=\int_{V}|f-r|^{2}d\upsilon.$

Let $g=f-r$, and denote its positive and negative parts by
$g_{+}=\max\\{g,0\\}$ and $g_{-}=\max\\{-g,0\\}$, respectively. Then

$\displaystyle\frac{\langle L_{(G,\upsilon,\varepsilon)}f,f\rangle}{\langle
f,f\rangle}$ $\displaystyle=\frac{\int_{E}\lVert\nabla
f\rVert^{2}d\varepsilon}{\int_{V}|f|^{2}d\upsilon}$
$\displaystyle\geq\frac{\int_{E}\lVert\nabla
g\rVert^{2}d\varepsilon}{\int_{V}|g|^{2}d\upsilon}$
$\displaystyle\geq\frac{\int_{E}\lVert\nabla
g_{+}\rVert^{2}d\varepsilon+\int_{E}\lVert\nabla
g_{-}\rVert^{2}d\varepsilon}{\int_{V}|g_{+}|^{2}d\upsilon+\int_{V}|g_{-}|^{2}d\upsilon}\geq\min\left\\{\frac{\int_{E}\lVert\nabla
g_{+}\rVert^{2}d\varepsilon}{\int_{V}|g_{+}|^{2}d\upsilon},\frac{\int_{E}\lVert\nabla
g_{-}\rVert^{2}d\varepsilon}{\int_{V}|g_{-}|^{2}d\upsilon}\right\\},$

where in the last expression we take the minimum among the terms that are
defined. We assume without loss of generality that this minimum is
$\frac{\int_{E}\lVert\nabla
g_{+}\rVert^{2}d\varepsilon}{\int_{V}|g_{+}|^{2}d\upsilon}$.

Note after extending the definition of $\frac{\lVert\nabla
g_{+}^{2}\rVert^{2}}{\lVert\nabla g_{+}\rVert^{2}}$ where it is undefined, we
have for each edge $uv\in E$ that

$\frac{\lVert\nabla g_{+}^{2}(uv)\rVert^{2}}{\lVert\nabla
g_{+}(uv)\rVert^{2}}=|g_{+}(u)+g_{+}(v)|^{2}\leq
2(|g_{+}(u)|^{2}+|g_{+}(v)|^{2}).$

Therefore,

$\int_{E}\frac{\lVert\nabla g_{+}^{2}\rVert^{2}}{\lVert\nabla
g_{+}\rVert^{2}}d\varepsilon\leq 2\int_{V}|g_{+}|^{2}dd_{(G,\varepsilon)},$

and so

$\frac{\int_{E}\lVert\nabla
g_{+}\rVert^{2}d\varepsilon}{\int_{V}|g_{+}|^{2}d\upsilon}\geq\frac{\left(\int_{E}\lVert\nabla
g_{+}\rVert^{2}d\varepsilon\right)\left(\int_{E}\frac{\lVert\nabla
g_{+}^{2}\rVert^{2}}{\lVert\nabla
g_{+}\rVert^{2}}d\varepsilon\right)}{\left(\int_{V}|g_{+}|^{2}d\upsilon\right)\left(2\int_{V}|g_{+}|^{2}dd_{(G,\varepsilon)}\right)}\geq\frac{\left(\int_{E}\lVert\nabla
g_{+}^{2}\rVert
d\varepsilon\right)^{2}}{2\left(\int_{V}|g_{+}|^{2}d\upsilon\right)^{2}\max_{v\in
V}\frac{d_{(G,\varepsilon)}(v)}{\upsilon(v)}},$

where in the second inequality we apply Cauchy-Schwarz to the numerator.

Define

$\gamma_{f}=\min_{\emptyset\subsetneq S_{t}\subsetneq V}\theta(S_{t}),$

and choose real numbers $t_{1}<\dots<t_{k}$ such that all distinct level sets
of $g_{+}$ (and hence of $g_{+}^{2}$) are given by $L_{1}=S_{t_{1}}$,
$L_{2}=S_{t_{2}}\setminus S_{t_{1}}$, …, $L_{k-1}=S_{t_{k}}\setminus
S_{t_{k-1}}$. Then

$\displaystyle\int_{E}\lVert\nabla g_{+}^{2}\rVert d\varepsilon$
$\displaystyle=\sum_{i=1}^{k-1}(|g_{+}(L_{i+1})|^{2}-|g_{+}(L_{i})|^{2})\varepsilon(\nabla
S_{t_{i}})$
$\displaystyle\geq\gamma_{f}\sum_{i=1}^{k-1}(|g_{+}(L_{i+1})|^{2}-|g_{+}(L_{i})|^{2})\upsilon(S_{t_{i}}^{c})$
$\displaystyle=\gamma_{f}\sum_{i=1}^{k}|g_{+}(L_{i})|^{2}\upsilon(L_{i})=\gamma_{f}\int_{V}|g_{+}|^{2}d\upsilon,$

where the first line follows by counting, and the second line by definition of
$\gamma_{f}$ and noting that each
$\upsilon(S_{t_{i}})\geq\upsilon(S_{r})\geq\frac{\upsilon(V)}{2}$.

Putting everything together, we obtain

$\frac{\langle L_{(G,\upsilon,\varepsilon)}f,f\rangle}{\langle
f,f\rangle}\geq\frac{\left(\gamma_{f}\int_{V}|g_{+}|^{2}d\upsilon\right)^{2}}{2\left(\int_{V}|g_{+}|^{2}d\upsilon\right)^{2}\max_{v\in
V}\frac{d_{(G,\varepsilon)}(v)}{\upsilon(v)}}.$

Rearranging gives the desired inequality

$\frac{\gamma_{f}^{2}}{2}\leq\frac{\langle
L_{(G,\upsilon,\varepsilon)}f,f\rangle}{\langle f,f\rangle}\max_{v\in
V}\frac{d_{(G,\varepsilon)}(v)}{\upsilon(v)}.$

∎

As a corollary, we can show that a weighted graph has a good cut if and only
if its second weighted Laplacian eigenvalue $\lambda_{2}$ is small. The harder
direction of Corollary 7.2 was also proved by Friedman and Tillich, who also
studied graph Laplacians with general vertex and edge measures, in [23,
Theorem 5.2], which generalises [22, Theorem 2.3] and [17, Theorem 2.2] for
the combinatorial and normalised Laplacians, respectively.

######  Corollary 7.2 (Weighted Cheeger inequality).

Let $(G,\upsilon,\varepsilon)$ be a weighted multigraph with at least two
vertices and let $\lambda_{2}$ be its second smallest weighted Laplacian
eigenvalue. Then

$\frac{\lambda_{2}}{2}\leq\theta_{(G,\upsilon,\varepsilon)}\leq\sqrt{2\lambda_{2}\max_{v\in
V}\frac{d_{(G,\varepsilon)}(v)}{{\upsilon}(v)}}$

###### Proof.

Let $\emptyset\subsetneq S\subsetneq V$ attain an isoperimetric ratio of
$\theta_{(G,\upsilon,\varepsilon)}$. Consider the scalar field
$f=1_{S}-\frac{\upsilon(S)}{\upsilon(V)}1_{V}$. We note that

$\langle L_{(G,\upsilon,\varepsilon)}f,f\rangle=\int_{E}\lVert\nabla
1_{S}\rVert^{2}d\varepsilon=\varepsilon(\nabla S),$

where the first equality follows because $1_{V}$ lies in the kernel of
$\nabla$. Additionally, we can compute from the definition of $f$ that

$\langle
f,f\rangle=\int_{S}\left|1-\frac{\upsilon(S)}{\upsilon(V)}\right|^{2}d\upsilon+\int_{S^{c}}\left|\frac{\upsilon(S)}{\upsilon(V)}\right|^{2}d\upsilon=\frac{\upsilon(S)\upsilon(S^{c})}{\upsilon(V)}.$

Note that

$\upsilon(S)\upsilon(S^{c})=\min\\{\upsilon(S),\upsilon(S^{c})\\}\max\\{\upsilon(S),\upsilon(S^{c})\\}$

with

$\frac{\max\\{\upsilon(S),\upsilon(S^{c})\\}}{\upsilon(V)}\geq\frac{1}{2},$

and so

$\frac{\lambda_{2}}{2}\leq\frac{\langle
L_{(G,\upsilon,\varepsilon)}f,f\rangle}{2\langle
f,f\rangle}\leq\frac{\varepsilon(\nabla
S)}{\min\\{\upsilon(S),\upsilon(S^{c})\\}}=\theta_{(G,\upsilon,\varepsilon)}.$

The left inequality above is a consequence of Lemma 2.5 applied to
$L_{(G,\upsilon,\varepsilon)}$ restricted to the orthogonal complement of
$1_{V}$, since nonzero $f\in L^{2}(V,\upsilon)$ satisfies

$\int_{V}fd\upsilon=\int_{S}d\upsilon-\frac{\upsilon(S)}{\upsilon(V)}\int_{V}d\upsilon=\upsilon(S)-\frac{\upsilon(S)}{\upsilon(V)}\upsilon(V)=0.$

For the other direction, let nonzero $f_{2}\in L^{2}(V,\upsilon)$ be an
eigenfunction of $L_{(G,\upsilon,\varepsilon)}$ orthogonal to $1_{V}$ with
eigenvalue $\lambda_{2}$, and apply Theorem 7.1. ∎

We next prove a bound on the weight of an independent set, a subset
$S\subseteq V$ with no two vertices of $S$ joined by an edge, using the
largest weighted Laplacian eigenvalue $\lambda_{n}$ of a weighted graph.

######  Theorem 7.3.

Let $(G,\upsilon,\varepsilon)$ be a weighted multigraph with at least one
nonloop edge and let $\lambda_{n}$ be its largest weighted Laplacian
eigenvalue. Then for any nonempty independent set $S$, we have

$\upsilon(S)\leq\upsilon(V)\frac{\lambda_{n}-\frac{d_{(G,\varepsilon)}(S)}{\upsilon(S)}}{\lambda_{n}}.$

###### Proof.

Consider the scalar field $f=1_{S}-\frac{\upsilon(S)}{\upsilon(V)}1_{V}\in
L^{2}(V,\upsilon)$. By the same calculations as in the proof of Theorem 7.2,

$\langle L_{(G,\upsilon,\varepsilon)}f,f\rangle=\varepsilon(\nabla
S)=d_{(G,\varepsilon)}(S),$

where the right equality is because $S$ is an independent set and so $\nabla
S$ consists of all edges incident to any vertex of $S$, and

$\langle
f,f\rangle=\frac{\upsilon(S)\upsilon(S^{c})}{\upsilon(V)}=\upsilon(S)\left(1-\frac{\upsilon(S)}{\upsilon(V)}\right).$

Therefore, the Rayleigh quotient of $f$ satisfies

$\frac{\langle L_{(G,\upsilon,\varepsilon)}f,f\rangle}{\langle
f,f\rangle}=\frac{d_{(G,\varepsilon)}(S)}{\upsilon(S)\left(1-\frac{\upsilon(S)}{\upsilon(V)}\right)}\leq\lambda_{n},$

by Lemma 2.5. Rearranging gives the desired inequality

$\upsilon(S)\leq\upsilon(V)\frac{\lambda_{n}-\frac{d_{(G,\varepsilon)}(S)}{\upsilon(S)}}{\lambda_{n}}.$

∎

######  Remark 7.4.

Lower bounding the quantity $\frac{d_{(G,\varepsilon)}(S)}{\upsilon(S)}$ by
$\min_{v\in V}\frac{d_{(G,\varepsilon)}(v)}{\upsilon(v)}$ gives a weaker but
perhaps more practical bound on the weight of an independent set, without the
dependence on $S$ on the right hand side.

When $L_{(G,\upsilon,\varepsilon)}$ is the combinatorial Laplacian, we obtain
the following bound on the size of an independent set, which is also [25,
Corollary 3.5] of Godsil and Newman when all edge weights are $1$.

######  Corollary 7.5.

Let $(G,\varepsilon)$ be an edge-weighted graph with at least one nonloop edge
and let $\lambda_{n}$ be its largest combinatorial Laplacian eigenvalue. Then
for any nonempty independent set $S$, we have

$|S|\leq n\frac{\lambda_{n}-\bar{d}_{(G,\varepsilon)}(S)}{\lambda_{n}},$

where $\bar{d}_{(G,\varepsilon)}(S)$ denotes the average degree of a vertex in
$S$.

Additionally, one could think to apply Theorem 7.3 when
$L_{(G,\upsilon,\varepsilon)}$ is the normalised Laplacian, which gives the
following bound used by Chung [17] in her proof of Corollary 7.9.

######  Corollary 7.6.

Let $(G,\varepsilon)$ be an edge-weighted graph with no isolated vertices and
at least one nonloop edge and let $\lambda_{n}$ be its largest normalised
Laplacian eigenvalue. Then for any nonempty independent set $S$, we have

$d_{(G,\varepsilon)}(S)\leq 2\varepsilon(E)\frac{\lambda_{n}-1}{\lambda_{n}}.$

We conclude this section with results on proper colourings of a graph $G$,
which are maps

$\kappa:V\to\mathbb{Z}_{>0}$

with the property that $\kappa(u)\neq\kappa(v)$ whenever $u,v$ are joined by
an edge in $E$. More specifically, we will give spectral lower bounds on the
chromatic number $\chi(G)$ of a loopless graph $G$, which is the least
$t\in\mathbb{Z}_{>0}$ for which there exists a proper $t$-colouring of $G$, a
proper colouring $\kappa$ with $\kappa(v)\in[t]$ for all vertices $v\in V$.

######  Theorem 7.7.

Let $(G,\upsilon,\varepsilon)$ be a loopless weighted multigraph with at least
one edge and let $\lambda_{n}$ be its largest weighted Laplacian eigenvalue.
Then

$\chi(G)\geq\frac{\lambda_{n}}{\lambda_{n}-\frac{2\varepsilon(E)}{\upsilon(V)}}.$

###### Proof.

Fix a proper $\chi(G)$-colouring $\kappa:V\to[\chi(G)]$ of $G$. Define
$x_{\kappa},y_{\kappa}\in L^{2}(V,\upsilon)$ to be the scalar fields with
$x_{\kappa}(v)=\cos\frac{2\pi\kappa(v)}{\chi(G)}$ and
$y_{\kappa}(v)=\sin\frac{2\pi\kappa(v)}{\chi(G)}$ for all $v\in V$, and extend
the notation similarly to other proper $\chi(G)$-colourings of $G$.

Let $\sigma\in S_{\chi(G)}$ be chosen uniformly at random. Then

$\displaystyle\mathbb{E}\frac{\langle
L_{(G,\upsilon,\varepsilon)}x_{\sigma\kappa},x_{\sigma\kappa}\rangle+\langle
L_{(G,\upsilon,\varepsilon)}y_{\sigma\kappa},y_{\sigma\kappa}\rangle}{\langle
x_{\sigma\kappa},x_{\sigma\kappa}\rangle+\langle
y_{\sigma\kappa},y_{\sigma\kappa}\rangle}$
$\displaystyle=\mathbb{E}\frac{\int_{E}\lVert\nabla
x_{\sigma\kappa}\rVert^{2}d\varepsilon+\int_{E}\lVert\nabla
y_{\sigma\kappa}\rVert^{2}d\varepsilon}{\int_{V}|x_{\sigma\kappa}|^{2}d\upsilon+\int_{V}|y_{\sigma\kappa}|^{2}d\upsilon}$
$\displaystyle=\frac{\mathbb{E}[\int_{E}\lVert\nabla
x_{\sigma\kappa}\rVert^{2}d\varepsilon+\int_{E}\lVert\nabla
y_{\sigma\kappa}\rVert^{2}d\varepsilon]}{\upsilon(V)}$
$\displaystyle=\frac{\int_{E}\mathbb{E}[\lVert\nabla
x_{\sigma\kappa}\rVert^{2}+\lVert\nabla
y_{\sigma\kappa}\rVert^{2}]d\varepsilon}{\upsilon(V)},$

where the second line follows since
$\cos^{2}\frac{2\pi\sigma(\kappa(v))}{\chi(G)}+\sin^{2}\frac{2\pi\sigma(\kappa(v))}{\chi(G)}=1$
for all $\sigma\in S_{\chi(G)}$ and for all vertices $v\in V$, and the third
line follows by interchanging the order of expectation and integration.

Note for any edge $e\in E$ that the values of its endpoints under
$\sigma\kappa$ can be any pair of distinct values in $[\chi(G)]$ with equal
likelihood. Then, letting
$\omega=\cos\frac{2\pi}{\chi(G)}+i\sin\frac{2\pi}{\chi(G)}$,

$\displaystyle\mathbb{E}[\lVert\nabla
x_{\sigma\kappa}(e)\rVert^{2}+\lVert\nabla y_{\sigma\kappa}(e)\rVert^{2}]$
$\displaystyle=\frac{1}{\chi(G)(\chi(G)-1)}\sum_{\begin{subarray}{c}1\leq
i\leq j\leq\chi(G)\\\ i\neq j\end{subarray}}|\omega^{i}-\omega^{j}|^{2}$
$\displaystyle=\frac{1}{\chi(G)-1}\sum_{i=1}^{\chi(G)-1}|\omega^{i}-1|^{2}$
$\displaystyle=\frac{1}{\chi(G)-1}\sum_{i=1}^{\chi(G)-1}(2-\omega^{i}-\omega^{-i})$
$\displaystyle=\frac{2}{\chi(G)-1}\left(\chi(G)-1-\sum_{i=1}^{\chi(G)-1}\omega^{i}\right)=\frac{2\chi(G)}{\chi(G)-1}$

for every edge $e\in E$. Therefore,

$\mathbb{E}\frac{\langle
L_{(G,\upsilon,\varepsilon)}x_{\sigma\kappa},x_{\sigma\kappa}\rangle+\langle
L_{(G,\upsilon,\varepsilon)}y_{\sigma\kappa},y_{\sigma\kappa}\rangle}{\langle
x_{\sigma\kappa},x_{\sigma\kappa}\rangle+\langle
y_{\sigma\kappa},y_{\sigma\kappa}\rangle}=\frac{2\varepsilon(E)\chi(G)}{\upsilon(V)(\chi(G)-1)},$

and so there exists some $\sigma\in S_{\chi(G)}$ for which

$\displaystyle\frac{2\varepsilon(E)\chi(G)}{\upsilon(V)(\chi(G)-1)}$
$\displaystyle\leq\frac{\langle
L_{(G,\upsilon,\varepsilon)}x_{\sigma\kappa},x_{\sigma\kappa}\rangle+\langle
L_{(G,\upsilon,\varepsilon)}y_{\sigma\kappa},y_{\sigma\kappa}\rangle}{\langle
x_{\sigma\kappa},x_{\sigma\kappa}\rangle+\langle
y_{\sigma\kappa},y_{\sigma\kappa}\rangle}$
$\displaystyle\leq\max\left\\{\frac{\langle
L_{(G,\upsilon,\varepsilon)}x_{\sigma\kappa},x_{\sigma\kappa}\rangle}{\langle
x_{\sigma\kappa},x_{\sigma\kappa}\rangle},\frac{\langle
L_{(G,\upsilon,\varepsilon)}y_{\sigma\kappa},y_{\sigma\kappa}\rangle}{\langle
y_{\sigma\kappa},y_{\sigma\kappa}\rangle}\right\\}\leq\lambda_{n},$

where on the second line we take the maximum among the terms that are defined
and apply Lemma 2.5. Rearranging gives the desired inequality

$\chi(G)\geq\frac{\lambda_{n}}{\lambda_{n}-\frac{2\varepsilon(E)}{\upsilon(V)}}.$

∎

When $L_{(G,\upsilon,\varepsilon)}$ is the combinatorial Laplacian, we obtain
the following, which was also found by Spielman in [40, Section 3.7] in the
case where all edge weights are $1$.

######  Corollary 7.8.

Let $(G,\varepsilon)$ be a loopless edge-weighted multigraph with at least one
edge and let $\lambda_{n}$ be its largest combinatorial Laplacian eigenvalue.
Then

$\chi(G)\geq\frac{\lambda_{n}}{\lambda_{n}-\bar{d}_{(G,\varepsilon)}},$

where $\bar{d}_{(G,\varepsilon)}$ denotes the average degree of a vertex.

Finally, if we apply our spectral bound on the chromatic number when
$L_{(G,\upsilon,\varepsilon)}$ is the normalised Laplacian, we obtain Chung’s
[17, Theorem 6.7], which also appears in the work of Coutinho, Grandsire and
Passos in [19, Lemma 3.3] when all edge weights are $1$.

######  Corollary 7.9.

[17, Theorem 6.7] Let $(G,\varepsilon)$ be a loopless edge-weighted multigraph
with no isolated vertices and let $\lambda_{n}$ be its largest normalised
Laplacian eigenvalue. Then

$\chi(G)\geq 1+\frac{1}{\lambda_{n}-1}.$

######  Remark 7.10.

Spielman’s [40] proof of Corollary 7.8 in the case of unit edge weights and
Chung’s [17] proof of Corollary 7.9 used Theorem 7.3 applied to the
combinatorial and normalised Laplacians, respectively. Coutinho, Grandsire and
Passos in [19] gave a proof of Corollary 7.9 in the case of unit edge weights
using interlacing.

Our proof of Theorem 7.7 is distinct from both approaches and demonstrates an
application of the probabilistic method. Moreover, our proof shows something
slightly stronger than the theorem statement, namely that there exists a
nonzero scalar field of one of the forms $x_{\sigma\kappa},y_{\sigma\kappa}$
with Rayleigh quotient
$\geq\frac{2\varepsilon(E)\chi(G)}{\upsilon(V)(\chi(G)-1)}$.

##  8\. New families of trees distinguished by the chromatic symmetric
function

In our final section, we will use deletion-contraction to relate the weighted
Laplacian characteristic polynomial to Stanley’s chromatic symmetric function
[43], and use this connection to prove new cases of a conjecture of Stanley.

We begin by introducing a few new definitions. An integer partition
$\alpha=(\alpha_{1},\dots,\alpha_{\ell(\alpha)})$ is a list of positive
integers $\alpha_{1}\geq\dots\geq\alpha_{\ell(\alpha)}$ sorted in weakly
decreasing order. If $\alpha_{1}+\dots+\alpha_{\ell(\alpha)}=n$, then we write
$\alpha\vdash n$. $\operatorname{Sym}$, the algebra of symmetric functions,
may be realised as a subalgebra of $\mathbb{R}[[x_{1},x_{2},\dots]]$, where
the variables $x_{j}$ commute, as follows. The $i$th power sum symmetric
function $p_{i}$ is defined by

$p_{i}=\sum_{j}x_{j}^{i}.$

Given a partition $\alpha=(\alpha_{1},\dots,\alpha_{\ell(\alpha)})$, the power
sum symmetric function $p_{\alpha}$ is

$p_{\alpha}=\prod_{i=1}^{\ell(\alpha)}p_{\alpha_{i}}.$

Then $\operatorname{Sym}$ is the algebra spanned by the basis
$\\{p_{\alpha}\\}_{\alpha\vdash n\geq 0}$.

Stanley’s chromatic symmetric function [43] was extended to vertex-weighted
graphs with integer weights by Crew and Spirkl in [20].

######  Definition 8.1.

The chromatic symmetric function of an integer vertex-weighted multigraph
$(G,\upsilon)$ with vertex set $\\{v_{1},\dots,v_{n}\\}$ is

$X_{(G,\upsilon)}=\sum_{\kappa}x_{\kappa(v_{1})}^{\upsilon(v_{1})}\dots
x_{\kappa(v_{n})}^{\upsilon(v_{n})},$

where the sum is over all proper colourings $\kappa$ of $G$.

The motivation of Crew and Spirkl to consider vertex-weighted graphs was to
obtain a deletion-contraction recurrence, which we state next.

######  Theorem 8.2.

[20, Lemma 2] Let $(G,\upsilon)$ be an integer vertex-weighted multigraph and
let $e$ be an edge. Then

$X_{(G,\upsilon)}=X_{(G-e,\upsilon)}-X_{(G/e,\upsilon/e)}.$

######  Remark 8.3.

Due to the deletion-contraction relation, the chromatic symmetric function
$X_{(G,\upsilon)}$ is, up to a sign, an evaluation of the $W$-polynomial of
Noble and Welsh [35, Section 2] for integer vertex-weighted graphs. Similarly,
by the relations in Theorem 4.4 and Lemma 3.8(ii), the polynomial
$P_{(G,\upsilon)}(t)$ for integer vertex-weighted graphs is also, up to a
sign, an evaluation of the $W$-polynomial.

In the special case where the graph is unweighted, the $W$-polynomial is known
as the $U$-polynomial. The $U$-polynomial, Brylawski’s polychromate [9] and a
generalisation of Stanley’s chromatic symmetric function known as the Tutte
symmetric function [44] have been shown to be equivalent in [35, 37]. Because
the combinatorial Laplacian characteristic polynomial of an unweighted graph
is, up to a sign, an evaluation of the $U$-polynomial, results on the three
equivalent graph polynomials can give results on the combinatorial Laplacian.

For example, the construction of graphs with equal Tutte symmetric function in
[2, Theorem 11], which generalises a construction of Brylawski of graphs with
equal polychromate in [9, Theorem 4.6], also constructs graphs with equal
combinatorial Laplacian spectrum. Because it employs a deletion-contraction
argument, it can also be modified to construct weighted graphs with equal
weighted Laplacian eigenvalues, even when not all weights are equal to $1$.

Another application is to the graph reconstruction conjecture of Kelly and
Ulam, which asks whether for all graphs $G$ on at least three vertices the
graph can be determined, up to isomorphism, from the multiset of isomorphism
classes of the graphs $G-v$ for $v\in V$; see [4] for a survey. One approach
to the conjecture is to study which graph polynomials and invariants are
reconstructible, or can be deduced from the multiset of isomorphism classes of
the $G-v$ for all graphs $G$ on at least three vertices.

Tutte showed in [46] that various polynomials and invariants, including the
adjacency characteristic polynomial and chromatic polynomial of a graph, are
reconstructible. It turns out that the combinatorial Laplacian characteristic
polynomial is also reconstructible, because the $U$-polynomial is
reconstructible, e.g. by considering the spanning subgraph expansion of the
$U$-polynomial in [35, Proposition 5.1], and applying [46, Theorem 6.7] and
[46, Theorem 6.8] to reconstruct the terms corresponding to the disconnected
and connected spanning subgraphs, respectively.

Stanley’s original definition in [43, Definition 2.1] considered only
unweighted graphs, which is the case where all vertex weights are equal to
$1$. We say that an (unweighted) simple graph is distinguished by the
chromatic symmetric function if any other simple graph with the same chromatic
symmetric function must be isomorphic. Stanley’s tree isomorphism conjecture
is as follows.

######  Conjecture 8.4.

[43, Section 2] Unweighted trees are distinguished by the chromatic symmetric
function.

It is known that any simple graph with the same chromatic symmetric function
as a tree must also be a tree, since the chromatic symmetric function
specialises to the chromatic polynomial $\chi_{G}(t)$, which counts the number
of proper $t$-colourings $\kappa:G\to[t]$, at $x_{1}=\dots=x_{t}=1$ and
$x_{j}=0$ for $j>t$, and the chromatic polynomial of a simple graph $G$ is
equal to $t(t-1)^{n-1}$ if and only if $G$ is a tree on $n$ vertices. Some
families of trees known to be distinguished by the chromatic symmetric
function include all caterpillars [31] and all starlike trees [32].

We will now show that for integer vertex-weighted forests, the weighted
Laplacian characteristic polynomial can be recovered from the chromatic
symmetric function.

######  Theorem 8.5.

Let $(F,\upsilon)$ be an integer vertex-weighted forest. Then

$P_{(F,\upsilon)}(t)=\varphi(X_{(F,\upsilon)}),$

where $\varphi$ is the algebra homomorphism

$\displaystyle\varphi:\operatorname{Sym}$ $\displaystyle\to\mathbb{R}[t]$
$\displaystyle p_{\alpha}$
$\displaystyle\mapsto\left(\prod_{i=1}^{\ell(\alpha)}\alpha_{i}\right)t^{\ell(\alpha)}.$

###### Proof.

We will proceed by induction on the number of edges of $F$. If $F$ has no
edges and its vertex weights under $\upsilon$ are given in weakly decreasing
order by the partition $\alpha$, then the chromatic symmetric function of
$(F,\upsilon)$ is exactly the power sum symmetric function $p_{\alpha}$, e.g.
by [20, Section 3]. Moreover, since $F$ has no edges, the combinatorial
Laplacian $L_{F}$ is just the zero matrix. Therefore,

$P_{(F,\upsilon)}(t)=\det(tW_{\upsilon})=\left(\prod_{v\in
V}\upsilon(v)\right)t^{|F|}=\left(\prod_{i=1}^{\ell(\alpha)}\alpha_{i}\right)t^{\ell(\alpha)}=\varphi(X_{(F,\upsilon)}).$

For the inductive step, assume $F$ has at least one edge $e$. It is not a
loop, as $F$ is a forest. Since $(F-e,\upsilon)$ and $(F/e,\upsilon/e)$ are
both integer vertex-weighted forests with strictly fewer edges, we have by the
inductive hypothesis and the deletion-contraction relations in Theorem 4.4
(recalling that for vertex-weighted graphs we treat all edge weights as being
$1$) and Theorem 8.2 that

$P_{(F,\upsilon)}(t)=P_{(F-e,\upsilon)}(t)-P_{(F/e,\upsilon/e)}(t)=\varphi(X_{(F-e,\upsilon)})-\varphi(X_{(F/e,\upsilon/e)})=\varphi(X_{(F,\upsilon)}),$

as claimed. ∎

An (unweighted) simple graph $G$ is said to be determined by its combinatorial
Laplacian spectrum if any other simple graph with the same combinatorial
Laplacian spectrum must be isomorphic. From Theorem 8.5, we can deduce the
following.

######  Corollary 8.6.

If an unweighted tree $T$ is determined by its combinatorial Laplacian
spectrum, then it is also distinguished by the chromatic symmetric function.

###### Proof.

Suppose $T^{\prime}$ is another unweighted simple graph with the same
chromatic symmetric function $X_{T}=X_{T^{\prime}}$. Then $T^{\prime}$ must be
a tree. By Theorem 8.5,

$P_{T}(t)=\varphi(X_{T})=\varphi(X_{T^{\prime}})=P_{T^{\prime}}(t),$

so $T$ and $T^{\prime}$ have the same combinatorial Laplacian spectrum. Since
$T$ is determined by its combinatorial Laplacian spectrum, any such
$T^{\prime}$ must be isomorphic to $T$, and so $T$ is distinguished by the
chromatic symmetric function. ∎

There has been a large body of work on trees determined by their combinatorial
Laplacian spectra, partly due to the interest generated by the survey paper of
van Dam and Haemers [21], which asked more generally, which graphs are
determined by their spectra for various matrices associated with a graph. In
their concluding remarks [21, Section 8], they noted that resolving the
question for general graphs seemed out of reach, and proposed the more
tractable problem of classifying which trees are determined by their spectra.

Various families of caterpillars [3, 6, 10, 28, 30, 38, 41], including paths
[21], and all starlike trees [36] are known to be determined by their
combinatorial Laplacian spectra. Some families of trees which are determined
by their combinatorial Laplacian spectra but not previously known to be
distinguished by the chromatic symmetric function are described next.

######  Corollary 8.7.

The following unweighted trees are distinguished by the chromatic symmetric
function:

  1. (i)

Trees $B^{a}_{n}$ with a central vertex adjacent to $a$ vertices, each of
which is joined by pendant edges to $n-1$ other vertices, for $n=3$ with
$a\geq 1$, as well as for $n\geq a^{2}\geq 1$.

  2. (ii)

Trees $h_{m,n}^{a}$ obtained by joining by edges a vertex to an endpoint of
each of three paths on $a$, $m$ and $n$ vertices, respectively, and adding a
pendant edge to each vertex of the path on $a$ vertices.

  3. (iii)

Trees $H_{m,n}^{a}$ obtained by adding a pendant edge to the vertex on the
path on $a$ vertices furthest from the initial vertex in $h_{m,n}^{a}$, for
$a,m,n\geq 1$.

  4. (iv)

Trees $i_{n}$ obtained from a path on $n$ vertices by joining an endpoint of a
unique path on $2$ vertices to each vertex of the path on $n$ vertices, as
well as to both endpoints of the path on $n$ vertices (with repetition), for
$n\geq 1$.

  5. (v)

Trees $M_{m,n}^{a,b}$ obtained by joining by edges one endpoint of an edge to
an endpoint of each of two paths on $a$ and $m$ vertices, and the other
endpoint of the edge to an endpoint of each of two paths on $b$ and $n$
vertices, for $a\geq m\geq 1$, $b\geq n\geq 1$, $a\geq b$ and
$(a,b,m,n)\neq(m+2n+1,m+n+1,m,n),(b+2n+2,b,b+n,n)$.

  6. (vi)

Trees $T_{\ell,m,n}^{a}$ obtained by joining by edges a vertex to an endpoint
of each of three paths on $\ell$, $m$, and $n$ vertices, and adding two
pendant edges to the opposite endpoints of the first $a$ paths, for
$\ell,m,n\geq 1$ and $1\leq a\leq 3$.

  7. (vii)

Trees $y_{n}$ obtained by adding a pendant edge to each vertex of degree $2$
in $i_{n}$, for $n\geq 1$.

  8. (viii)

Trees $Y_{n}$ obtained by adding a pendant edge to each vertex of the initial
path in $y_{n}$, for $n\geq 1$.

  9. (iv)

Trees $Z_{n}$ obtained by adding a pendant edge to each vertex of degree $3$
in $Y_{n}$, for $n\geq 1$.

###### Proof.

The given families of trees are shown to be determined by their combinatorial
Laplacian spectra in [1, Theorem 11], [28, Theorem 3.2.4], [28, Theorem
3.2.1], [28, Theorem 3.3.2], [48, Theorem 3.1], [47, Theorem 3.2], [28,
Theorem 3.4.2], [50, Theorem 2.1] and [28, Theorem 3.4.4], respectively. By
Corollary 8.6, they are distinguished by the chromatic symmetric function. ∎

######  Example 8.8.

By Corollary 8.7, the following trees are all distinguished by the chromatic
symmetric function.

$B^{2}_{4}$$h_{3,3}^{2}$$H_{3,3}^{2}$$i_{3}$$M_{2,1}^{2,2}$$T_{2,2,4}^{2}$$y_{3}$$Y_{3}$$Z_{3}$

Unfortunately, only studying the combinatorial Laplacian spectra of trees is
not sufficient to resolve Conjecture 8.4, as there exist infinitely many pairs
of nonisomorphic trees with the same combinatorial Laplacian spectrum,
including pairs consisting of a caterpillar and a tree that is not a
caterpillar [41]. An even stronger negative result due to McKay in [33,
Corollary 4.4] states that the proportion of trees on $n$ vertices that are
determined by their combinatorial Laplacian spectra goes to zero as $n$ goes
to infinity. (Actually, McKay’s result stated that the proportion goes to zero
for trees determined by the adjacency spectra of their line graphs, which is
equivalent, since for any tree $T$ the adjacency matrix of its line graph can
be shown to equal to $K_{T}-2I$, where $K_{T}$ is the edge Laplacian of $T$ in
a certain basis.)

However, Theorem 8.5 does give insight into what information is captured by
the chromatic symmetric function of a tree. It may also be worthwhile to study
constructions of nonisomorphic trees with the same combinatorial Laplacian
spectrum, either to search for counterexamples of the conjecture, or to
understand the properties of possible counterexamples. Some relevant
constructions can be found in [33, Theorem 4.2] and [48, Theorem 3.1].

##  9\. Acknowledgments

The authors would like to thank Will Evans and Joel Friedman for helpful
conversations, Mike Huang for helping translate Chinese-language articles and
Fei Wen for sending the authors a copy of [47].

## References

  * [1] G. Aalipour, S. Akbari and N. Shajari, Laplacian spectral characterization of two families of trees, _Linear Multilinear Algebra_ 62 (7), 965-977 (2014).
  * [2] J. Aliste-Prieto, L. Crew, S. Spirkl and J. Zamora, A vertex-weighted Tutte symmetric function, and constructing graphs with equal chromatic symmetric function, _Electron. J. Comb._ 28 (2), P2.1 33pp (2021).
  * [3] M. Ajmal, X.-W. Cao, M. Salman, J.-B. Liu and M. Ur Rehman, A special class of triple starlike trees characterized by Laplacian spectrum, _AIMS Math._ 6 (5), 4394–4403 (2021).
  * [4] J. A. Bondy, A graph reconstructor’s manual, Surveys in Combinatorics, 1991 (A. D. Keedwell, ed.), _Cambridge University Press_ , 221–252 (1991).
  * [5] B. Bollobás, Modern Graph Theory, _Springer Science & Business Media_, (1998).
  * [6] R. Boulet, The centipede is determined by its Laplacian spectrum, _C. R. Math. Acad. Sci. Paris_ 346 (13)–(14), 711–716 (2008).
  * [7] G. Bravo-Hermsdorff and L. M. Gunderson, A unifying framework for spectrum-preserving graph sparsification and coarsening, _Adv. Neural Inf. Process. Syst._ 32, (2019).
  * [8] R. L. Brooks, C. A. B. Smith, A. H. Stone and W. T. Tutte, The dissection of rectangles into squares, _Duke Math. J._ 7 (1), 312–340 (1940).
  * [9] T. Brylawski, Intersection theory for graphs, _J. Combin. Theory Ser. B_ 30 (2), 233–246 (1981).
  * [10] C.-J. Bu, J. Zhou, H.-B. Li, Spectral determination of some chemical graphs, _Filomat_ 26 (6), 1123–1131 (2012).
  * [11] S. Butler, Interlacing for weighted graphs using the normalized Laplacian, _Electron. J. Linear Algebra_ 16, 90–98 (2007).
  * [12] C. Cai, D. Wang and Y. Wang, Graph coarsening with neural networks, _Int. Conf. Learn. Represent._ , (2021).
  * [13] S. Chaiken, A combinatorial proof of the all minors matrix tree theorem, _SIAM J. Alg. Disc. Meth._ 3 (3), 319–329 (1982).
  * [14] G. Chen, G. Davis, F. Hall, Z. Li, K. Patel and M. Stewart, An interlacing result on normalized Laplacians, _SIAM J. Discrete Math._ 18 (2), 353–361 (2004).
  * [15] J. Cheeger, A lower bound for the smallest eigenvalue of the Laplacian, Problems in Analysis (R. C. Gunning, ed.), _Princeton University Press_ , 195–199 (1970).
  * [16] S. V. Chmutov, S. V. Duzhin and S. K. Lando, Vassiliev knot invariants. III. Forest algebra and weighted graphs, _Adv. in Soviet Math._ 21, 135–146 (1994).
  * [17] F. R. K. Chung, Spectral Graph Theory, American Mathematical Society, edition 2, (1997).
  * [18] F. R. K. Chung and R. P. Langlands, A combinatorial Laplacian with vertex weights, _J. Combin. Theory Ser. A_ 75 (2), 316–327 (1996).
  * [19] G. Coutinho, R. Grandsire and C. Passos, Colouring the normalized Laplacian, _Electron. Notes Theor. Comput. Sci._ 346, 345–354, (2019).
  * [20] L. Crew and S. Spirkl, A deletion-contraction relation for the chromatic symmetric function, _European J. Combin._ 89, 103–143 (2020).
  * [21] E. R. van Dam and W. H. Haemers, Which graphs are determined by their spectrum?, _Linear Algebra Appl._ 373, 241–272 (2003).
  * [22] J. Dodziuk, Difference equations, isoperimetric inequality and transience of certain random walks, _Trans. Amer. Math. Soc._ 284 (2), 787–794 (1984).
  * [23] J. Friedman and J.-P. Tillich, Calculus on graphs, arXiv:cs/0408028v2
  * [24] R. Grone, R. Merris and V. S. Sunder, The Laplacian spectrum of a graph, _SIAM J. Matrix Anal. Appl._ 11 (2), 218–238 (1990).
  * [25] C. D. Godsil and M. W. Newman, Eigenvalue bounds for independent sets, _J. Combin. Theory Ser. B_ 98 (4), 721–734 (2008).
  * [26] D. Horak and J. Jost, Spectra of combinatorial Laplace operators on simplicial complexes, _Adv. Math._ 244, 303–336 (2013).
  * [27] G. Kirchhoff, Uber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird, _Ann. Phys. Chem._ 148 (12), 497–508 (1847).
  * [28] J.-F. Li, Some trees determined by their Laplacian spectrum, master’s thesis, Hunan Normal University (2008).
  * [29] L. Lovász, Combinatorial Problems and Exercises, _North-Holland_ , edition 2, (1993).
  * [30] P.-L. Lu and X.-G. Liu, Laplacian spectral characterization of some double starlike trees, _Journal of Harbin Engineering University_ 37 (2), 242–247 (2016).
  * [31] M. Loebl, J.-S. Sereni, Isomorphism of weighted trees and Stanley’s isomorphism conjecture for caterpillars, _Ann. Inst. Henri Poincaré Comb. Phys. Interact._ 6 (3), 357–384 (2019).
  * [32] J. Martin, M. Morin and J. Wagner, On distinguishing trees by their chromatic symmetric functions, _J. Combin. Theory Ser. A_ 115 (2), 237–253 (2008).
  * [33] B. D. McKay, On the spectral characterisation of trees, _Ars Combin._ 3, 219–232 (1977).
  * [34] B. Mohar, Eigenvalues, diameter, and mean distance in graphs, _Graphs Combin._ 7, 53–64 (1991).
  * [35] S. D. Noble and D. J. A. Welsh, A weighted graph polynomial from chromatic invariants of knots, _Ann. Inst. Fourier (Grenoble)_ 49 (3), 1057–1087 (1999).
  * [36] G. R. Omidi and K. Tajbakhsh, Starlike trees are determined by their Laplacian spectrum, _Linear Algebra Appl._ 422 (2)–(3), 654–658 (2007).
  * [37] I. Sarmiento, The polychromate and a chord diagram polynomial, _Ann. Comb._ 4, 227–236 (2000).
  * [38] X.-L. Shen and Y.-P. Hou, Some trees are determined by their Laplacian spectra, _J. Nat. Sci. Hunan Norm. Univ._ 29 (1), 21–24, 46 (2006).
  * [39] R. L. Smith, Some interlacing properties of the Schur complement of a Hermitian matrix, _Linear Algebra Appl._ 177, 137–144 (1992).
  * [40] D. A. Spielman, The adjacency matrix and the $n$th eigenvalue, https://www.cs.yale.edu/homes/spielman/561/2012/lect03-12.pdf
  * [41] Z. Stanić, On determination of caterpillars with four terminal vertices by their Laplacian spectrum, _Linear Algebra Appl._ 431 (11), 2035–2048 (2009).
  * [42] R. P. Stanley, Acyclic orientations of graphs, _Discrete Math._ 5 (2), 171–198 (1973).
  * [43] R. P. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, _Adv. Math._ 111 (1), 166–194 (1995).
  * [44] R. P. Stanley, Graph colorings and related symmetric functions: ideas and applications. A description of results, interesting applications, & notable open problems, _Discrete Math._ 193 (1)–(3), 267–286 (1998).
  * [45] W. T. Tutte, A contribution to the theory of chromatic polynomials, _Canad. J. Math._ 6, 80–91 (1954).
  * [46] W. T. Tutte, All the king’s horses (a guide to reconstruction), Graph Theory and Related Topics (J. A. Bondy and U. S. R. Murty, ed.), _Academic Press_ , 15–33 (1979).
  * [47] F. Wen and Q.-X. Huang, On the Laplacian spectral characterization of the generalized $T$-shape trees, _Ars Combin._ 112, 419–431 (2013).
  * [48] F. Wen, Q.-X. Huang, X.-Y. Huang and F.-J. Liu, On the Laplacian spectral characterization of $\Pi$-shape trees, _Indian J. Pure Appl. Math._ 49, 397–411 (2018).
  * [49] S. Xu, J. Fang and X.-Y. Liu, Weighted Laplacian and its theoretical applications, _IOP Conf. Ser.: Mater. Sci. Eng._ 768, 072032 (2020).
  * [50] T. Zhang and Y.-Q. Bai, Two families of trees determined by their Laplacian spectrum, _Oper. Res. Trans._ 21 (1), 103–110 (2017).