# On average hitting time and Kemeny’s constant for weighted trees

Ji Zeng Department of Mathematics, University of California at San Diego, La
Jolla, CA, 92093 USA. Partly supported by NSF grant DMS-1800746. Email:
<EMAIL_ADDRESS>
###### Abstract

For a connected graph $G$, the average hitting time $\alpha(G)$ and the
Kemeny’s constant $\kappa(G)$ are two similar quantities, both measuring the
time for the random walk on $G$ to travel between two randomly chosen
vertices. We prove that, among all weighted trees whose edge-weights form a
fixed multiset, $\alpha$ is maximized by a special type of ”polarized” paths
and is minimized by a unique weighted star graph. We also give a short proof
of the fact that, among all simple trees of a fixed size, $\kappa$ is
maximized by the path and is minimized by the star graph. Our proofs are based
on the forest formulas for the average hitting time and the Kemeny’s constant.

##  1 Introduction

In this paper, we consider random walks on graphs whose edges are assigned
with positive weights. For the random walk on a connected weighted graph
$G=(V,E)$, the transition probability from vertex $u$ to vertex $v$ is
proportional to the weight of the edge $uv$ (see [8]Section 1.4). The _hitting
time_ $H_{G}(u,v)$ is the expected number of steps to walk from the vertex $u$
to the vertex $v$. We shall study the _average hitting time_ , defined as the
arithmetic mean of all hitting times of $G$,

$\displaystyle\alpha(G):=\frac{1}{|V|^{2}}\sum_{u\in V}\sum_{v\in
V}H_{G}(u,v).$

The _stationary distribution_ of $G$ is a unique probability vector $\pi_{G}$
satisfying $\pi_{G}^{T}=\pi_{G}^{T}P_{G}$, where $P_{G}$ is the transition
probability matrix for the random walk on $G$ (see [8]Exercise 2.1). The
_Kemeny’s constant_ of $G$, similar to $\alpha(G)$ but more complicated, is
defined as

$\displaystyle\kappa(G):=\sum_{v\in V}H_{G}(u,v)\pi_{G}(v).$

In words, $\kappa(G)$ is the expected time to travel from a fixed starting
vertex $u$ to a random destination sampled from the stationary distribution.
Formally, this definition of $\kappa(G)$ depends on the choice of $u$, but
Kemeny and Snell [5] observed the surprising fact that the value $\kappa(G)$
is independent of $u$ (see [8]Exercise 2.48). The Kemeny’s constant has
applications in network theory([6]), robotics([9]) and chemistry([7]).

The original motivation of this paper is to prove the following.

######  Theorem 1.1.

Among all simple (i.e. unweighted) trees of a fixed size, the path has the
largest $\alpha$ and $\kappa$, and the star graph has the smallest $\alpha$
and $\kappa$.

However, our methods generalize to a weighted setting: For a multiset (i.e.
set with multiplicities) $W$ of positive numbers, we let $\mathcal{T}_{W}$ be
the collection of all weighted trees $T$ such that $W$ equals
$\\{\omega(e)|e\in E(T)\\}$ as a multiset. Here, $\omega(e)$ denotes the
weight of the edge $e$. See Figure 1 for an example of $\mathcal{T}_{W}$.
Notice that when $W$ only consists of multiple $1$’s, $\mathcal{T}_{W}$ is the
collection of all simple trees of a fixed size. We will investigate which
elements in $\mathcal{T}_{W}$ maximize or minimize $\alpha$ and $\kappa$ for a
general $W$.

Clearly, there’s a unique element $S_{W}$ in $\mathcal{T}_{W}$ whose
underlying graph structure is a star graph. On the other hand, there are many
weighted paths in $\mathcal{T}_{W}$ due to various ways to assign the edge-
weights. We care about a special type of ”polarized” paths: For a weighted
path $P=v_{1}v_{2}\dots v_{n}$, we denote its edges as $e_{i}:=v_{i}v_{i+1}$
and define $c(e_{i}):=\min\\{i,n-i\\}$ for $i\in[n-1]$, then we say $P$ is
_polarized_ provided $\omega(e_{i})\geq\omega(e_{j})$ whenever $c(e_{i})\leq
c(e_{j})$.

Intuitively, $c(e_{i})$ measures how centrally $e_{i}$ is located in $P$: We
regard $e_{1}$ and $e_{n-1}$, the edges containing the leaves of $P$, as the
least central edges hence they have the smallest $c(e_{1})=c(e_{n-1})=1$; We
regard $e_{2}$ and $e_{n-2}$ as the second least central edges hence they have
the second smallest $c(e_{2})=c(e_{n-2})=2$ and so on; We regard the middle
edge $e_{\lceil\frac{n-1}{2}\rceil}$ as the most central edge hence it has the
largest $c(e_{\lceil\frac{n-1}{2}\rceil})=\lceil\frac{n-1}{2}\rceil$. So, in
words, a weight path is polarized if edges located more centrally are assigned
with smaller weights. See Figure 1 for an illustration.

Figure 1: From left to right: a weighted tree in $\mathcal{T}_{W}$ where
$W=\\{7,5,4,2,2,1\\}$ and the numbers indicate edge-weights; the weighted star
$S_{W}$; a polarized path in $\mathcal{T}_{W}$ where $c(e_{1})=c(e_{6})=1$,
$c(e_{2})=c(e_{5})=2$, and $c(e_{3})=c(e_{4})=3$.

######  Theorem 1.2.

In $\mathcal{T}_{W}$, where $W$ is a multiset of positive numbers, the
polarized paths are the elements that maximize $\alpha$; and $S_{W}$ is the
unique element that minimizes $\alpha$.

By a slight modification of the proof of Theorem 1.2, we obtain a similar
result for the Kemeny’s constant.

######  Theorem 1.3.

In $\mathcal{T}_{W}$, where $W$ is a multiset of positive numbers, the
elements that maximize $\kappa$ are among the weighted paths; and $S_{W}$ is
the unique element that minimizes $\kappa$.

In Theorem 1.3, we fail to characterize which elements among the weighted
paths in $\mathcal{T}_{W}$ maximize $\kappa$ for a general $W$. In Remark 5.2,
we give an example where the $\kappa$-maximizing path isn’t polarized for some
$\mathcal{T}_{W}$. Nevertheless, there’s only one simple path with a given
size, so Theorem 1.1 is just a corollary of Theorem 1.2 and Theorem 1.3.

We note that, among all simple trees of a fixed size, Ciardo et al. [3]
previously proved the star graph minimizes $\kappa$; and recently, Faught et
al. [4] proved the path maximizes $\kappa$. However, the discovery of our
results is independent of their ideas. Our proofs are based on the forest
formulas for the average hitting time and the Kemeny’s constant which we will
introduce in Section 2.

There are also formulas that express the the average hitting time and the
Kemeny’s constant through eigenvalues of graph-theoretic Laplacian matrices,
see Remark 5.1. Consequently, our results can be interpreted as extremal
characterizations of the Laplacian spectra of weighted trees.

During our proofs, we introduce a type of operations on trees called ”edge-
transfers”. The edge-transfer operations induce a partial order $\succeq$ on
the set of simple trees of a fixed size. We observed similarity between this
partial order and another partial order previously defined by Sidorenko [10]
using graph homomorphisms, see Remark 5.3.

##  2 Preliminaries

Let $G=(V,E)$ be a connected weighted graph without loops. For each edge
$e=uv\in E$, we denote its _weight_ by $\omega(e)=\omega(uv)>0$. It’s required
that $\omega(e)=0$ for $e\not\in E$. For any subgraph $H$ of $G$, we define
its weight by

$\displaystyle\omega(H)$ $\displaystyle=\prod_{e\in E(H)}\omega(e).$

For each vertex $u$, we define its _degree_ by $d_{G}(u):=\sum_{v\in
V}\omega(uv)$. The _volume_ of a subset $U\subset V$ refers to the quantity
$\text{vol}_{G}(U):=\sum_{u\in U}d_{G}(u)$. The volume of a subgraph $H\subset
G$ refers to the volume of $V(H)\subset V$ and is denoted by
$\text{vol}_{G}(H)$. We remind our readers that in general
$\text{vol}_{G}(H)\neq\text{vol}_{H}(H)$. The _size_ of $G$ refers to the
number of its vertices and is denoted by $|G|$.

A _tree_ is a graph that’s acyclic and connected. A _$2$ -forest_ is a graph
that’s acyclic and has two connected components. A subgraph $H\subset G$ is
said to be _spanning_ if $V(H)=V(G)$. We use $\mathbb{F}_{1}(G)$ to denote the
set of all spanning sub-trees of $G$, and use $\mathbb{F}_{2}(G)$ to denote
the set of all spanning sub-$2$-forests of $G$.

We shall use the next two lemmas in our proofs. They express $\alpha(G)$ and
$\kappa(G)$ as weighted enumerations of elements in $\mathbb{F}_{1}(G)$ and
$\mathbb{F}_{2}(G)$. For simplicity of presentation, we define the quantity

$\displaystyle\tau(G):=\sum_{T\in\mathbb{F}_{1}(G)}\omega(T);$

And we define for any $2$-forest $F\in\mathbb{F}_{2}(G)$, whose two components
denoted as $T_{1}$ and $T_{2}$,

$\displaystyle S(F):=|T_{1}||T_{2}|\qquad\text{and}\qquad
V_{G}(F):=\text{vol}_{G}(T_{1})\text{vol}_{G}(T_{2}).$

######  Lemma 2.1 ([2]Corollary 4.5).

For a connected weighted graph $G$, we have

$\displaystyle\frac{|G|}{\text{vol}_{G}(G)}\alpha(G)=\frac{1}{|G|\tau(G)}\sum_{F\in\mathbb{F}_{2}(G)}S(F)\omega(F).$

######  Lemma 2.2 ([2]Corollary 4.4).

For a connected weighted graph $G$, we have

$\displaystyle\kappa(G)=\frac{1}{\text{vol}_{G}(G)\tau(G)}\sum_{F\in\mathbb{F}_{2}(G)}V_{G}(F)\omega(F).$

We remark that Lemma 2.2 is also established in [1] prior to [2].

##  3 Proof of Theorem 1.2

We consider the following operation on a tree $T$: Take two adjacent edges
$e_{1}=v_{1}v_{2}$ and $e_{2}=v_{2}v_{3}$, and name the component of
$T\backslash\\{e_{1},e_{2}\\}$ containing $v_{i}$ as $T_{i}$, for $i=1,2,3$.
If $|T_{1}|>|T_{2}|$, we construct another tree $T^{\prime}$ from $T$ by
deleting the edge $e_{2}$ and adding an edge $e_{2}^{\prime}=v_{1}v_{3}$ with
weight $\omega(e_{2}^{\prime}):=\omega(e_{2})$. In this case we say _$T$ edge-
transfers to $T^{\prime}$ with respect to size_. See Figure 2 for an
illustration.

Figure 2: $T$ edge-transfers to $T^{\prime}$ with respect to size.

######  Lemma 3.1.

If $T$ edge-transfers to $T^{\prime}$ with respect to size, then
$\alpha(T)>\alpha(T^{\prime})$.

###### Proof.

We keep the notations as in the previous paragraph. Since $T$ and $T^{\prime}$
are trees, by definition of $\tau(T)$ and $\tau(T^{\prime})$, we have
$\tau(T)=\omega(T)=\omega(T^{\prime})=\tau(T^{\prime})=:\tau$. It’s also
obvious that $|T|=|T^{\prime}|=:n$ and
$\text{vol}_{T}(T)=\text{vol}_{T^{\prime}}(T^{\prime})=:\text{vol}$.

Notice that for any edge $e\not\in\\{e_{1},e_{2},e_{2}^{\prime}\\}$, the
$2$-forests $T\backslash e$ and $T^{\prime}\backslash e$ give the same
component partition of vertices, that is, two vertices $x,y$ are in the same
component of $T\backslash e$ if and only if they are in the same component of
$T^{\prime}\backslash e$. See Figure 3 for an illustration. So we have
$S(T\backslash e)=S(T^{\prime}\backslash e)$. We also have $\omega(T\backslash
e)=\tau/\omega(e)=\omega(T^{\prime}\backslash e)$. The two $2$-forests
$T\backslash e_{2}$ and $T^{\prime}\backslash e_{2}^{\prime}$ are equal as
graphs, so $S(T\backslash e_{2})=S(T^{\prime}\backslash e^{\prime}_{2})$ and
$\omega(T\backslash e_{2})=\omega(T^{\prime}\backslash
e^{\prime}_{2})=\tau/\omega(e_{2})$. Therefore, the difference between
$\alpha(T)$ and $\alpha(T^{\prime})$ in the formula of Lemma 2.1 is only
contributed by the $2$-forests $T\backslash e_{1}$ and $T^{\prime}\backslash
e_{1}$:

$\displaystyle\frac{n}{\text{vol}}(\alpha(T)-\alpha(T^{\prime}))=\frac{1}{n\omega(e_{1})}(S(T\backslash
e_{1})-S(T^{\prime}\backslash e_{1})).$ (3.1)

Here we used $\omega(T\backslash
e_{1})=\tau/\omega(e_{1})=\omega(T^{\prime}\backslash e_{1})$.

Figure 3: $T\backslash e$ and $T^{\prime}\backslash e$ give the same component
partition of vertices.

The two components of $T\backslash e_{1}$ are $T_{1}$ and $T_{2}\cup T_{3}$
respectively, and the two components of $T^{\prime}\backslash e_{1}$ are
$T_{1}\cup T_{3}$ and $T_{2}$ respectively. Hence we have

$\displaystyle S(T\backslash e_{1})-S(T^{\prime}\backslash
e_{1})=|T_{1}|(|T_{2}|+|T_{3}|)-(|T_{1}|+|T_{3}|)|T_{2}|=(|T_{1}|-|T_{2}|)|T_{3}|>0,$

since $|T_{1}|>|T_{2}|$ by our assumption of the edge-transfer. This
inequality together with (3.1) concludes $\alpha(T)>\alpha(T^{\prime})$. ∎

Let’s write $T\succeq_{s}T^{\prime}$ if $T^{\prime}$ can be obtained after
applying multiple edge-transfers with respect to size starting with $T$. As a
consequence of Lemma 3.1, the relation $\succeq_{s}$ defines a partial order
on $\mathcal{T}_{W}$.

######  Lemma 3.2.

For any multiset $W$ of positive numbers, the maximal elements of the poset
$(\mathcal{T}_{W},\succeq_{s})$ are the weighted paths, and the minimal
element of $(\mathcal{T}_{W},\succeq_{s})$ is the weighted star $S_{W}$.

###### Proof.

Suppose $T^{\prime}\in\mathcal{T}_{W}$ is not a weighted path, then
$T^{\prime}$ has a vertex $v$ with at least three vertices $u_{1},u_{2},u_{3}$
adjacent to $v$. Let $T^{\prime}_{i}$ be the component of
$T^{\prime}\backslash vu_{i}$ containing $u_{i}$, for $i=1,2,3$. Without loss
of generality, we can assume $|T^{\prime}_{1}|\geq|T^{\prime}_{2}|$. Now, we
construct another tree $T$ in $\mathcal{T}_{W}$ from $T^{\prime}$ by deleting
the edge $vu_{3}$ and adding the edge $u_{2}u_{3}$ with weight
$\omega(u_{2}u_{3}):=\omega(vu_{3})$. Then $T$ edge-transfers to $T^{\prime}$
with respect to size. Indeed, in $T$, if we name $v_{1}:=v$, $v_{2}:=u_{2}$,
$v_{3}=u_{3}$, $e_{1}:=v_{1}v_{2}$, $e_{2}:=v_{2}v_{3}$ and the component of
$T\backslash\\{e_{1},e_{2}\\}$ containing $v_{i}$ as $T_{i}$, we have
$|T_{1}|\geq|T^{\prime}_{1}\cup\\{v\\}|>|T^{\prime}_{1}|\geq|T^{\prime}_{2}|=|T_{2}|$.
So we can perform an edge-transfer on $T$, taking $e_{1},e_{2}$ as the two
adjacent edges, to obtain $T^{\prime}$. By Lemma 3.1, $T$ and $T^{\prime}$ are
not isomorphic, so $T^{\prime}$ isn’t a maximal element of
$(\mathcal{T}_{W},\succeq_{s})$. On the other hand, since every vertex of a
weight path $P\in\mathcal{T}_{W}$ has at most two neighbors, $P$ cannot be a
result of an edge-transfer, so $P$ is maximal with respect to $\succeq_{s}$.

Suppose $T\in\mathcal{T}_{W}$ is not $S_{W}$, then $T$ contains a path of
length three which we can write as $v_{0}v_{1}v_{2}v_{3}$. Let $C_{i}$ be the
component of $T\backslash v_{1}v_{2}$ containing $v_{i}$, for $i=1,2$. Without
loss of generality, we can assume $|C_{1}|\geq|C_{2}|$. Then we can perform an
edge-transfer with respect to size on $T$ to obtain another tree $T^{\prime}$.
Indeed, if we name $e_{1}:=v_{1}v_{2}$, $e_{2}:=v_{2}v_{3}$ and the component
of $T\backslash\\{e_{1},e_{2}\\}$ containing $v_{i}$ as $T_{i}$, we have
$|T_{1}|=|C_{1}|\geq|C_{2}|>|C_{2}\backslash\\{v_{3}\\}|\geq|T_{2}|$. By Lemma
3.1, $T$ and $T^{\prime}$ are not isomorphic, so $T^{\prime}$ isn’t a minimal
element of $(\mathcal{T}_{W},\succeq_{s})$. On the other hand, it’s easy to
check that $S_{W}$ is minimal with respect to $\succeq_{s}$. ∎

###### Proof of Theorem 1.2.

As a consequence of Lemma 3.1 and Lemma 3.2, the elements that maximize
$\alpha$ are among the weighted paths in $\mathcal{T}_{W}$, and $S_{W}$ is the
unique element that minimizes $\alpha$.

Let $P=v_{1}v_{2}\dots v_{n}$, where $n=|W|+1$, be a weighted path and name
the edges $e_{i}:=v_{i}v_{i+1}$ for $i\in[n-1]$. We now assign edge-weights
from $W$ to the $e_{i}$’s to maximize $\alpha(P)$. Since $S(P\backslash
e_{i})=i(n-i)$ is independent of the choice of edge-weights, to maximize
$\alpha(P)$ in the formula of Lemma 2.1, we need to assign the edge-weights
such that larger $S(P\backslash e_{i})$ is paired with larger
$\omega(P\backslash e_{i})$. Since $\omega(P\backslash
e_{i})=\omega(e_{i})^{-1}(\prod_{w\in W}w)$, we should pair larger
$S(P\backslash e_{i})$ with smaller $\omega(e_{i})$. Recall from Section 1
that $c(e_{i})=\min\\{i,n-i\\}$. We can check $c(e_{i})>c(e_{j})$ if and only
if $S(P\backslash e_{i})>S(P\backslash e_{j})$. Hence, in order to maximize
$\alpha(P)$, the edges with larger $c(e_{i})$ should have smaller
$\omega(e_{i})$, meaning that $P$ has to be polarized.

Now it suffices to show all polarized paths in $\mathcal{T}_{W}$ have the same
$\alpha$. To see this, we write $W=\\{w_{1},w_{2},\dots,w_{n}\\}$ such that
$w_{i}\geq w_{i+1}$ for $i\in[n-1]$. We also partition the edge set of $P$
into $E_{i}:=\\{e_{i},e_{n-i}\\}$ for $i=1,\dots,\lceil\frac{n-1}{2}\rceil$.
Since $e\in E_{i}$ if and only if $c(e)=i$, to generate all polarized paths in
$\mathcal{T}_{W}$, it suffices to assign the weights $w_{2i-1}$ and $w_{2i}$
to edges in $E_{i}$ for all $i$. Because $S(P\backslash e_{i})=S(P\backslash
e_{n-i})$, the two possible assignments for $E_{i}$,
$(\omega(e_{i}),\omega(e_{n-i}))=(w_{2i-1},w_{2i})$ or
$(\omega(e_{i}),\omega(e_{n-i}))=(w_{2i},w_{2i-1})$, won’t affect $\alpha$ in
the formula of Lemma 2.1. Hence, all weighted paths generated by this process
have the same $\alpha$. ∎

##  4 Proof of Theorem 1.3

We consider another operation on a tree $T$: Take two adjacent edges
$e_{1}=v_{1}v_{2}$ and $e_{2}=v_{2}v_{3}$, and name the component of
$T\backslash\\{e_{1},e_{2}\\}$ containing $v_{i}$ as $T_{i}$, for $i=1,2,3$.
If $\text{vol}_{T_{1}}(T_{1})>\text{vol}_{T_{2}}(T_{2})$, we construct another
tree $T^{\prime}$ from $T$ by deleting the edge $e_{2}$ and adding an edge
$e_{2}^{\prime}=v_{1}v_{3}$ with weight
$\omega(e_{2}^{\prime}):=\omega(e_{2})$. In this case we say _$T$ edge-
transfers to $T^{\prime}$ with respect to volume_.

######  Lemma 4.1.

If $T$ edge-transfers to $T^{\prime}$ with respect to volume, then
$\kappa(T)>\kappa(T^{\prime})$.

###### Proof.

We keep the notations as in the previous paragraph. Same as in the proof of
Lemma 3.1, we have
$\tau(T)=\omega(T)=\omega(T^{\prime})=\tau(T^{\prime})=:\tau$ and
$\text{vol}_{T}(T)=\text{vol}_{T^{\prime}}(T^{\prime})=:\text{vol}$.

We have $V_{T}(T\backslash e)=V_{T^{\prime}}(T^{\prime}\backslash e)$ for any
edge $e\not\in\\{e_{1},e_{2},e_{2}^{\prime}\\}$. Indeed, denoting the
component of $T\backslash e$ ($T^{\prime}\backslash e$ resp.) containing
$v_{1}$ as $T_{1}$ ($T_{1}^{\prime}$ resp.), and the other component as
$T_{2}$ ($T^{\prime}_{2}$ resp.), we must have $T_{2}=T_{2}^{\prime}$ as
graphs. See Figure 3 for an illustration. This implies

$\displaystyle\text{vol}_{T}(T_{2})=\text{vol}_{T_{2}}(T_{2})+\omega(e)=\text{vol}_{T^{\prime}_{2}}(T^{\prime}_{2})+\omega(e)=\text{vol}_{T^{\prime}}(T^{\prime}_{2}),$

and
$\text{vol}_{T}(T_{1})=\text{vol}-\text{vol}_{T}(T_{2})=\text{vol}-\text{vol}_{T^{\prime}}(T^{\prime}_{2})=\text{vol}_{T^{\prime}}(T^{\prime}_{1})$.
So $V_{T}(T\backslash e)=V_{T^{\prime}}(T^{\prime}\backslash e)$ as claimed.
We also have $\omega(T\backslash e)=\tau/\omega(e)=\omega(T^{\prime}\backslash
e)$. A similar argument gives us $V_{T}(T\backslash
e_{2})=V_{T^{\prime}}(T^{\prime}\backslash e^{\prime}_{2})$ and
$\omega(T\backslash
e_{2})=\tau/\omega(e_{2})=\tau/\omega(e^{\prime}_{2})=\omega(T^{\prime}\backslash
e^{\prime}_{2})$. Therefore, the difference between $\kappa(T)$ and
$\kappa(T^{\prime})$ in the formula of Lemma 2.2 is only contributed by the
$2$-forests $T\backslash e_{1}$ and $T^{\prime}\backslash e_{1}$:

$\displaystyle\kappa(T)-\kappa(T^{\prime})=\frac{1}{\text{vol}\cdot\omega(e_{1})}(V_{T}(T\backslash
e_{1})-V_{T^{\prime}}(T^{\prime}\backslash e_{1})).$ (4.1)

Here we used $\omega(T\backslash
e_{1})=\tau/\omega(e_{1})=\omega(T^{\prime}\backslash e_{1})$.

Now we write $\omega_{1}:=\omega(e_{1})$ and
$\omega_{2}:=\omega(e_{2})=\omega(e^{\prime}_{2})$. The two components of
$T\backslash e_{1}$ are $T_{1}$ and $T_{2}\cup T_{3}$ respectively. Notice
that $d_{T}(v_{1})=d_{T_{1}}(v_{1})+\omega_{1}$ and $d_{T}(v)=d_{T_{1}}(v)$
for any $v\neq v_{1}$ in $T_{1}$, we have

$\displaystyle\text{vol}_{T}(T_{1})=\text{vol}_{T_{1}}(T_{1})+\omega_{1}.$

Also notice that $d_{T}(v_{2})=d_{T_{2}}(v_{2})+\omega_{1}+\omega_{2}$,
$d_{T}(v_{3})=d_{T_{2}}(v_{3})+\omega_{2}$, $d_{T}(v)=d_{T_{2}}(v)$ for any
$v\neq v_{2}$ in $T_{2}$, and $d_{T}(v)=d_{T_{3}}(v)$ for any $v\neq v_{3}$ in
$T_{3}$. So we have

$\displaystyle\text{vol}_{T}(T_{2}\cup
T_{3})=\text{vol}_{T_{2}}(T_{2})+\omega_{1}+2\omega_{2}+\text{vol}_{T_{3}}(T_{3}).$

Similarly, the two components of $T^{\prime}\backslash e_{1}$ are $T_{1}\cup
T_{3}$ and $T_{2}$ respectively, and we can check
$\text{vol}_{T^{\prime}}(T_{1}\cup
T_{3})=\text{vol}_{T_{1}}(T_{1})+\omega_{1}+2\omega_{2}+\text{vol}_{T_{3}}(T_{3})$
and $\text{vol}_{T^{\prime}}(T_{2})=\text{vol}_{T_{2}}(T_{2})+\omega_{1}$. So
we have the following computation.

$\displaystyle V_{T}(T\backslash e_{1})-V_{T^{\prime}}(T^{\prime}\backslash
e_{1})$
$\displaystyle=(\text{vol}_{T_{1}}(T_{1})+\omega_{1})(\text{vol}_{T_{2}}(T_{2})+\omega_{1}+2\omega_{2}+\text{vol}_{T_{3}}(T_{3}))$
$\displaystyle\hskip
20.0pt-(\text{vol}_{T_{1}}(T_{1})+\omega_{1}+2\omega_{2}+\text{vol}_{T_{3}}(T_{3}))(\text{vol}_{T_{2}}(T_{2})+\omega_{1})$
$\displaystyle=(\text{vol}_{T_{3}}(T_{3})+2\omega_{2})(\text{vol}_{T_{1}}(T_{1})-\text{vol}_{T_{2}}(T_{2}))>0,$

since $\text{vol}_{T_{1}}(T_{1})>\text{vol}_{T_{2}}(T_{2})$ by our assumption
of the edge-transfer. This inequality together with (4.1) concludes
$\kappa(T)>\kappa(T^{\prime})$. ∎

Let’s write $T\succeq_{v}T^{\prime}$ if $T^{\prime}$ can be obtained after
applying multiple edge-transfers with respect to volume starting with $T$. As
a consequence of Lemma 4.1, the relation $\succeq_{v}$ defines a partial order
on $\mathcal{T}_{W}$.

######  Lemma 4.2.

For any multiset $W$ of positive numbers, the maximal elements of the poset
$(\mathcal{T}_{W},\succeq_{v})$ are the weighted paths, and the minimal
element of $(\mathcal{T}_{W},\succeq_{v})$ is the weighted star $S_{W}$.

We skip the proof of Lemma 4.2 since it’s very similar to the proof of Lemma
3.2.

###### Proof of Theorem 1.3.

This theorem follows directly from Lemma 4.1 and Lemma 4.2. ∎

##  5 Remarks

######  Remark 5.1.

Theorem 1.2 and Theorem 1.3 can be interpreted as extremal characterizations
of the Laplacian spectra for weighted trees in $\mathcal{T}_{W}$. This is
because $\alpha$ and $\kappa$ satisfy the following spectral formulas: For a
connected weighted graph $G$ of size $n$, write the eigenvalues of its
_combinatorial Laplacian matrix_ as
$0=\lambda_{0}<\lambda_{1}\leq\dots\leq\lambda_{n-1}$, and the eigenvalues of
its _normalized Laplacian matrix_ as
$0=\mu_{0}<\mu_{1}\leq\dots\leq\mu_{n-1}$, then we have

$\displaystyle\frac{n}{\text{vol}_{G}(G)}\alpha(G)=\sum_{i=1}^{n-1}\lambda_{i}^{-1}\text{\qquad
and \qquad}\kappa(G)=\sum_{i=1}^{n-1}\mu_{i}^{-1}.$

We refer our readers to [2] for definitions of Laplacian matrices and proofs
of these identities.

######  Remark 5.2.

After Theorem 1.3, it’s natural to ask which weighted paths in
$\mathcal{T}_{W}$ maximize $\kappa$ for a general $W$. For a path
$P=v_{1}v_{2}\dots v_{n}$ in $\mathcal{T}_{W}$, where $n=|W|+1$, if we write
$\omega_{i}:=\omega(v_{i}v_{i+1})$ for $i\in[n-1]$, we can check through the
formula of Lemma 2.2 that the maximization of $\kappa(P)$ is equivalent to the
maximization of

$\displaystyle\sum_{i=1}^{n-1}\sum_{j=1}^{i-1}\sum_{k=i+1}^{n-1}\frac{\omega_{j}\omega_{k}}{\omega_{i}}\text{,
where $\\{\omega_{i}\\}=W$ as multisets.}$

This optimization problem is very different from the trivial one we encounter
in Theorem 1.2. For example, when $W=\\{10,8,1,1,0.1\\}$, $\kappa(P)$ is
maximized by taking $\omega_{1}=10$, $\omega_{2}=0.1$, $\omega_{3}=1$,
$\omega_{4}=1$ and $\omega_{5}=8$, which corresponds to a weighted path in
$\mathcal{T}_{W}$ that’s not polarized according to the definition in Section
1.

######  Remark 5.3.

The two partial orders $\succeq_{s}$ and $\succeq_{v}$ are identical for
simple trees. Indeed, if $T$ is simple in the definitions of $\succeq_{s}$ and
$\succeq_{v}$, we have $\text{vol}_{T_{1}}(T_{1})=2|T_{1}|-1$ and
$\text{vol}_{T_{2}}(T_{2})=2|T_{2}|$ by handshaking lemma, so
$|T_{1}|>|T_{2}|$ if and only if
$\text{vol}_{T_{1}}(T_{1})>\text{vol}_{T_{2}}(T_{2})$. Hence, we can write
$\succeq:=\succeq_{s}=\succeq_{v}$ if we only consider simple trees. Figure 4
illustrates the Hasse diagram of $\succeq$ on simple trees of of size $7$.

Figure 4: Hasse diagram of the partial order $\succeq$ on simple trees of of
size $7$.

Sidorenko [10] introduced a partial order $\succcurlyeq$ before: For two
simple trees $T$ and $T^{\prime}$, we write $T\succcurlyeq T^{\prime}$ if and
only if $\text{hom}(T,G)\geq\text{hom}(T^{\prime},G)$ for any simple graph
$G$. Here, $\text{hom}(T,G)$ is the number of graph homomorphisms from $T$
into $G$. The Hasse diagrams of $\succcurlyeq$ on simple trees with size $6$
and $7$ are determined in [10]. We observed (empirically) that there don’t
exist distinct trees $T$ and $T^{\prime}$ satisfying both $T\succcurlyeq
T^{\prime}$ and $T\succeq T^{\prime}$. Hence we conjecture the following.

######  Conjecture 5.4.

For two trees $T$ and $T^{\prime}$ with $|T|=|T^{\prime}|$, if $T\succcurlyeq
T^{\prime}$, then $\alpha(T^{\prime})\geq\alpha(T)$.

We have verified this conjecture to be true for simple trees of size $6$, $7$,
and $8$.

Acknowledgement. I wish to thank Fan Chung and Alexander Sidorenko for
valuable comments.

## References

  * [1] Pavel Chebotarev and Elena Deza.  Hitting time quasi-metric and its forest representation.  Optimization Letters, 14(2):291–307, 2020.
  * [2] Fan Chung and Ji Zeng.  Forest formulas of discrete Green’s functions.  2021\.  arXiv:2109.01324. https://arxiv.org/abs/2109.01324.
  * [3] Lorenzo Ciardo, Geir Dahl, and Steve Kirkland.  On Kemeny’s constant for trees with fixed order and diameter.  Linear and Multilinear Algebra, pages 1–23, 2020.
  * [4] Nolan Faught, Mark Kempton, and Adam Knudson.  A 1-separation formula for the graph Kemeny constant and Braess edges.  Journal of Mathematical Chemistry, pages 1–21, 2021.
  * [5] John G. Kemeny and J. Laurie Snell.  Finite Markov Chains.  Van Nostrand, 1960.
  * [6] Mark Levene and George Loizou.  Kemeny’s constant and the random surfer.  The American Mathematical Monthly, 109(8):741–745, 2002.
  * [7] Shuchao Li, Wanting Sun, and Shujing Wang.  Multiplicative degree-Kirchhoff index and number of spanning trees of a zigzag polyhex nanotube TUHC [2n, 2].  International Journal of Quantum Chemistry, 119(17):e25969, 2019\.
  * [8] Russell Lyons and Yuval Peres.  Probability on Trees and Networks, volume 42.  Cambridge University Press, 2017.
  * [9] Rushabh Patel, Pushkarini Agharkar, and Francesco Bullo.  Robotic surveillance and Markov chains with minimal weighted Kemeny constant.  IEEE Transactions on Automatic Control, 60(12):3156–3167, 2015\.
  * [10] Alexander Sidorenko.  A partially ordered set of functionals corresponding to graphs.  Discrete Mathematics, 131(1-3):263–277, 1994.