# Solution to an open problem on Laplacian ratio††thanks:  supported by NSFC
(No. 12261071)and NSF of Qinghai Province (No. 2020-ZJ-920).

Tingzeng Wua,b, Xiangshuai Donga, Hong-Jian Laic, Xiaolin Zenga
a School of Mathematics and Statistics, Qinghai Nationalities University,
Xining, Qinghai 810007, P.R. China
b Qinghai Institute of Applied Mathematics, Xining, Qinghai, 810007, P.R.
China
c Department of Mathematics, West Virginia University, Morgantown, WV, USA
Corresponding author.
_E-mail address_<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
Abstract: Let $G$ be a graph. The Laplacian ratio of $G$ is the permanent of
the Laplacian matrix of $G$ divided by the product of degrees of all vertices.
The computational complexity of Laplacian ratio is $\\#{\rm P}$-complete.
Brualdi and Goldwasser studied systematicly the properties of Laplacian ratios
of graphs. And they proposed an open problem: what is the minimum value of the
Laplacian ratios of trees with $n$ vertices having diameter at least $k$ ? In
this paper, we give a solution to the problem.

Keywords: Permanent; Laplacian matrix; Laplacian ratio; Tree; Diameter

##  1 Introduction

The permanent of an $n$ square matrix $M=[m_{ij}]$ with
$i,j\in\\{1,2,\ldots,n\\}$, is defined as

$\displaystyle{\rm
per}M=\sum_{\sigma\in\Lambda_{n}}\prod_{i=1}^{n}m_{i\sigma(i)},$

where $\Lambda_{n}$ denotes the symmetry group of order $n$. Valiant [1] has
shown that computing the permanent is $\\#{\rm P}$-complete even when
restricted to (0,1)-matrices.

Let $G=(V(G),E(G))$ be a simple graph with
$V(G)=\\{v_{1},v_{2},\ldots,v_{n}\\}$ and $d_{i}$ denote the degree of vertex
$v_{i}$ in $V(G)$ for $i=1,2,\ldots,n$. Let $D(G)$ be the diagonal matrix
whose $(i,i$)-entry is $d_{i}$, and let $A(G)$ be the adjacency matrix of $G$.
The matrix $L(G)=D(G)-A(G)$ is the Laplacian matrix of $G$. Let $PD(G)$ be the
product of degrees all vertices in $G$. If $G$ has a $u,v$-path, then the
distance from $u$ to $v$, denoted $d(u,v)$, is the least length of a
$u,v$-path. The diameter of $G$ is $\max_{u,v\in V(G)}d(u,v)$. Suppose that
$G-v$ and $G-uv$ denote the graph obtained from $G$ by deleting vertex $v\in
V(G)$, or edge $uv\in E(G)$, respectively (this notation is naturally extended
if more than one vertex or edge is deleted). The path and star of order $n$
are denoted by $P_{n}$ and $S_{n}$, respectively. A caterpillar is a tree in
which a single path (the spine) is incident to (or containing) every edge. A
double-star $DS(p,q)$ is a tree obtained by joining the center of stars
$S_{p}$ and $S_{q}$ by one edge, where $p\geq 2$ and $q\geq 2$.

The Laplacian ratio of $G$ is defined by

$\displaystyle\pi(G)=\frac{{\rm per}L(G)}{PD(G)}.$

By the definition as above, we can conclude that computing the Laplacian ratio
of a graph is $\\#{\rm P}$-complete because of Valiant’s result [1] mentioned
earlier. Laplacian ratios of graphs were first considered by Brualdi and
Goldwasser [2]. They determined the bounds for $\pi(G)$ when $G$ is a tree or
generally, a bipartite graph. In particular, they proposed three open problems
for Laplacian ratios of trees in 1984. That is,

######  Problem 1.

([2]) What is the minimum value of the Laplacian ratios of trees with $n$
vertices having diameter at least $k$?

######  Problem 2.

([2]) What is the minimum value of the Laplacian ratios of trees with $n$
vertices having a $k$-matching?

######  Problem 3.

([2]) Let $\mathscr{T}_{1}(n,k)$ be the family of all trees of order $n$ with
diameter at most $k$, and $\mathscr{T}_{2}(n,k)$ be the family of all trees of
order $n$ with matching number at most $k$. Determine the maximum value of
Laplacian ratios of graphs in $\mathscr{T}_{1}$ and in $\mathscr{T}_{2}$.

Over the last forty years, only Problem 2 is solved in [3]. Problems 1 and 3
remain open. In this paper, our interest is to investigate Problem 1. Let $n$
and $k$ be integers. The Broom graph $B(n,k)$ is a graph obtained by attaching
$n-k$ pendant edges to an endvertex of $P_{k}$. We prove the following main
result.

Figure 1: The Broom graph $B(n,k)$.

######  Theorem 1.1.

Let $T$ be a tree with $n$ vertices and diameter at least $k$, Then

$\pi(T)\geq\biggl{[}1+\sqrt{2}-\frac{\sqrt{2}}{2(n-k+1)}\biggl{]}\biggl{(}\frac{1+\sqrt{2}}{2}\biggl{)}^{k-2}+\biggl{[}1-\sqrt{2}+\frac{\sqrt{2}}{2(n-k+1)}\biggl{]}\biggl{(}\frac{1-\sqrt{2}}{2}\biggl{)}^{k-2},$

where equality holds if and only if tree $T$ is the broom graph $B(n,k)$.

This paper is organized as follows. In Section 2, we first develop some
properties of the permanent of Laplacian matrices of graphs, and we introduce
some graph operations that can be considered as graph transformations which
will have smaller Laplacian ratios than that of the original graphs. Based on
results as above, we give the proof of Theorem 1.1. A brief summary will be
given in section 3.

##  2 Main results

Before proceeding to the proof of Theorem 1.1, we first prove some lemmas.

Lemma 2.1 follows from the definition of permanent and is well-known.

######  Lemma 2.1.

Let $A$ be any $n\times n$ matrix and $i,j$ be indices between $1$ and $n$.
Then

${\rm per}A=\sum_{i}a_{ij}{\rm per}A_{ij}~{}{\rm and}~{}{\rm
per}A=\sum_{j}a_{ij}{\rm per}A_{ij},$

where $A_{ij}$ is the $(n-1)\times(n-1)$ matrix obtained by striking out the
$i$th row and $j$th column of $A$.

Let $G$ be a simple graph, and let $S\subseteq V(G)$ be a vertex subset. We
use $L_{S}(G)$ to denote the principal submatrix of $L(G)$ formed by deleting
the rows and columns corresponding to all vertices of $S\subseteq V(G)$. In
particular, if $S=\\{v\\}$ with $v\in V(G)$, then $L_{\\{v\\}}(G)$ is simply
written as $L_{v}(G)$.

Suppose that $v$ is a vertex of $G$. Define $\mathscr{C}_{G}(v)$ to be the set
of cycles containing the vertex $v$ in $G$, and $N(v)$ the neighborhood of
$v$.

######  Lemma 2.2.

Let $G$ be a simple graph, and $v\in V(G)$ be a vertex. Then

$\displaystyle{\rm per}L(G)=d(v)~{}{\rm per}L_{v}(G)+\sum\limits_{u\in
N(v)}{\rm per}L_{vu}(G)+2\sum\limits_{C\in\mathscr{C}_{G}(v)}(-1)^{|V(C)|}{\rm
per}L_{V(C)}(G).$

###### Proof.

Suppose that $V(G)=\\{v_{1}$, $v_{2}$, $\ldots$, $v_{n}\\}$. Consider a term
$a_{1\sigma(1)}a_{2\sigma(2)}\cdots a_{n\sigma(n)}$ in the expansion of ${\rm
per}L(G)$, where $a_{ij}$ is the $(i,j)$-entry of $L(G)$. Note that
$a_{ii}=d(v_{i})$, and when $i\neq j$, if $v_{i}v_{j}\in E(G)$, then
$a_{ij}=-1$; otherwise $a_{ij}=0$, Hence if
$a_{1\sigma(1)}a_{2\sigma(2)}\cdots a_{n\sigma(n)}\neq 0$, then $j=\sigma(j)$
or $v_{j\sigma_{j}}\in E(G)$. Next, we only consider the situation that the
permanent expansion of $L(G)$ is not $0$. Without loss of generality, let
$v=v_{1}$. Hence $a_{11}=d(v)$. Let $\sigma$ be a set of disjoint cyclic
permutation. When $\gamma_{1}$ is a cycle in $\sigma$, we write
$\sigma=\gamma_{1}\sigma^{{}^{\prime}}$. Define
$P=\\{\sigma|a_{1\sigma(1)}a_{2\sigma(2)}\cdots a_{n\sigma(n)}\neq 0\\}$.
According to the length of $\gamma_{1}$, $\sigma$ has three situations as
follows:

$S_{1}=\\{\sigma\in P,\gamma_{1}=(1)$, i.e., $\sigma$ fixes $1\\}$,

$S_{2}^{j}=\\{\sigma\in P,\gamma_{1}=(1j)$, i.e., $\gamma_{1}$ corresponds to
an edge $vv_{j}$ of $G\\}$,

$S_{C}=\\{\sigma\in P,\gamma_{1}$ corresponds to a cycle $C$ of length $l\geq
3$ which contains the vertex $v$ of $G\\}$.

Then, as $S_{1},S_{2}^{j}$ (for any $j\neq 1$) and $S_{C}$ are mutually
disjoint and $P=S_{1}\cup S_{2}^{j}\cup S_{C}$, we have

$\displaystyle{\rm per}L(G)$ $\displaystyle=$
$\displaystyle\sum_{\sigma}a_{1\sigma(1)}a_{2\sigma(2)}\cdots a_{n\sigma(n)}$
$\displaystyle=$ $\displaystyle\sum_{\sigma\in
S_{1}}a_{1\sigma(1)}a_{2\sigma(2)}\cdots
a_{n\sigma(n)}+\sum_{j}\sum_{\sigma\in
S_{2}^{j}}a_{1\sigma(1)}a_{2\sigma(2)}\cdots a_{n\sigma(n)}$
$\displaystyle+\sum_{C}\sum_{\sigma\in
S_{C}}a_{1\sigma(1)}a_{2\sigma(2)}\cdots a_{n\sigma(n)}$ $\displaystyle=$
$\displaystyle
d(v)\sum_{\sigma^{{}^{\prime}}\atop\gamma_{1}\sigma^{{}^{\prime}}\in
S_{1}}a_{2\sigma^{{}^{\prime}}(2)}\cdots
a_{n\sigma^{{}^{\prime}}(n)}+\sum_{vv_{j}\in
E(G)}\sum_{\sigma^{{}^{\prime}}\atop\gamma_{1}\sigma^{{}^{\prime}}\in
S_{2}^{j}}a_{2\sigma^{{}^{\prime}}(2)}\cdots
a_{(j-1)\sigma^{{}^{\prime}}(j-1)}a_{(j+1)\sigma^{{}^{\prime}}(j+1)}$
$\displaystyle\cdots
a_{n\sigma^{{}^{\prime}}(n)}+2\sum_{C\in\mathscr{C}_{G}(v)}(-1)^{|V(C)|}\sum_{\sigma^{{}^{\prime}}\atop\gamma_{1}\sigma^{{}^{\prime}}\in
S_{C}}a_{i_{1}\sigma^{{}^{\prime}}(i_{1})}a_{i_{2}\sigma^{{}^{\prime}}(i_{2})}\cdots
a_{i_{n-l}\sigma^{{}^{\prime}}(i_{i_{n-l}})}$ $\displaystyle=$ $\displaystyle
d(v)~{}{\rm per}L_{v}(G)+\sum\limits_{vv_{j}\in E(G)}{\rm
per}L_{vu}(G)+2\sum\limits_{C\in\mathscr{C}_{G}(v)}(-1)^{|V(C)|}{\rm
per}L_{V(C)}(G),$

where in the penultimate step $i_{1}$, $\ldots$, $i_{n-l}$ are indices of the
vertices of the graph $G-V(C)$. ∎

######  Lemma 2.3.

If $v$ is a pendant vertex of $G$, and $u$ is the vertex adjacent to $v$. Then

$\displaystyle{\rm per}L(G)={\rm per}L(G-v)+2~{}{\rm per}L_{u}(G-v).$

###### Proof.

By Lemma 2.2 with $d_{v}=1$ and $\mathscr{C}_{G}=\phi$, we have ${\rm
per}L(G)={\rm per}L_{v}(G)+{\rm per}L_{uv}(G)$. Using the linearity of the
permanent as a function of any row or column, it can be known that ${\rm
per}L_{v}(G)={\rm per}L(G-v)+{\rm per}L_{uv}(G)$. By the definition of ${\rm
per}L_{uv}(G)$, we have ${\rm per}L_{uv}(G)={\rm per}L_{u}(G-v)$. According to
arguments as above, we obtain that

${\rm per}L(G)={\rm per}L(G-v)+2~{}{\rm per}L_{uv}(G)={\rm per}L(G-v)+2~{}{\rm
per}L_{u}(G-v).$

∎

######  Lemma 2.4.

Let $v$ be a vertex of $G$. Suppose that $H$ is a proper subgraph of $G$
satisfying $v\notin V(H)$. Then

$\displaystyle{\rm per}L_{V(H)}(G)$ $\displaystyle=$ $\displaystyle
d(v)~{}{\rm per}L_{V(H)\cup\\{v\\}}(G)+\sum\limits_{uv\in E(G)\atop u\notin
V(H)}{\rm per}L_{V(H)\cup\\{u,v\\}}(G)$
$\displaystyle+2\sum\limits_{C\in\mathscr{C}_{G}(v)\atop V(C)\cap
V(H)=\emptyset}(-1)^{|V(C)|}{\rm per}L_{V(C)\cup V(H)}(G).$

###### Proof.

The proof is similar to that of Lemma 2.2, Without loss of generality, we
denote $V(H)=\\{v_{h+1},v_{h+2},...,v_{n}\\}$. Then, as $S_{1},S_{2}^{j}$ (for
any $j\neq 1$) and $S_{C}$ are mutually disjoint and $P=S_{1}\cup
S_{2}^{j}\cup S_{C}$, we have

$\displaystyle{\rm per}~{}L_{V(H)}(G)$ $\displaystyle=$
$\displaystyle\sum_{\sigma\atop\gamma_{1}\sigma^{{}^{\prime}}\in
S_{1}}a_{1\sigma(1)}a_{2\sigma(2)}\cdots a_{h\sigma(h)}$ $\displaystyle=$
$\displaystyle\sum_{\sigma\in S_{1}}a_{1\sigma(1)}a_{2\sigma(2)}\cdots
a_{h\sigma(h)}+\sum_{j}\sum_{\sigma\in
S_{2}^{j}}a_{1\sigma(1)}a_{2\sigma(2)}\cdots a_{h\sigma(h)}$
$\displaystyle+\sum_{C}\sum_{\sigma\in
S_{C}}a_{1\sigma(1)}a_{2\sigma(2)}\cdots a_{h\sigma(h)}$ $\displaystyle=$
$\displaystyle
d(v)\sum_{\sigma^{{}^{\prime}}\atop\gamma_{1}\sigma^{{}^{\prime}}\in
S_{1}}a_{2\sigma^{{}^{\prime}}(2)}\cdots
a_{h\sigma^{{}^{\prime}}(h)}+\sum_{vv_{j}\in
E(G)}\sum_{\sigma^{{}^{\prime}}\atop\gamma_{1}\sigma^{{}^{\prime}}\in
S_{2}^{j}}a_{2\sigma^{{}^{\prime}}(2)}\cdots
a_{(j-1)\sigma^{{}^{\prime}}(j-1)}a_{(j+1)\sigma^{{}^{\prime}}(j+1)}$
$\displaystyle\cdots
a_{h\sigma^{{}^{\prime}}(h)}+2\sum_{C\in\mathscr{C}_{G}(v)}(-1)^{|V(C)|}\sum_{\sigma^{{}^{\prime}}\atop\gamma_{1}\sigma^{{}^{\prime}}\in
S_{C}}a_{i_{1}\sigma^{{}^{\prime}}(i_{1})}a_{i_{2}\sigma^{{}^{\prime}}(i_{2})}\cdots
a_{i_{n-h-l}\sigma^{{}^{\prime}}(i_{i_{n-h-l}})}$ $\displaystyle=$
$\displaystyle d(v)~{}{\rm per}L_{V(H)\cup\\{v\\}}(G)+\sum\limits_{vv_{j}\in
E(G)\atop u\notin V(H)}{\rm per}L_{V(H)\cup\\{u,v\\}}(G)$
$\displaystyle+2\sum\limits_{C\in\mathscr{C}_{G}(v)\atop V(C)\cap
V(H)=\emptyset}(-1)^{|V(C)|}{\rm per}L_{V(C)\cup V(H)}(G),$

where in the penultimate step $i_{1},\ldots,i_{n-h-l}$ are indices of the
vertices of the graph $G-\\{V(H)$
$\cup V(C)\\}$. ∎

######  Lemma 2.5.

Let $e=uv$ be an edge of $G$, and let $\mathscr{C}_{G}(e)$ be a set of cycles
containing the edge $e$ in $G$. Then

$\displaystyle{\rm per}L(G)$ $\displaystyle=$ $\displaystyle{\rm
per}L(G-e)+{\rm per}L_{v}(G-e)+{\rm per}L_{u}(G-e)$ $\displaystyle+2~{}{\rm
per}L_{uv}(G)+2\sum\limits_{C\in\mathscr{C}_{G}(e)}(-1)^{|V(C)|}{\rm
per}L_{V(C)}(G).$

###### Proof.

By Lemma 2.2, we have

$\displaystyle{\rm per}L(G)=d(u)~{}{\rm per}L_{u}(G)+\sum\limits_{uw\in
E(G)}{\rm per}L_{uw}(G)+2\sum\limits_{C\in\mathscr{C}_{G}(u)}(-1)^{|V(C)|}{\rm
per}L_{V(C)}(G)$

and

$\displaystyle{\rm per}L(G-e)$ $\displaystyle=$ $\displaystyle(d(u)-1)~{}{\rm
per}L_{u}(G-e)+\sum\limits_{uw\in E(G-e)}{\rm per}L_{uw}(G-e)$
$\displaystyle+2\sum\limits_{C\in\mathscr{C}_{G-e}(u)}(-1)^{|V(C)|}{\rm
per}L_{V(C)}(G-e).$

Therefore,

$\displaystyle{\rm per}L(G)-{\rm per}L(G-e)$ $\displaystyle=$ $\displaystyle
d(u)~{}{\rm per}L_{u}(G)-(d(u)-1)~{}{\rm
per}L_{u}(G-e)+\biggl{[}\sum\limits_{uw\in E(G)}{\rm per}L_{uw}(G)$
$\displaystyle-\sum\limits_{uw\in E(G-e)}{\rm
per}L_{uw}(G-e)\biggl{]}+2~{}\biggl{[}\sum\limits_{C\in\mathscr{C}_{G}(u)}(-1)^{|V(C)|}{\rm
per}L_{V(C)}(G)$
$\displaystyle-\sum\limits_{C\in\mathscr{C}_{G-e}(u)}(-1)^{|V(C)|}{\rm
per}L_{V(C)}(G-e)\biggl{]}.$

Since

$\displaystyle{\rm per}L_{u}(G)={\rm per}L_{u}(G-e)+{\rm per}L_{uv}(G-e)={\rm
per}L_{u}(G-e)+{\rm per}L_{uv}(G).$ (2)

Similarly, we have both

$\displaystyle\sum_{uw\in E(G)\atop w\neq v}{\rm per}L_{uw}(G)=\sum_{uw\in
E(G-e)}{\rm per}L_{uw}(G-e)+\sum_{uw\in E(G)\atop w\neq v}{\rm
per}L_{\\{u,w,v\\}}(G)$ (3)

and

$\displaystyle\sum_{C\in\mathscr{C}_{G-e}(u)\atop v\notin
V(C)}(-1)^{|V(C)|}{\rm per}L_{V(C)}(G)$ $\displaystyle=$
$\displaystyle\sum_{C\in\mathscr{C}_{G-e}(u)\atop v\notin
V(C)}(-1)^{|V(C)|}{\rm per}L_{V(C)}(G-e)$ (4)
$\displaystyle+\sum_{C\in\mathscr{C}_{G-e}(u)\atop v\notin
V(C)}(-1)^{|V(C)|}{\rm per}L_{V(C)\cup\\{v\\}}(G-e).$

Substituting (2), (3), (4) into (2), we have

$\displaystyle{\rm per}L(G)-{\rm per}L(G-e)$ (5) $\displaystyle=$
$\displaystyle(d(u)+1)~{}{\rm per}L_{uv}(G)+{\rm per}L_{u}(G-e)$
$\displaystyle+\sum_{uw\in E(G)\atop w\neq v}{\rm
per}L_{\\{u,w,v\\}}(G)+2\sum\limits_{C\in\mathscr{C}_{G}(e)}(-1)^{|V(C)|}{\rm
per}L_{V(C)}(G)$ $\displaystyle+2\sum_{C\in\mathscr{C}_{G-e}(u)\atop v\notin
V(C)}(-1)^{|V(C)|}{\rm per}L_{V(C)\cup\\{v\\}}(G-e).$

By Lemma 2.4, we have

$\displaystyle{\rm per}L_{v}(G-e)$ $\displaystyle=$
$\displaystyle(d(u)-1)~{}{\rm per}L_{uv}(G-e)+\sum_{uw\in E(G-e)\atop w\neq
v}{\rm per}L_{\\{u,w,v\\}}(G-e)$ (6)
$\displaystyle+2\sum_{C\in\mathscr{C}_{G-e}(u)\atop v\notin
V(C)}(-1)^{|V(C)|}{\rm per}L_{V(C)\cup\\{v\\}}(G-e).$

Substituting (6) into (5), we have

$\displaystyle{\rm per}L(G)-{\rm per}L(G-e)$ $\displaystyle=$
$\displaystyle{\rm per}L_{v}(G-e)+{\rm per}L_{u}(G-e)$ $\displaystyle+2~{}{\rm
per}L_{uv}(G)+2\sum\limits_{C\in\mathscr{C}_{G}(e)}(-1)^{|V(C)|}{\rm
per}L_{V(C)}(G).$

It follow that

$\displaystyle{\rm per}L(G)$ $\displaystyle=$ $\displaystyle{\rm
per}L(G-e)+{\rm per}L_{v}(G-e)+{\rm per}L_{u}(G-e)$ $\displaystyle+2~{}{\rm
per}L_{uv}(G)+2\sum\limits_{C\in\mathscr{C}_{G}(e)}(-1)^{|V(C)|}{\rm
per}L_{V(C)}(G).$

∎

Let $k$ be a nonnegative integer, and let $\mu$ be a $k$-matching of $G$
(i.e., a set of $k$ vertex disjoint edges) which meets vertices
$v_{{}_{i_{1}}},v_{{}_{i_{2}}},\ldots,v_{{}_{i_{2k}}}$ such that
$v_{{}_{i_{j}}}$ has degree $d_{{}_{i_{j}}}$, $1\leq j\leq 2k$. Define

$d_{G}(\mu)=\begin{cases}d_{{}_{i_{1}}}\cdots d_{{}_{i_{2k}}}~{}~{}~{}{\rm
if}~{}k>0\\\ ~{}~{}~{}~{}~{}1~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}{\rm
if}~{}k=0\end{cases}$

In particular, if $e=u_{1}u_{2}\in E(G)$ and the vertices $u_{1},u_{2}$ has
degrees $d_{{}_{u_{1}}}$ and $d_{{}_{u_{2}}}$, then

$d_{G}(e)=d_{{}_{u_{1}}}d_{{}_{u_{2}}}.$

When the graph $G$ is understood from the context, we also omit the subscript
$G$ and simply write $d(\mu)$ and $d(e)$ for $d_{G}(\mu)$ and $d_{G}(e)$,
respectively. Let $\mathscr{G}_{k}(G)$ denote the set of all $k$-matchings of
$G$. We define $\pi_{k}(G)$ by

$\pi_{k}(G)=\sum\limits_{\mu\in\mathscr{G}_{k}(G)}\frac{1}{d(\mu)}.$

######  Lemma 2.6.

([2]) Let $T$ be a tree, then

$\displaystyle\pi(T)=\sum\limits_{k=0}\limits^{\lfloor\frac{n}{2}\rfloor}\pi_{k}(T)$

######  Lemma 2.7.

([2]) Let $T$ be a tree with diameter $k$. Then $\pi(T)\geq\pi(P_{k+1})$ with
equality holding if and only if $T$ is the path $P_{k+1}$, or when $k=2$, $T$
is the star $S_{n}$.

For an integer $r\geq 1$, let $T_{r}$ denote a tree of order $r(r\geq 1)$.
Suppose that $H$ is a tree disjoint from $T_{r}$ Assume that $u\in V(H)$ and
$v\in V(T_{r})$. Let $G_{1}$ be the graph obtained from the union of $H$ and
$T_{r}$ by linking $u$ and $v$ with a new edge, and $G_{2}$ be the graph
obtained from $H$ by attaching $r$ pendent edges to $u$. Suppose in $G_{2}$,
the edges incident with $u$ in $H$ are labelled $h_{1},h_{2},\cdots,h_{s}$,
and other $r$ pendent edges incident with $u$ in $G_{2}$ are labelled
$e_{1},e_{2},\cdots,e_{r}$. Suppose in $G_{1}$, the edges in $T_{r}$ are
labelled $e_{2}^{{}^{\prime}},e_{3}^{{}^{\prime}},\cdots,e_{r}^{{}^{\prime}}$,
and $e_{1}^{{}^{\prime}}=uv$. See Figure 1 for illustrations of $G_{1}$ and
$G_{2}$. By the definitions of $G_{1}$ and $G_{2}$, we have
$d_{G_{2}}(u)=d_{G_{1}}(u)+r-1$. Let $\mathscr{G}_{k}(G_{2})$ denote the set
of all $k$-matchings of $G_{2}$, let $\mathscr{G}_{k,u}^{+}(G_{2})$ be the set
of all $k$-matchings covering $u$, and $\mathscr{G}^{-}_{k,u}(G_{2})$ be the
set of all $k$-matchings not covering $u$. By these definitions,
$\mathscr{G}_{k,u}^{+}(G_{2})\cup\mathscr{G}^{-}_{k,u}(G_{2})=\mathscr{G}_{k}(G_{2})$.
Denote by $\mathscr{G}_{k,u}^{++}(G_{2})$ the set of all $k$-matching in
$\mathscr{G}_{k,u}^{+}(G_{2})$ which covers exactly one edge of
$\\{e_{1},e_{2},\cdots,e_{r}\\}$, and denote by
$\mathscr{G}_{k,u}^{+-}(G_{2})$ the set of all k-matching in
$\mathscr{G}_{k,u}^{+}(G_{2})$ which covers exactly one edge of
$\\{h_{1},h_{2},\cdots,h_{s}\\}$. By their definitions,
$\mathscr{G}_{k,u}^{++}(G_{2})\cup\mathscr{G}_{k,u}^{+-}(G_{2})=\mathscr{G}_{k,u}^{+}(G_{2})$.
$\mathscr{G}_{k}(G_{1})$ denotes the set of all $k$-matchings of $G_{1}$.
Denote by $\mathscr{G}_{k}^{+}(G_{1})$ the set of all $k$-matchings in
$\mathscr{G}_{k}(G_{1})$ which covers exactly one edge of
$\\{h_{1},h_{2},\cdots,h_{s},e_{1}^{{}^{\prime}},e_{2}^{{}^{\prime}},\cdots,e_{r}^{{}^{\prime}}\\}$.
Let $\mathscr{G}^{-}_{k}(G_{1})$ be the set of all $k$-matchings uncovering
$u$ in $H$, and
$\mathscr{G}^{*}_{k}(G_{1})=\mathscr{G}_{k}(G_{1})-\mathscr{G}_{k}^{+}(G_{1})-\mathscr{G}^{-}_{k}(G_{1})$.
Denote by $\mathscr{G}_{k}^{++}(G_{1})$ the set of all k-matching in
$\mathscr{G}_{k}^{+}(G_{1})$ which covers one edge of
$\\{e_{1}^{{}^{\prime}},e_{2}^{{}^{\prime}},\cdots,e_{r}^{{}^{\prime}}\\}$,
and denote by $\mathscr{G}_{k}^{+-}(G_{1})$ the set of all k-matching in
$\mathscr{G}_{k}^{+}(G_{1})$ which covers one edge of
$\\{h_{1},h_{2},\cdots,h_{s}\\}$. By their definitions,
$\mathscr{G}_{k}^{++}(G_{2})\cup\mathscr{G}^{+-}_{k}(G_{2})=\mathscr{G}_{k}^{+}(G_{2})$.

Figure 2: Graphs $G_{1}$ and $G_{2}$.

Define

$\displaystyle\psi=\frac{1}{d(e_{1}^{{}^{\prime}})}+\frac{1}{d(e_{2}^{{}^{\prime}})}+\cdots+\frac{1}{d(e_{r}^{{}^{\prime}})}~{}{\rm
and}~{}\theta=\frac{1}{d(e_{1})}+\frac{1}{d(e_{2})}+\cdots+\frac{1}{d(e_{r})}.$
(7)

######  Lemma 2.8.

Let $G_{1}$ and $G_{2}$ be two graphs defined as above. Then

(i) If $\psi\geq\theta$, then $\pi(G_{1})\geq\pi(G_{2})$.

(ii) If $T_{r}$ is a star and $v$ is the center of $T_{r}$, then
$\pi(G_{1})\geq\pi(G_{2})$.

(iii) $\pi(G_{1})\geq\pi(G_{2})$.

###### Proof.

(i). If $r=1$ in $G_{1}$ and $G_{2}$, then $G_{1}\cong G_{2}$. Therefore
$\pi(G_{1})=\pi(G_{2})$. Now, set $r\geq 2$. By the definitions of
$\pi_{k}(G_{1})$ and $\pi_{k}(G_{2})$, we have
$\pi_{k}(G_{2})=\sum\limits_{\mu\in\mathscr{G}^{-}_{k,u}(G_{2})}\frac{1}{d(\mu)}+\sum\limits_{\mu\in\mathscr{G}^{+}_{k,u}(G_{2})}\frac{1}{d(\mu)}$
and
$\pi_{k}(G_{1})\geq\sum\limits_{\mu\in\mathscr{G}^{-}_{k}(G_{1})}\frac{1}{d(\mu)}+\sum\limits_{\mu\in\mathscr{G}^{+}_{k}(G_{1})}\frac{1}{d(\mu)}$.
Checking the structure of a $k$-matching in $\mathscr{G}^{++}_{k,u}(G_{2})$,
since every $k$-matching in $\mathscr{G}^{++}_{k,u}(G_{2})$ contains exactly
one edge of $\\{e_{1},e_{2},\cdots,e_{r}\\}$ and a $(k-1)$-matching in
$\mathscr{G}^{-}_{k,u}(G_{2})$, we have
$\sum\limits_{\mu\in\mathscr{G}^{++}_{k,u}(G_{2})}\frac{1}{d(\mu)}=\sum\limits_{\mu\in\mathscr{G}^{-}_{k-1,u}(G_{2})}\frac{1}{d(\mu)}\theta$.
Similarly, by the definition of $G_{1}$ and the distributions of a
$k$-matching in $\mathscr{G}^{++}_{k}(G_{1})$, we observe that every
$k$-matching in $\mathscr{G}^{++}_{k}(G_{1})$ contains exactly one edge of
$\\{e_{1}^{{}^{\prime}},e_{2}^{{}^{\prime}},\cdots,e_{r}^{{}^{\prime}}\\}$ and
a $(k-1)$-matching in $\mathscr{G}^{-}_{k}(G_{1})$. This yields
$\sum\limits_{\mu\in\mathscr{G}^{++}_{k}(G_{1})}\frac{1}{d(\mu)}=\sum\limits_{\mu\in\mathscr{G}^{-}_{k-1}(G_{1})}\frac{1}{d(\mu)}\psi$.
Hence,

$\displaystyle\pi_{k}(G_{2})$ $\displaystyle=$
$\displaystyle\sum\limits_{\mu\in\mathscr{G}^{-}_{k,u}(G_{2})}\frac{1}{d(\mu)}+\sum\limits_{\mu\in\mathscr{G}^{-}_{k,u}(G_{2})}\frac{1}{d(\mu)}$
$\displaystyle=$
$\displaystyle\sum\limits_{\mu\in\mathscr{G}^{-}_{k,u}(G_{2})}\frac{1}{d(\mu)}+\sum\limits_{\mu\in\mathscr{G}^{++}_{k,u}(G_{2})}\frac{1}{d(\mu)}+\sum\limits_{\mu\in\mathscr{G}^{+-}_{k,u}(G_{2})}\frac{1}{d(\mu)}$
$\displaystyle=$
$\displaystyle\sum\limits_{\mu\in\mathscr{G}^{-}_{k,u}(G_{2})}\frac{1}{d(\mu)}+\sum\limits_{\mu\in\mathscr{G}^{-}_{k-1,u}(G_{2})}\frac{1}{d(\mu)}\theta+\sum\limits_{\mu\in\mathscr{G}^{++}_{k,u}(G_{2})}\frac{1}{d(\mu)},$
$\displaystyle\pi_{k}(G_{1})$ $\displaystyle\geq$
$\displaystyle\sum\limits_{\mu\in\mathscr{G}^{-}_{k}(G_{1})}\frac{1}{d(\mu)}+\sum\limits_{\mu\in\mathscr{G}^{+}_{k}(G_{1})}\frac{1}{d(\mu)}$
$\displaystyle=$
$\displaystyle\sum\limits_{\mu\in\mathscr{G}^{-}_{k}(G_{1})}\frac{1}{d(\mu)}+\sum\limits_{\mu\in\mathscr{G}^{++}_{k}(G_{1})}\frac{1}{d(\mu)}+\sum\limits_{\mu\in\mathscr{G}^{+-}_{k}(G_{1})}\frac{1}{d(\mu)}$
$\displaystyle=$
$\displaystyle\sum\limits_{\mu\in\mathscr{G}^{-}_{k}(G_{1})}\frac{1}{d(\mu)}+\sum\limits_{\mu\in\mathscr{G}^{-}_{k-1}(G_{1})}\frac{1}{d(\mu)}\psi+\sum\limits_{\mu\in\mathscr{G}^{+-}_{k}(G_{1})}\frac{1}{d(\mu)}.$

Checking the structure of $G_{1}$ and $G_{2}$, we know that
$\mathscr{G}^{-}_{k,u}(G_{2})=\mathscr{G}^{-}_{k}(G_{1})$. Therefore

$\displaystyle\sum\limits_{\mu\in\mathscr{G}^{-}_{k,u}(G_{2})}\frac{1}{d(\mu)}=\sum\limits_{\mu\in\mathscr{G}^{-}_{k}(G_{1})}\frac{1}{d(\mu)}~{}{\rm
and}~{}\sum\limits_{\mu\in\mathscr{G}^{-}_{k-1,u}(G_{2})}\frac{1}{d(\mu)}=\sum\limits_{\mu\in\mathscr{G}^{-}_{k-1}(G_{1})}\frac{1}{d(\mu)}.$

Since $\psi\geq\theta$, we obtain
$\sum\limits_{\mu\in\mathscr{G}^{-}_{k}(G_{1})}\frac{1}{d(\mu)}\psi\geq\sum\limits_{\mu\in\mathscr{G}^{-}_{k-1,u}(G_{2})}\frac{1}{d(\mu)}\theta$.

By the definitions of $G_{1}$ and $G_{2}$, since $r>1$, we have
$d_{G_{1}}(u)<d_{G_{2}}(u)$. Therefore, we also have
$d_{G_{1}}(h_{i})<d_{G_{2}}(h_{i})(1\leq i\leq s)$. This implies that
$\sum\limits_{\mu\in\mathscr{G}^{+-}_{k}(G_{1})}\frac{1}{d(\mu)}>\sum\limits_{\mu\in\mathscr{G}^{+-}_{k,u}(G_{2})}\frac{1}{d(\mu)}$.

Combining the arguments above, we conduce that
$\pi_{k}(G_{1})\geq\pi_{k}(G_{2})$. By Lemma 2.6, we obtain
$\pi(G_{1})\geq\pi(G_{2})$.

(ii). If $r=1$ in $G_{1}$ and $G_{2}$, then $G_{1}\cong G_{2}$. Therefore
$\pi(G_{1})=\pi(G_{2})$. Now, set $r\geq 2$. Checking the structures of
$G_{1}$ and $G_{2}$, set $T_{r}$ is a star, and $v$ is the center of $T_{r}$
in $G_{1}$. By (7), we have $\psi=\frac{1}{d_{u}r}+\frac{r-1}{r}~{}{\rm
and}~{}\theta=\frac{r}{d_{u}+r-1}$. By the definitions of $G_{1}$ and $G_{2}$,
if $d_{u}=1$ in $G_{1}$, then $G_{1}\cong G_{2}$. This implies that
$\pi(G_{1})=\pi(G_{2})$. If $d_{u}=2$ in $G_{1}$, then
$\psi-\theta=\frac{1}{2r}+\frac{r-1}{r}-\frac{r}{2+r-1}>\frac{r-1}{2r(r+1)}\geq
0$. If $d_{u}\geq 3$ in $G_{1}$, then
$\psi-\theta>\frac{r-1}{r}-\frac{r}{3+r-1}>\frac{r-2}{r(r+2)}\geq 0$. By (i)
of Lemma 2.8, we have $\pi(G_{1})\geq\pi(G_{2})$.

(iii). If $r=1$ in $G_{1}$. By the definitions of $G_{1}$ and $G_{2}$, it can
be known that $G_{1}\cong G_{2}$. Therefore $\pi(G_{1})=\pi(G_{2})$. Now, set
$r\geq 2$. We consider two cases as follows.

Case 1. Suppose that the induced subgraph with vertices $V(T_{r})\cup\\{u\\}$
in $G_{1}$ is isomorphic to $P_{r}$. By (7), we have
$\psi=\frac{1}{2d_{u}}+\frac{r-2}{4}+\frac{1}{2}~{}{\rm
and}~{}\theta=\frac{r}{d_{u}+r-1}$. Since $r\geq 2$ and $d_{u}\geq 1$,
$\psi-\theta=\frac{1}{2d_{u}}+\frac{r}{4}-\frac{r}{d_{u}+r-1}=\frac{d_{u}(r^{2}+d_{u}r+2-5r)+2r-2}{4d_{u}(d_{u}+r-1)}\geq\frac{r(r-2)}{4d_{u}(d_{u}+r-1)}\geq
0.$ By (i) of Lemma 2.8, we have $\pi(G_{1})\geq\pi(G_{2})$.

Case 2. Suppose that the induced subgraph of the vertices of
$V(T_{r})\cup\\{u\\}$ in $G_{1}$ is not isomorphic to $P_{r}$. The structure
of $G_{1}$ in this case is displayed on Figure 2. There exists the longest
$v,w$-path in $T_{r}$ and the vertices of the $v,w$-path are labeling
$v(w_{0})$, $w_{1},w_{2},\cdots,w_{m}$, $w$ and their degrees in $G_{1}$ is
$d_{v},d_{w_{1}},d_{w_{2}},\cdots,d_{w_{m}},d_{w}$, respectively. By the
definition of $G_{1}$ as illustrated in Figure 2, we observe that $G_{1}$
contains a vertex $w_{i}$ with $i\geq 0$ and $d_{w_{i}}\geq 3$, and with
$d(v,w_{i})$, the length of a shortest $v,w$-path in $G$, being minimized Let
$V(T_{r-i+1})=V(T_{r})-\\{w_{1},w_{2},\cdots,w_{i-1}\\}$, and
$H^{{}^{\prime}}$ is $G[V(H)\cup\\{v,w_{1},w_{2},\cdots,w_{i-1}\\}]$. Let
$G_{1}^{{}^{\prime}}$ be a tree obtained from $H^{{}^{\prime}}$ by attaching
$r-i$ pendent vertices to $w_{i-1}$. See Figure 2 for the structures of
$H^{{}^{\prime}}$. Direct computation yields that
$PD(G_{1})=\frac{PD(H^{{}^{\prime}})}{d_{w_{i-1}}-1}\times
d_{w_{i-1}}\times\frac{d_{w_{i}}PD(T_{r-i})}{d_{w_{i}}-1}$. By the definitions
of $G_{1}$ and $G_{1}^{{}^{\prime}}$, it is easy to obtain that
$d_{G_{1}^{{}^{\prime}}}(w_{i-1})=d_{w_{i-1}}+r-i$.

Figure 3: Graphs $G_{1}$ and $G_{1}^{{}^{\prime}}$.

With these definitions and notion, we will prove
$\pi(G_{1})>\pi(G_{1}^{{}^{\prime}})$ and
$\pi(G_{1}^{{}^{\prime}})\geq\pi(G_{2})$. To prove
$\pi(G_{1})>\pi(G_{1}^{{}^{\prime}})$, we consider different values of the
diameter of $T_{r}$.

If the diameter of $T_{r-i}$ is $2$. Then $G_{1}\cong G_{1}^{{}^{\prime}}$,
$\pi(G_{1})=\pi(G_{1}^{{}^{\prime}})$.

Assume that the diameter of $T_{r-i}$ is $3$, then $T_{r-i}$ is a double-star.
Assume $T_{r-i}=DS(p,q)$ and $p+q=r-i$. Suppose that the vertices
$c_{1},c_{2}$ is two centers of $DS(p,q)$ and the degree sequence of $DS(p,q)$
is $p,q,1,\cdots,1$. Since $d_{w_{i}}\geq 3$, $w_{i}$ is $c_{1}$ or $c_{2}$.
Without loss of generality, set $w_{i}$ is $c_{1}$ (or $c_{2}$). $G_{1}^{*}$
denotes the tree obtained by deleting pendent vertices of $c_{2}$ (or $c_{1}$)
in $G_{1}$ and attaching simultaneously these pendent vertices to $c_{1}$ (or
$c_{2}$). By (ii) of Lemma 2.8, we have $\pi(G_{1})>\pi(G_{1}^{*})$. By (ii)
of Lemma 2.8 again, we have $\pi(G_{1}^{*})>\pi(G_{2})$. Therefore
$\pi(G_{1})>\pi(G_{1}^{{}^{\prime}})$.

Suppose that the diameter of $T_{r-i}$ is at least $4$. By Lemma 2.5, we have

$\displaystyle{\rm per}~{}L(G_{1})$ $\displaystyle=$ $\displaystyle{\rm
per}L(G_{1}-w_{i-1}w_{i})+{\rm per}L_{w_{i-1}}(G_{1}-w_{i-1}w_{i})$
$\displaystyle+{\rm per}L_{w_{i}}(G_{1}-w_{i-1}w_{i})+{\rm
per}L_{w_{i-1}w_{i}}(G_{1})$ $\displaystyle=$ $\displaystyle{\rm
per}L(H^{{}^{\prime}})~{}{\rm per}L(T_{r-i})+{\rm
per}L_{w_{i-1}}(H^{{}^{\prime}})~{}{\rm per}L(T_{r-i})$ $\displaystyle+{\rm
per}L(H^{{}^{\prime}})~{}{\rm per}L_{w_{i}}(T_{r-i})+2~{}{\rm
per}L_{w_{i-1}}(H^{{}^{\prime}})~{}{\rm per}L_{w_{i}}(T_{r-i})$
$\displaystyle=$ $\displaystyle[{\rm per}~{}L(T_{r-i})+{\rm
per}~{}L_{w_{i}}(T_{r-i})]{\rm per}~{}L(H^{{}^{\prime}})$ $\displaystyle+[{\rm
per}~{}L(T_{r-i})+2~{}{\rm per}~{}L_{w_{i}}(T_{r-i})]{\rm
per}~{}L_{w_{i-1}}(H^{{}^{\prime}}).$

By the definitions of $G_{1}^{{}^{\prime}}$ and $H^{{}^{\prime}}$, we have
${\rm per}~{}L_{v_{1}w_{i-1}}(G_{1}^{{}^{\prime}})={\rm
per}~{}L_{w_{i-1}}(H^{{}^{\prime}})$. By Lemma 2.3, and by deleting
$v_{1},v_{2},\cdots,v_{r-i}$ one by one in $G_{1}^{{}^{\prime}}$, we obtain
that

$\displaystyle{\rm per}~{}L(G_{1}^{{}^{\prime}})$ $\displaystyle=$
$\displaystyle{\rm per}~{}L(G_{1}^{{}^{\prime}}-v_{1})+2~{}{\rm
per}~{}L_{v_{1}w_{i-1}}(G_{1}^{{}^{\prime}})$ $\displaystyle=$
$\displaystyle{\rm per}~{}L(G_{1}^{{}^{\prime}}-v_{1})+2~{}{\rm
per}~{}L_{w_{i-1}}(H^{{}^{\prime}})$ $\displaystyle=$ $\displaystyle{\rm
per}~{}L(G_{1}^{{}^{\prime}}-v_{1}-v_{2})+2~{}{\rm
per}~{}L_{w_{i-1}}(H^{{}^{\prime}})+2~{}{\rm
per}~{}L_{w_{i-1}}(H^{{}^{\prime}})$ $\displaystyle=$ $\displaystyle{\rm
per}~{}L(G_{1}^{{}^{\prime}}-v_{1}-v_{2}-v_{3})+2~{}{\rm
per}~{}L_{w_{i-1}}(H^{{}^{\prime}})+2~{}{\rm
per}~{}L_{w_{i-1}}(H^{{}^{\prime}})+2~{}{\rm
per}~{}L_{w_{i-1}}(H^{{}^{\prime}})$ $\displaystyle\cdots$ $\displaystyle=$
$\displaystyle{\rm per}~{}L(G_{1}^{{}^{\prime}}-v_{1}-v_{2}-\cdots-
v_{r-i-1}-v_{r-i})+2(r-i)~{}{\rm per}~{}L_{w_{i-1}}(H^{{}^{\prime}})$
$\displaystyle=$ $\displaystyle{\rm per}~{}L(H^{{}^{\prime}})+2(r-i)~{}{\rm
per}~{}L_{w_{i-1}}(H^{{}^{\prime}}).$

By Definition of Laplacian ratio, we obtain that

$\displaystyle\pi(G_{1})-\pi(G_{1}^{{}^{\prime}})$ $\displaystyle=$
$\displaystyle\frac{[{\rm per}~{}L(T_{r-i})+{\rm
per}~{}L_{w_{i}}(T_{r-i})]{\rm per}~{}L(H^{{}^{\prime}})+[{\rm
per}~{}L(T_{r-i})}{\frac{PD(H^{{}^{\prime}})}{d_{w_{i-1}}-1}\times
d_{w_{i-1}}\times\frac{d_{w_{i}}}{d_{w_{i}}-1}PD(T_{r-i})}$
$\displaystyle+\frac{2~{}{\rm per}~{}L_{w_{i}}(T_{r-i})]{\rm
per}~{}L_{w_{i-1}}(H^{{}^{\prime}})}{\frac{PD(H^{{}^{\prime}})}{d_{w_{i-1}}-1}\times
d_{w_{i-1}}\times\frac{d_{w_{i}}}{d_{w_{i}}-1}PD(T_{r-i})}-\frac{{\rm
per}~{}L(H^{{}^{\prime}})+2(r-i)~{}{\rm
per}~{}L_{w_{i-1}}(H^{{}^{\prime}})}{\frac{PD(H^{{}^{\prime}})}{d_{w_{i-1}}-1}\times(d_{w_{i-1}}+r-i-1)\times
1^{r-i}}$ $\displaystyle=$ $\displaystyle\frac{(d_{w_{i-1}}+r-i-1)[{\rm
per}~{}L(T_{r-i-1})+{\rm per}~{}L_{w_{i}}(T_{r-i})]{\rm
per}~{}L(H^{{}^{\prime}})}{\frac{PD(H^{{}^{\prime}})}{d_{w_{i-1}}-1}\times
d_{w_{i-1}}\times\frac{d_{w_{i}}}{d_{w_{i}}-1}PD(T_{r-i})\times(d_{w_{i-1}}+r-i-1)}$
$\displaystyle+\frac{(d_{w_{i-1}}+r-i-1)[{\rm per}~{}L(T_{r-i})+2~{}{\rm
per}~{}L_{w_{i}}(T_{r-i})]{\rm
per}~{}L_{w_{i-1}}(H^{{}^{\prime}})}{\frac{PD(H^{{}^{\prime}})}{d_{w_{i-1}}-1}\times
d_{w_{i-1}}\times\frac{d_{w_{i}}}{d_{w_{i}}-1}PD(T_{r-i})\times(d_{w_{i-1}}+r-i-1)}$
$\displaystyle-\frac{d_{w_{i-1}}\times\frac{d_{w_{i}}}{d_{w_{i}}-1}PD(T_{r-i})[{\rm
per}~{}L(H^{{}^{\prime}})+2(r-i)~{}{\rm
per}~{}L_{w_{i-1}}(H^{{}^{\prime}})]}{\frac{PD(H^{{}^{\prime}})}{d_{w_{i-1}}-1}\times
d_{w_{i-1}}\times\frac{d_{w_{i}}}{d_{w_{i}}-1}PD(T_{r-i})\times(d_{w_{i-1}}+r-i-1)}$
$\displaystyle=$ $\displaystyle\frac{[(d_{w_{i-1}}+r-i-1)~{}{\rm
per}~{}L(T_{r-i})+(d_{w_{i-1}}+r-i-1)~{}{\rm per}~{}L_{w_{i}}(T_{r-i})]{\rm
per}~{}L(H^{{}^{\prime}})}{\frac{PD(H^{{}^{\prime}})}{d_{w_{i-1}}-1}\times
d_{w_{i-1}}\times\frac{d_{w_{i}}}{d_{w_{i}}-1}PD(T_{r-i})\times(d_{w_{i-1}}+r-i-1)}$
$\displaystyle-\frac{d_{w_{i-1}}\times\frac{d_{w_{i}}}{d_{w_{i}}-1}PD(T_{r-i}){\rm
per}~{}L(H^{{}^{\prime}})}{\frac{PD(H^{{}^{\prime}})}{d_{w_{i-1}}-1}\times
d_{w_{i-1}}\times\frac{d_{w_{i}}}{d_{w_{i}}-1}PD(T_{r-i})\times(d_{w_{i-1}}+r-i-1)}$
$\displaystyle+\frac{[(d_{w_{i-1}}+r-i-1)~{}{\rm
per}~{}L(T_{r-i})+2~{}(d_{w_{i-1}}+r-i-1)~{}{\rm
per}~{}L_{w_{i}}(T_{r-i})]{\rm
per}~{}L_{w_{i-1}}(H^{{}^{\prime}})}{\frac{PD(H^{{}^{\prime}})}{d_{w_{i-1}}-1}\times
d_{w_{i-1}}\times\frac{d_{w_{i}}}{d_{w_{i}}-1}PD(T_{r-i})\times(d_{w_{i-1}}+r-i-1)}$
$\displaystyle-\frac{2(r-i)d_{w_{i-1}}\times\frac{d_{w_{i}}}{d_{w_{i}}-1}PD(T_{r-i}){\rm
per}~{}L(H^{{}^{\prime}})}{\frac{PD(H^{{}^{\prime}})}{d_{w_{i-1}}-1}\times
d_{w_{i-1}}\times\frac{d_{w_{i}}}{d_{w_{i}}-1}PD(T_{r-i})\times(d_{w_{i-1}}+r-1)}.$

Since $r\geq 2$, $\frac{PD(H^{{}^{\prime}})}{d_{w_{i-1}}-1}\times
d_{w_{i-1}}\times\frac{d_{w_{i}}}{d_{w_{i}}-1}PD(T_{r-i})\times(d_{w_{i-1}}+r-i-1)>0$.
By the definition of $T_{r-i}$ and utilizing the structure of the matrix
$L_{w_{i}}(T_{r-i})$, we obtain ${\rm per}~{}L_{w_{i}}(T_{r-i})\geq 1$. By
Lemma 2.1, we have ${\rm per}~{}L(H^{{}^{\prime}})>(d_{w_{i-1}}-1){\rm
per}~{}L_{w_{i-1}}(H^{{}^{\prime}})$. Since $T_{r-i}$ have diameter at least
$4$ and $\pi(P_{5})=3$, by Lemma 2.7, we have $\pi(T_{r-i})\geq 3$. Since
$d_{w_{i}}\geq 3$, we know that ${\rm per}~{}L(T_{r-i})\geq
3~{}PD(T_{r-i})\geq 2~{}\frac{d_{w_{i}}}{d_{w_{i}}-1}PD(T_{r-i})$. Let
$\Gamma$ denote the numerator of $\pi(G_{1})-\pi(G_{1}^{{}^{\prime}})$, see
(2). Hence

$\displaystyle\Gamma$ $\displaystyle=$
$\displaystyle[(d_{w_{i-1}}+r-i-1)~{}{\rm
per}~{}L(T_{r-i})+(d_{w_{i-1}}+r-i-1)~{}{\rm per}~{}L_{w_{i}}(T_{r-i})$
$\displaystyle-d_{w_{i-1}}\times\frac{d_{w_{i}}}{d_{w_{i}}-1}PD(T_{r-i})]{\rm
per}~{}L(H^{{}^{\prime}})+[(d_{w_{i-1}}+r-i-1)~{}{\rm per}~{}L(T_{r-i})$
$\displaystyle+2~{}(d_{w_{i-1}}+r-i-1)~{}{\rm per}~{}L_{w_{i}}(T_{r-i})]{\rm
per}~{}L_{w_{i-1}}(H^{{}^{\prime}})$
$\displaystyle-2(r-i)d_{w_{i-1}}\times\frac{d_{w_{i}}}{d_{w_{i}}-1}PD(T_{r-i}){\rm
per}~{}L_{w_{i-1}}(H^{{}^{\prime}})$ $\displaystyle>$
$\displaystyle[2(d_{w_{i-1}}+r-i-1)\times\frac{d_{w_{i}}}{d_{w_{i}}-1}PD(T_{r-i})+(d_{w_{i-1}}+r-i-1)$
$\displaystyle-
d_{w_{i}-1}\times\frac{d_{w_{i}}}{d_{w_{i}}-1}PD(T_{r-i})](d_{w_{i-1}}-1){\rm
per}~{}L_{w_{i-1}}(H^{{}^{\prime}})$
$\displaystyle+[2(d_{w_{i-1}}+r-i-1)\times\frac{d_{w_{i}}}{d_{w_{i}}-1}PD(T_{r-i})+2~{}(d_{w_{i-1}}+r-i-1)$
$\displaystyle-2rd_{w_{i}-1}\times\frac{d_{w_{i}}}{d_{w_{i}}-1}PD(T_{r-i})]{\rm
per}~{}L_{w_{i-1}}(H^{{}^{\prime}})$ $\displaystyle=$
$\displaystyle(d_{w_{i-1}}^{2}-d_{w_{i-1}})\times\frac{d_{w_{i}}}{d_{w_{i}}-1}PD(T_{r-i})+(d_{w_{i-1}}+1)(d_{w_{i-1}}+r-i-1)$
$\displaystyle+(r-i)\times\frac{d_{w_{i}}}{d_{w_{i}}-1}PD(T_{r-i}).$

Since $d_{w_{i-1}}\geq 2$, $r>i$, we have
$\pi(G_{1})-\pi(G_{1}^{{}^{\prime}})>0$.

Combining arguments above, it is easy to obtain that
$\pi(G_{1})>\pi(G_{1}^{{}^{\prime}})$.

We are now ready to prove $\pi(G_{1}^{{}^{\prime}})\geq\pi(G_{2})$.

By the definitions of $G_{1}^{{}^{\prime}}$, by (7), we have
$\psi=\frac{1}{d_{u}d_{v}}+\frac{1}{d_{w_{0}}d_{w_{1}}}+\frac{1}{d_{w_{1}}d_{w_{2}}}+\cdots+\frac{1}{d_{w_{i-2}}d_{w_{i-1}}}+\frac{1}{d_{w_{i-1}}d_{v_{1}}}+\frac{1}{d_{w_{i-1}}d_{v_{2}}}+\cdots+\frac{1}{d_{w_{i-1}}d_{v_{r-i}}}$
and $\theta=\frac{r}{d_{u}+r-1}$.

Assume $i\geq 3$. We obtain
$\psi=\frac{1}{2d_{u}}+\frac{i-2}{4}+\frac{1}{2(r-i+1)}+\frac{r-i}{r-i+1}$.
Since $d_{w_{1}}=2$, $d_{w_{i-2}}=2$ and $d_{u}\geq 1$, it is easy to obtain
that $\psi-\theta>\frac{i-2}{4}-\frac{1}{2(r-i+1)}\geq 0$.

Assume that $i=2$. Then $r\geq i+1\geq 3$. If $d_{u}=1$, then
$\psi-\theta=\frac{1}{2}[1-\frac{1}{(r-1)}]>0$. If $d_{u}\geq 2$, then
$\psi-\theta>\frac{r-3}{2(r+1)(r-1)}\geq 0$.

Assume $i=1$. By (ii) of Lemma 2.8, we have
$\pi(G_{1}^{{}^{\prime}})-\pi(G_{2})>0$.

Set $i=0$. We obtain that $G_{1}^{{}^{\prime}}\cong G_{2}$. Hence
$\pi(G_{1}^{{}^{\prime}})=\pi(G_{2})$.

Combining arguments as above, we obtain that
$\pi(G_{1}^{{}^{\prime}})\geq\pi(G_{2})$. ∎

######  Lemma 2.9.

Let $s,t$ be positive integers satisfying $s\geq t$, $T^{{}^{\prime\prime}}$
be a tree with $n\geq 4$ vertices which contains two vertices of degree $2$
$u$ and $v$. Let $T$ be a tree obtained from $T^{{}^{\prime\prime}}$ by
attaching $s$ and $t$ pendant vertices to $u$ and $v$, respectively. Denote by
$T_{1}$ the tree obtained from $T^{{}^{\prime\prime}}$ by attaching $s+t$
pendant vertices to $u$. Denote by $T_{2}$ the tree obtained from
$T^{{}^{\prime\prime}}$ by attaching $s+t$ pendant vertices to $v$. See Figure
3 for illustrations of these graphs. Then $\pi(T)>{\rm
min}\\{\pi(T_{1}),\pi(T_{2})\\}$.

Figure 4: Graphs $T$, $T_{1}$ and $T_{2}$.

###### Proof.

Suppose that $T^{{}^{\prime}}$ is a tree obtained from $T$ by deleting all
vertices $u_{1},u_{2},\cdots,u_{s}$. By the definitions of $T$, $T_{1}$,
$T_{2}$, $T^{{}^{\prime}}$ and $T^{{}^{\prime\prime}}$, we obtain that

$\displaystyle{\rm per}L_{u}(T-u_{1})$ $\displaystyle=$ $\displaystyle{\rm
per}L_{u}(T-u_{1}-u_{2})$ $\displaystyle=$ $\displaystyle\cdots$
$\displaystyle=$ $\displaystyle{\rm per}L_{u}(T-u_{1}-u_{2}-\cdots-
u_{s-1}-u_{s})$ $\displaystyle=$ $\displaystyle{\rm
per}L_{u}(T^{{}^{\prime}}),$ $\displaystyle{\rm
per}L_{v}(T^{{}^{\prime}}-v_{1})$ $\displaystyle=$ $\displaystyle{\rm
per}L_{v}(T^{{}^{\prime}}-v_{1}-v_{2})$ $\displaystyle=$ $\displaystyle\cdots$
$\displaystyle=$ $\displaystyle{\rm
per}L_{v}(T^{{}^{\prime}}-v_{1}-v_{2}-\cdots-v_{t-1}-v_{t})$ $\displaystyle=$
$\displaystyle{\rm per}L_{v}(T^{{}^{\prime\prime}}),$ $\displaystyle{\rm
per}L_{u}(T_{1}-u_{1})$ $\displaystyle=$ $\displaystyle{\rm
per}L_{u}(T_{1}-u_{1}-u_{2})$ $\displaystyle=$ $\displaystyle\cdots$
$\displaystyle=$ $\displaystyle{\rm per}L_{u}(T_{1}-u_{1}-u_{2}-\cdots-
u_{s-1}-u_{s})$ $\displaystyle=$ $\displaystyle{\rm
per}L_{u}(T_{1}-u_{1}-u_{2}-\cdots-u_{s-1}-u_{s}-v_{1})$ $\displaystyle=$
$\displaystyle{\rm per}L_{u}(T_{1}-u_{1}-u_{2}-\cdots-
u_{s-1}-u_{s}-v_{1}-v_{2})$ $\displaystyle=$ $\displaystyle\cdots$
$\displaystyle=$ $\displaystyle{\rm per}L_{u}(T_{1}-u_{1}-u_{2}-\cdots-
u_{s-1}-u_{s}-v_{1}-v_{2}-\cdots-v_{t-1}-v_{t})$ $\displaystyle=$
$\displaystyle{\rm per}L_{u}(T^{{}^{\prime\prime}})$

and

$\displaystyle{\rm per}L_{v}(T_{2}-u_{1})$ $\displaystyle=$ $\displaystyle{\rm
per}L_{v}(T_{2}-u_{1}-u_{2})$ $\displaystyle=$ $\displaystyle\cdots$
$\displaystyle=$ $\displaystyle{\rm per}L_{v}(T_{2}-u_{1}-u_{2}-\cdots-
u_{s-1}-u_{s})$ $\displaystyle=$ $\displaystyle{\rm
per}L_{v}(T_{2}-u_{1}-u_{2}-\cdots-u_{s-1}-u_{s}-v_{1})$ $\displaystyle=$
$\displaystyle{\rm per}L_{v}(T_{2}-u_{1}-u_{2}-\cdots-
u_{s-1}-u_{s}-v_{1}-v_{2})$ $\displaystyle=$ $\displaystyle\cdots$
$\displaystyle=$ $\displaystyle{\rm per}L_{v}(T_{2}-u_{1}-u_{2}-\cdots-
u_{s-1}-u_{s}-v_{1}-v_{2}-\cdots-v_{t-1}-v_{t})$ $\displaystyle=$
$\displaystyle{\rm per}L_{v}(T^{{}^{\prime\prime}}).$

By Lemma 2.3, deleting $u_{1}$, $u_{2}$, $\cdots$, $u_{s}$, $v_{1}$, $v_{2}$,
$\cdots$, $v_{t}$ one by one in $T$, $T_{1}$ and $T_{2}$, we obtain that

$\displaystyle{\rm per}L(T)$ $\displaystyle=$ $\displaystyle{\rm
per}L(T-u_{1})+2~{}{\rm per}L_{u}(T-u_{1})$ $\displaystyle=$
$\displaystyle{\rm per}L(T-u_{1}-u_{2})+2~{}{\rm per}L_{u}(T-u_{1})+2~{}{\rm
per}L_{u}(T-u_{1}-u_{2})$ $\displaystyle=$ $\displaystyle\cdots$
$\displaystyle=$ $\displaystyle{\rm per}L(T-u_{1}-u_{2}-\cdots-u_{s})+2~{}{\rm
per}L_{u}(T-u_{1})+2~{}{\rm per}L_{u}(T-u_{1}-u_{2})$
$\displaystyle+\cdots+2~{}{\rm per}L_{u}(T-u_{1}-u_{2}-\cdots-u_{s-1}-u_{s})$
$\displaystyle=$ $\displaystyle{\rm per}L(T^{{}^{\prime}})+2s~{}{\rm
per}L_{u}(T^{{}^{\prime}})$ $\displaystyle=$ $\displaystyle{\rm
per}L(T^{{}^{\prime}}-v_{1})+2s~{}{\rm per}L_{u}(T^{{}^{\prime}})+2~{}{\rm
per}L_{v}(T^{{}^{\prime}}-v_{1})$ $\displaystyle=$ $\displaystyle{\rm
per}L(T^{{}^{\prime}}-v_{1}-v_{2})+2s~{}{\rm
per}L_{u}(T^{{}^{\prime}})+2~{}{\rm per}L_{v}(T^{{}^{\prime}}-v_{1})+2~{}{\rm
per}L_{v}(T^{{}^{\prime}}-v_{1}-v_{2})$ $\displaystyle=$ $\displaystyle\cdots$
$\displaystyle=$ $\displaystyle{\rm per}L(T^{{}^{\prime}}-v_{1}-v_{2}-\cdots-
v_{t-1}-v_{t})+2s~{}{\rm per}L_{u}(T^{{}^{\prime}})+2~{}{\rm
per}L_{v}(T^{{}^{\prime}}-v_{1})$ $\displaystyle+2~{}{\rm
per}L_{v}(T^{{}^{\prime}}-v_{1}-v_{2})+\cdots+2{\rm
per}L_{v}(T^{{}^{\prime}}-v_{1}-v_{2}-\cdots-v_{t-1}-v_{t})$ $\displaystyle=$
$\displaystyle{\rm per}L(T^{{}^{\prime}}-v_{1}-v_{2}-\cdots-
v_{t-1}-v_{t})+2s~{}{\rm per}L_{u}(T^{{}^{\prime}})+2t~{}{\rm
per}L_{v}(T^{{}^{\prime\prime}})$ $\displaystyle=$ $\displaystyle{\rm
per}L(T^{{}^{\prime\prime}})+2s~{}{\rm per}L_{u}(T^{{}^{\prime}})+2t~{}{\rm
per}L_{v}(T^{{}^{\prime\prime}}),$ $\displaystyle{\rm per}L(T_{1})$
$\displaystyle=$ $\displaystyle{\rm per}L(T_{1}-u_{1})+2~{}{\rm
per}L_{u}(T_{1}-u_{1})$ $\displaystyle=$ $\displaystyle{\rm
per}L(T_{1}-u_{1}-u_{2})+2~{}{\rm per}L_{u}(T_{1}-u_{1})+2~{}{\rm
per}L_{u}(T_{1}-u_{1}-u_{2})$ $\displaystyle=$ $\displaystyle\cdots$
$\displaystyle=$ $\displaystyle{\rm per}L(T_{1}-u_{1}-u_{2}-\cdots-
u_{s}-v_{1}-v_{2}-\cdots-v_{t-1}-v_{t})$ $\displaystyle+2~{}{\rm
per}L_{u}(T_{1}-u_{1})+2~{}{\rm per}L_{u}(T_{1}-u_{1}-u_{2})+\cdots+2{\rm
per}L_{u}(T_{1}$ $\displaystyle-u_{1}-u_{2}-\cdots-
u_{s-1}-u_{s}-v_{1}-v_{2}-\cdots-v_{t-1}-v_{t})$ $\displaystyle=$
$\displaystyle{\rm per}L(T^{{}^{\prime\prime}})+2(s+t)~{}{\rm
per}L_{u}(T^{{}^{\prime\prime}}),$ $\displaystyle{\rm per}L(T_{2})$
$\displaystyle=$ $\displaystyle{\rm per}L(T_{2}-u_{1})+2~{}{\rm
per}L_{v}(T_{2}-u_{1})$ $\displaystyle=$ $\displaystyle{\rm
per}L(T_{2}-u_{1}-u_{2})+2~{}{\rm per}L_{v}(T_{2}-u_{1})+2~{}{\rm
per}L_{v}(T_{2}-u_{1}-u_{2})$ $\displaystyle=$ $\displaystyle\cdots$
$\displaystyle=$ $\displaystyle{\rm per}L(T_{2}-u_{1}-u_{2}-\cdots-
u_{s-1}-u_{s}-v_{1}-v_{2}-\cdots-v_{t-1}-v_{t})$ $\displaystyle+2~{}{\rm
per}L_{v}(T_{2}-u_{1})+2~{}{\rm per}L_{v}(T_{2}-u_{1}-u_{2})+\cdots+2~{}{\rm
per}L_{v}(T_{2}$ $\displaystyle-u_{1}-u_{2}-\cdots-
u_{s-1}-u_{s}-v_{1}-v_{2}-\cdots-v_{t-1}-v_{t})$ $\displaystyle=$
$\displaystyle{\rm per}L(T^{{}^{\prime\prime}})+2(s+t)~{}{\rm
per}L_{v}(T^{{}^{\prime\prime}}).$

By the definitions of $T^{{}^{\prime\prime}}$, $T$, $T_{1}$ and $T_{2}$.
Direct computing yields

$\displaystyle PD(T)$ $\displaystyle=$
$\displaystyle\frac{(s+2)(t+2)}{4}PD(T^{{}^{\prime\prime}}),$ $\displaystyle
PD(T_{1})$ $\displaystyle=$
$\displaystyle\frac{(s+t+2)}{2}PD(T^{{}^{\prime\prime}}),$ $\displaystyle
PD(T_{2})$ $\displaystyle=$
$\displaystyle\frac{(s+t+2)}{2}PD(T^{{}^{\prime\prime}}).$

Hence

$\displaystyle\pi(T)$ $\displaystyle=$ $\displaystyle\frac{{\rm
per}L(T)}{\frac{(s+2)(t+2)}{4}PD(T^{{}^{\prime\prime}})}=\frac{4}{PD(T^{{}^{\prime\prime}})}[\frac{{\rm
per}L(T^{{}^{\prime\prime}})}{(s+2)(t+2)}+\frac{2s~{}{\rm
per}L_{u}(T^{{}^{\prime}})+2t~{}{\rm
per}L_{v}(T^{{}^{\prime\prime}})}{(s+2)(t+2)}],$ $\displaystyle\pi(T_{1})$
$\displaystyle=$ $\displaystyle\frac{{\rm
per}L(T_{1})}{\frac{(s+t+2)}{2}PD(T^{{}^{\prime\prime}})}=\frac{4}{PD(T^{{}^{\prime\prime}})}[\frac{{\rm
per}L(T^{{}^{\prime\prime}})}{2(s+t+2)}+\frac{2(s+t)~{}{\rm
per}L_{u}(T^{{}^{\prime\prime}})}{2(s+t+2)}],$ $\displaystyle\pi(T_{2})$
$\displaystyle=$ $\displaystyle\frac{{\rm
per}L(T_{2})}{\frac{(s+t+2)}{2}PD(T^{{}^{\prime\prime}})}=\frac{4}{PD(T^{{}^{\prime\prime}})}[\frac{{\rm
per}L(T^{{}^{\prime\prime}})}{2(s+t+2)}+\frac{2(s+t)~{}{\rm
per}L_{v}(T^{{}^{\prime\prime}})}{2(s+t+2)}].$

Since $d(v)=2$, the matrix $L(T^{{}^{\prime\prime}})$ has the following form

$\displaystyle
L(T^{{}^{\prime\prime}})=\left[\begin{matrix}\begin{array}[]{ccccc|c|ccccc}&&&&&0&&&&\\\
&&&&&\vdots&&&&\\\ &&A&&&0&&&&\\\ &&&&&0&&&&\\\ &&&&&-1&&&&\\\ \hline\cr
0&\cdots&0&0&-1&2&-1&0&0&\cdots&0\\\ \hline\cr&&&&&-1&&&&&\\\ &&&&&0&&&&&\\\
&&&&&0&&&B&&\\\ &&&&&\vdots&&&&&\\\ &&&&&0&&&&&\\\
\end{array}\end{matrix}\right],$ (9)

where $A$ and $B$ are two submatrices.

And the matrix $L_{u}(T^{{}^{\prime\prime}})$ has the following form

$L_{u}(T^{{}^{\prime\prime}})=\left[\begin{matrix}\begin{array}[]{ccccc|c|ccccc|c}&&&&&0&&&&&\\\
&&&&&\vdots&&&&&\\\ &&A&&&0&&&&&\\\ &&&&&0&&&&&\\\ &&&&&-1&&&&&\\\ \hline\cr
0&\cdots&0&0&-1&2&-1&0&0&\cdots&0&\\\ \hline\cr&&&&&-1&&&&&&\\\
&&&&&0&&&&&&\\\ &&&&&0&&&B^{{}^{\prime}}&&&\\\ &&&&&\vdots&&&&&&\\\
&&&&&0&&&&&&\\\ \hline\cr&&&&&&&&&&&C\\\ \end{array}\end{matrix}\right]$,
where $A$ , $B^{{}^{\prime}}$ and $C$ are three submatrices.

Similarly, since the vertex $v$ in $T^{{}^{\prime}}$ has degree $t+2$, the
matrix $L_{u}(T^{{}^{\prime}})$ has the following form

$L_{u}(T^{{}^{\prime}})=\left[\begin{matrix}\begin{array}[]{ccccc|ccccc|ccccc|c}&&&&&0&&&&&&&&&&\\\
&&&&&\vdots&&&&&&&&&&\\\ &&A&&&0&&&&&&&&&&\\\ &&&&&0&&&&&&&&&&\\\
&&&&&-1&&&&&&&&&&\\\ \hline\cr
0&\cdots&0&0&-1&t+2&-1&-1&\cdots&-1&-1&0&0&\cdots&0&\\\ &&&&&-1&1&&&&&&&&&\\\
&&&&&-1&&1&&&&&&&&\\\ &&&&&\vdots&&&\ddots&&&&&&&\\\ &&&&&-1&&&&1&&&&&&\\\
\hline\cr&&&&&-1&&&&&&&&&&\\\ &&&&&0&&&&&&&&&&\\\
&&&&&0&&&&&&&B^{{}^{\prime}}&&&\\\ &&&&&\vdots&&&&&&&&&&\\\
&&&&&0&&&&&&&&&&\\\ \hline\cr&&&&&&&&&&&&&&&C\\\
\end{array}\end{matrix}\right]$.

Suppose that $M$ is the matrix obtained by deleting the last row and the last
column in $A$. Let $N$ be the matrix obtained by deleting the first row and
the first column in $B$, and let $N^{{}^{\prime}}$ be the matrix obtained by
deleting the first row and the first column in $B^{{}^{\prime}}$. Direct
computing yields

${\rm per}L(T^{{}^{\prime\prime}})=2~{}{\rm per}A{\rm per}B+{\rm per}M{\rm
per}B+{\rm per}A{\rm per}N,$ $\displaystyle{\rm
per}L_{u}(T^{{}^{\prime}})={\rm per}C[(s+s+2)~{}{\rm per}A{\rm
per}B^{{}^{\prime}}+{\rm per}M{\rm per}B^{{}^{\prime}}+{\rm per}A{\rm
per}N^{{}^{\prime}}],$ (10) $\displaystyle{\rm
per}L_{u}(T^{{}^{\prime\prime}})={\rm per}C(2~{}{\rm per}A{\rm
per}B^{{}^{\prime}}+{\rm per}M{\rm per}B^{{}^{\prime}}+{\rm per}A{\rm
per}N^{{}^{\prime}}).$ (11)

Thus,

$2~{}{\rm per}A{\rm per}B\leq{\rm per}L(T^{{}^{\prime\prime}})\leq 4~{}{\rm
per}A{\rm per}B,$ $\displaystyle 2~{}{\rm per}A{\rm
per}B^{{}^{\prime}}\leq{\rm per}L_{u}(T^{{}^{\prime\prime}})\leq 4~{}{\rm
per}A{\rm per}B^{{}^{\prime}},$ (12)

Combining (10), (11) and (12), we have

$\displaystyle{\rm per}L_{u}(T^{{}^{\prime}})\geq\frac{5(s+t)}{4}~{}{\rm
per}L_{u}(T^{{}^{\prime\prime}}).$ (13)

By (9), we have ${\rm per}A{\rm per}B={\rm per}L_{u}(T^{{}^{\prime\prime}})$.
Therefore $2{\rm per}L_{v}(T^{{}^{\prime\prime}})\leq{\rm
per}L(T^{{}^{\prime\prime}})\leq 4{\rm per}L_{v}(T^{{}^{\prime\prime}})$.
Similarly we have $2{\rm per}L_{u}(T^{{}^{\prime\prime}})\leq{\rm
per}L(T^{{}^{\prime\prime}})\leq 4{\rm per}L_{u}(T^{{}^{\prime\prime}})$.

$\displaystyle\Delta_{1}$ $\displaystyle=$ $\displaystyle\pi(T)-\pi(T_{1})$
$\displaystyle=$ $\displaystyle\frac{4}{PD(T^{{}^{\prime\prime}})}[\frac{{\rm
per}L(T^{{}^{\prime\prime}})}{(s+2)(t+2)}+\frac{2s~{}{\rm
per}L_{u}(T^{{}^{\prime}})+2t~{}{\rm
per}L_{v}(T^{{}^{\prime\prime}})}{(s+2)(t+2)}]$
$\displaystyle-\frac{4}{PD(T^{{}^{\prime\prime}})}[\frac{{\rm
per}L(T^{{}^{\prime\prime}})}{2(s+t+2)}+\frac{2(s+t){\rm
per}L_{u}(T^{{}^{\prime\prime}})}{2(s+t+2)}]$ $\displaystyle=$
$\displaystyle\frac{4}{PD(T^{{}^{\prime\prime}})}[(\frac{1}{(s+2)(t+2)}-\frac{1}{2(s+t+2)})~{}{\rm
per}L(T^{{}^{\prime\prime}})+(\frac{2s~{}{\rm
per}L_{u}(T^{{}^{\prime}})+2t~{}{\rm
per}L_{v}(T^{{}^{\prime\prime}})}{(s+2)(t+2)}$
$\displaystyle-\frac{2(s+t)~{}{\rm
per}L_{u}(T^{{}^{\prime\prime}})}{2(s+t+2)})]$ $\displaystyle\geq$
$\displaystyle\frac{4}{PD(T^{{}^{\prime\prime}})}[(\frac{1}{(s+2)(t+2)}-\frac{1}{2(s+t+2)})\times
4~{}{\rm per}L_{u}(T^{{}^{\prime\prime}})$ $\displaystyle+(\frac{2s~{}{\rm
per}L_{u}(T^{{}^{\prime}})+2t~{}{\rm
per}L_{v}(T^{{}^{\prime\prime}})}{(s+2)(t+2)}-\frac{2(s+t)~{}{\rm
per}L_{u}(T^{{}^{\prime\prime}})}{2(s+t+2)})].$

$\displaystyle\Delta_{2}$ $\displaystyle=$ $\displaystyle\pi(T)-\pi(T_{2})$
$\displaystyle=$ $\displaystyle\frac{4}{PD(T^{{}^{\prime\prime}})}[\frac{{\rm
per}L(T^{{}^{\prime\prime}})}{(s+2)(t+2)}+\frac{2s~{}{\rm
per}L_{u}(T^{{}^{\prime}})+2t~{}{\rm
per}L_{v}(T^{{}^{\prime\prime}})}{(s+2)(t+2)}]$
$\displaystyle-\frac{4}{PD(T^{{}^{\prime\prime}})}[\frac{{\rm
per}L(T^{{}^{\prime\prime}})}{2(s+t+2)}+\frac{2(s+t)~{}{\rm
per}L_{v}(T^{{}^{\prime\prime}})}{2(s+t+2)}]$ $\displaystyle=$
$\displaystyle\frac{4}{PD(T^{{}^{\prime\prime}})}[(\frac{1}{(s+2)(t+2)}-\frac{1}{2(s+t+2)})~{}{\rm
per}L(T^{{}^{\prime\prime}})+(\frac{2s~{}{\rm
per}L_{u}(T^{{}^{\prime}})+2t~{}{\rm
per}L_{v}(T^{{}^{\prime\prime}})}{(s+2)(t+2)}$
$\displaystyle-\frac{2(s+t)~{}{\rm
per}L_{v}(T^{{}^{\prime\prime}})}{2(s+t+2)})]$ $\displaystyle\geq$
$\displaystyle\frac{4}{PD(T^{{}^{\prime\prime}})}[(\frac{1}{(s+2)(t+2)}-\frac{1}{2(s+t+2)})\times
4~{}{\rm per}L_{u}(T^{{}^{\prime\prime}})$ $\displaystyle+(\frac{2s~{}{\rm
per}L_{u}(T^{{}^{\prime}})+2t~{}{\rm
per}L_{v}(T^{{}^{\prime\prime}})}{(s+2)(t+2)}-\frac{2(s+t)~{}{\rm
per}L_{v}(T^{{}^{\prime\prime}})}{2(s+t+2)})].$

If ${\rm per}L_{u}(T^{{}^{\prime\prime}})\geq{\rm
per}L_{v}(T^{{}^{\prime\prime}})$, then we obtain from (13) that

$\Delta_{1}\geq\frac{(\frac{3}{4}t^{2}+2st+\frac{1}{2}t+\frac{3}{2}s+\frac{5}{4}s^{2}-2)s~{}{\rm
per}L_{v}(T^{{}^{\prime\prime}})}{\frac{1}{2}(s+2)(t+2)(s+t+2)}.$

Since $s\geq t\geq 1$, it follows that $\Delta_{1}>0$.

If ${\rm per}L_{u}(T^{{}^{\prime\prime}})<{\rm
per}L_{v}(T^{{}^{\prime\prime}})$, then we obtain from (13) that

$\Delta_{2}\geq\frac{(\frac{3}{4}st^{2}+2s^{2}t+\frac{1}{2}st+\frac{5}{4}s^{3}+\frac{3}{2}s^{2}+2t-2s)~{}{\rm
per}L_{u}(T^{{}^{\prime\prime}})}{\frac{1}{2}(s+2)(t+2)(s+t+2)}.$

Since $s\geq t\geq 1$, it follows that $\Delta_{2}>0$.

Combining the arguments as above, we have $\pi(T)>{\rm
min}\\{\pi(T_{1}),\pi(T_{2})\\}$. ∎

######  Lemma 2.10.

([2]) Let $T$ be a tree with $n$ vertices and diameter at least $k$. Then

${\rm per}L(T)\geq{\rm per}L(B(n,k)),$

where equality holds if and only if $T$ is broom $B(n,k)$.

######  Lemma 2.11.

([2]) Let $n\geq 3$ and $k\geq 2$. Suppose that $Q_{k}$ is the matrix obtained
from $L(P_{n+1})$ by eliminating row $1$ and column $1$. Then

${\rm per}L(B(n,k)=(2n-2k+1){\rm per}Q_{k-1}+{\rm per}Q_{k-2},$ ${\rm
per}Q_{k}=\frac{1}{2}(1+\sqrt{2})^{k}+\frac{1}{2}(1-\sqrt{2})^{k}.$

Proof of Theorem 1.1. Let $T$ be a tree with $n$ vertices having diameter $k$.
Suppose that $v_{1}v_{2}\cdots v_{k+1}$ is a path with diameter $k$ in $T$.
All branches hanged on the vertex $v_{i}(i=2,3,\cdots,k)$ in path
$v_{1}v_{2}\cdots v_{k+1}$ are changed into a star with the center $v_{i}$,
and the number of pendents vertices of the star equals to the number of
vertices of all branches. Then, $T$ is transformed into a caterpillar $T_{0}$
whose spine is the path $v_{1}v_{2}\cdots v_{k+1}$. By (iii) of Lemma 2.8, we
have $\pi(T)\geq\pi(T_{0})$. Repeated merging the leaves of vertices $v_{i}$
and $v_{j}$ into $v_{i}$ or $v_{j}$ in path $v_{1}v_{2}\cdots v_{k+1}$,
$T_{0}$ is transformed into $T_{1}$ which is a new caterpillar obtained by
joining $n-k-1$ vertices to the vertex $v_{s}$ of path $v_{1}v_{2}\cdots
v_{k+1}$, where $2\leq i,j,s\leq k+1$. By Lemma 2.9, it can be known that
$\pi(T_{0})\geq\pi(T_{1})$. Since $PD(T_{1})=PD(B(n,k))$, by Lemma 2.10, we
have $\pi(T_{1})\geq\pi(B(n,k))$. For all broom graphs with $n$ vertices
having diameter at least $k$, by (ii) of Lemma 2.8, it is easy to obtain that
$\pi(B(n,k))$ is minimum. So,

$\pi(T)\geq\frac{{\rm per}B(n,k)}{PD(B(n,k))},$

By Lemma 2.11, we obtain that

$\pi(T)\geq\biggl{[}1+\sqrt{2}-\frac{\sqrt{2}}{2(n-k+1)}\biggl{]}\biggl{(}\frac{1+\sqrt{2}}{2}\biggl{)}^{k-2}+\biggl{[}1-\sqrt{2}+\frac{\sqrt{2}}{2(n-k+1)}\biggl{]}\biggl{(}\frac{1-\sqrt{2}}{2}\biggl{)}^{k-2}$

with equality holding if and only if $T$ is broom $B(n,k)$. $\Box$

##  3 Summarize

In this paper, we determined the lower bound of Laplacian ratios of trees, and
the corresponding extremal graph is also determined. In general it is
difficult to evaluate Laplacian ratios of graphs, unless the graphs are of
very special type. It is precisely because of the difficulty of the
calculation of Laplacian ratio that there are a few published papers on
Laplacian ratio. Except for the problems raised by Brualdi and Goldwasser,
there exist some problems to worth study. Such as: characterizing the bound of
Laplacian ratios of general graphs, and determining the bound of Laplacian
ratios of general graphs with given graph parameters, etc.. These problems are
the direction of our future research.

Conflict of Interest Statement

The authors declare that they have no conflicts of interest.

## References

  * [1] L.G. Valiant, The complexity of computing the permanent, Theor. Comput. Sci. 8 (1979) 189–201.
  * [2] R.A. Brualdi, J.L. Goldwasser, Permanent of the Laplacian matrix of trees and bipartite graphs,  Discrete Math. 48 (1984) 1–21.
  * [3] J.L. Goldwasser, Permanent of the Laplacian matrix of trees with a given mathching,  Discrete Math. 61 (1986) 197–212.


# Iterative Bounding Box Annotation for Object Detection

Bishwo Adhikari  Tampere University, Finland
<EMAIL_ADDRESS>Heikki Huttunen  Tampere University, Finland
<EMAIL_ADDRESS>
###### Abstract

Manual annotation of bounding boxes for object detection in digital images is
tedious, and time and resource consuming. In this paper, we propose a semi-
automatic method for efficient bounding box annotation. The method trains the
object detector iteratively on small batches of labeled images and learns to
propose bounding boxes for the next batch, after which the human annotator
only needs to correct possible errors. We propose an experimental setup for
simulating the human actions and use it for comparing different iteration
strategies, such as the order in which the data is presented to the annotator.
We experiment on our method with three datasets and show that it can reduce
the human annotation effort significantly, saving up to 75% of total manual
annotation work.

##  I Introduction

Object detection is one of the core research fields in machine learning and
computer vision. Recently, object detection algorithms have matured enough to
solve real-world vision problems. It serves as the key component in
application fields such as face detection [1], pedestrian detection [2],
surveillance systems [3], autonomous vehicles [4, 5], etc. The supervised
learning principle is widely used in current object detection systems, where a
human labeled dataset is used for training the detection model. The
performance of supervised machine learning models relies heavily on the amount
and quality of annotated training data. However, the challenge in supervised
object detection is collecting large, high-quality labeled datasets with the
aim of having a well-performing object detection model.

Recently, both the scale and the variety of public datasets for object
detection has increased. Among the most popular ones are PASCAL VOC [6], MS
COCO [7], OpenImages [8], and Kitti [4] and they are widely used as benchmark
datasets in the field of object detection. The labor-intensive and tedious job
of object annotation for these large datasets has often been solved by
crowdsourcing [9] a large number of human annotators on web platforms such as
Amazon Mechanical Turk. However, crowdsourcing may not be a feasible option
for annotating small and medium-sized datasets, when the data is confidential
in nature, or simply when annotation resources are limited. Hence, there is
demand for resource-efficient, user-friendly annotation tools to prepare
labeled dataset for machine learning.

Researchers have been mainly focusing on two approaches to reduce the cost of
bounding box annotation, weakly-supervised and active learning methods. The
weakly-supervised approach uses images and corresponding object labels and
lets the network draw bounding boxes. On the other hand the active learning
approach trains the model and requests human to draw bounding boxes on a
subset of images actively selected by the learner itself. These approaches
still require a significant amount of human annotator time for drawing high-
quality bounding boxes.

In this paper, we present a simple and practical heuristic to annotate the
bounding boxes on image datasets. The iterative annotation approach takes
advantage of the trained model to propose labels for a batch of unlabeled
images leaving the annotator only for correction work. Thus reducing the
workload of annotation. Compared to other approaches, the iterative approach
alternating between training-prediction-annotation balances in the work
between machine and annotator for training and correction.

Although commercial and open source tools that learn while annotating do exist
(e.g., hasty.ai [10] and ilastic [11]), there is only a limited amount of
academic research on the topic. Moreover, our particular focus is not on tool
development, but rather a systematic study investigating different strategies
for an annotation campaign; in particular the order in which the images are
presented to the annotator. To this aim, we describe an easy-to-use measure of
workload based on precision and recall metrics of the learnt machine learning
model.

Figure 1: Our purposed system for iterative bounding box annotation. The
object detection model is trained on a small batch of manually annotated
images. The trained model is used to predict labels on an unlabeled batch,
followed by manual correction. After the first round of train-infer-
correction, detector is trained on the recently labeled batch. This process
continues in a loop until all unlabeled batches are labeled.

Our proposed strategy significantly reduces the workload to create environment
specific object detection datasets. Iterative training strategy is handy for a
data annotation campaign, reduces tedious manual work by assisting annotators
in real-time. A single annotator can efficiently annotate whole dataset
utilizing a partly trained detector with our iterative training – labels
proposal method. We experiment with the continual learning [12] effect, an
ability of network to learn consecutive tasks without forgetting how to
perform on previously trained task, on object detection models in an iterative
loop. Additionally, the catastrophic-forgetting [12] behaviour of object
detection models are experimented with multiple approaches. The term
catastrophic forgetting resembles neural networks tendency of forgetting
knowledge from the former data after learning from the new data.

The rest of this paper is structured as follows. We review the related
literature on object annotation in Section II. This is followed by a detailed
discussion of the individual components of the proposed iterative annotation
method in Section III. Next, we present our experimental setup with a brief
description of the dataset and pre-processing approaches together with the
discussion of experimental results in Section IV. Finally, in Section V, we
conclude our work and consider potential research directions for the future.

##  II Related Work

Object annotation in digital images has been widely studied since the first
object detection methods were proposed in computer vision. There have been
many studies focusing on speeding up the image dataset annotation for object
detection task. In [13, 14, 15], Papadopoulos et al. proposed multiple
approaches for bounding box annotation. In their bounding box verification
approach [13], annotator only needs to verify the label proposed by the
network with an accept/reject decision by human. In the click supervision
approach [14], the human annotator marks the point in the center of object in
an image; and in the extreme clicking approach [15], annotator clicks on four
physical points on the object: the top, bottom, left- and right-most points.

Among these works, the box verification approach [13] is the most similar to
the proposed one. However, the proposed approach is different from all of
these methods in that (1) we treat the object detector as a whole instead of
splitting the task into object proposal and classification stages; (2) our
human involvement is different (i.e., bounding box correction instead of
verification); (3) we evaluate the performance in terms of total workload; and
(4) we also study the order in which the examples are presented to the
annotator directing the research towards active learning.

Konyushkova et al. proposed learning intelligent dialogs [16] that takes
advantage of a trained network to a draw bounding box on image. It requires
human annotator to verify the bounding box proposed by the detector in all
images. Again, our human interaction model is more straightforward (correction
instead if yes/no verification), which in fact simplifies the task and the
total workload (as most proposals need no action).

In our previous paper [17], we used a two-stage semi-automatic approach to
speed up bounding box annotation on labeling small training dataset and
correction of network proposals. The proposed approach is related, but we
extend the two-stage approach into an iterative training loop with unlimited
number of training iterations rather than just two.

There are commercial annotations tools available, such as hasty.ai [10] and
ilastic [11]. Although these tools exist already, the semi-automatic
annotation approach specifically in bounding box annotation has not been
studied in the literature. To the best of our knowledge, this is the first
systematic study of how different strategies could work in manual annotations
workload reduction.

##  III Method

Our focus is in the iterative annotation framework illustrated in Figure 1.
This annotation framework uses an incremental learning approach on a small
batch of manually labeled images, trains a detection model, uses freshly
trained model to propose bounding boxes on a batch of unlabeled images, and
requests the annotator do the correction on possible incorrect bounding boxes
or labels proposals. The involvement of human annotators is only in the
correction stage, hence, decrease the tedious task of manual annotation.
Algorithm 1 summaries all steps of the iterative training method. Next, we
will describe each component of our method.

0: Set of unlabeled images split to $M+1$ distinct annotation batches
$B_{0},\ldots,B_{M+1}$

1: annotate images in batch $B_{0}$ manually

2: train object detection model with images from $B_{0}$

3: for $i\in 1,2,\ldots,M$ do

4: propose annotations for batch $B_{i}$ using the current prediction model

5: do manual correction for the proposals

6: fine-tune the object detection model with batch $B_{i}$

7: end for

return fully labeled dataset

Algorithm 1 Iterative annotation

###  III-A Manual Annotation

The first step is to fully annotate the first batch of (say, 50) images from
the unlabeled dataset. This stage is fully manual and requires human
involvement to draw bounding boxes and provide class label on images. We use a
basic bounding box annotation tools with no extra speed up procedures. The
ways of selecting images batch for manual annotation are described later in
Section IV-C.

###  III-B Object Detection Model Training

The second step is to train the object detection model. Although any detector
can be used, we focus on the recent deep learning-based object detection
models. The common practice is to use a pre-trained network and fine-tune on a
new dataset [18]. We choose two pre-trained networks trained on the MS COCO
[7] dataset and fine-tune on other widely used datasets. Details of our
training strategies are explained in Section IV.

###  III-C Bounding Box Proposals

After fine-tuning the object detection model with the batches annotated so
far, it is used to predict bounding boxes for the next batch of unlabeled
images. The most recently trained detection model proposes bounding boxes and
class labels on the next unlabeled batch of images.

###  III-D Manual Correction

The proposed annotations are inspected and manually corrected by a human
annotator. The human annotator needs to go through all the proposed labels and
bounding boxes. Incorrectly predicted boxes are removed, wrongly labeled
classes are corrected and new boxes are drawn, if needed. As the model is
presented more samples during the iterations, the human workload should
decrease, and the user only needs to accept the boxes in most cases.

###  III-E Estimating the Workload

Our goal is to estimate the human workload in a simulated setting, attempting
to find out how much time a human would spend on a full annotation campaign.
Namely, we can compute the number of corrections required from the user with
the commonly used precision and recall metrics. More specifically, the
datasets are fully annotated, but we will process them iteratively to measure
how much work a human would have done at each stage; and to compare different
strategies how this could have been done faster.

The amount of overlap between the ground truth label and the predicted
bounding box is used to define the false positives and false negatives. We
assume the user would correct the annotation if the intersection-over-union
(IoU) overlap between the true object location and the predicted bounding box
is less than 50%, which is commonly used in performance evaluation in object
detection.

The formula to calculate the amount of corrections to bounding boxes and class
labels is adopted from Adhikari et al. [17]. The number of additions the user
would have to perform for the next batch $B$ of images is given as

$\text{\\# additions}=(\text{\\# of true objects})\times(1-\text{recall}),$

with the recall metric computed from ground truth annotations for $B$.
Moreover, the number of removals the user would have to perform (for false
positives) is given as

$\text{\\# removals}=(\text{\\# of all
detections})\times(1-\text{precision}).$

with the precision computed from ground truth annotations for $B$. Finally,
the total correction work is the sum of these two steps:

$\text{\\# corrections}=\text{\\# additions}+\text{\\# removals}.$

In an ideal case, when the detection model is good enough, the correction work
on proposed bounding boxes should take significantly less time than drawing
new boxes [17]. Additionally, in the case of partial overlap less than 50%, we
model the user operation as removal of the incorrect box and addition of the
box at the correct location.

###  III-F Labeled Dataset

After every correction stage, the fully labeled batch is gathered and use for
training the detection model for the next iteration. The cycle of training
detection model, bounding box inference and correcting on proposed annotations
loop continues until all unlabeled images are fully labeled. Hence, the loop
produces a fully labeled image dataset for object detection in iterative loop
with reduced workload for human annotator.

##  IV Experiments and Results

In this section, we evaluate the efficiency of the proposed approach. More
specifically, we experiment on the iterative annotation with a number of
detection architectures and datasets; both described below.

###  IV-A Models

For detection architectures, we study the following two commonly used
configurations. Both networks were trained starting with weights pre-trained
with MS COCO dataset [7].

Faster RCNN—The faster region convolutional neural network (Faster RCNN)
framework proposed by Ren et al. [19] is a two-stage detector, where the first
stage network creates object proposals, followed by the second stage network
classifying the proposals into different categories. For the backbone, we use
the 50-layer variant of the residual convolutional network (Resnet50) [20].

SSD—A commonly used lightweight detection architecture, the single shot
detector (SSD) framework was proposed by Liu et al. [21]. Since the detections
are produced directly in a single forward pass of the network, it is often the
model of choice for resource limited inference scenarios. For the backbone, we
use the Mobilenet V2 [22].

These particular models were selected since Faster RCNN is typically more
accurate in detection, while the SSD is faster in inference. As detection
model complexity plays crucial role in training, it is always worth to put
some effort on model selection for the particular use case. Moreover, the idea
is to experiment various strategies to find out an optimal strategy for high
quality bounding box annotation efficiently in iterative approach.

Figure 2: An example of the effect of the order of iterative annotation. The
figures show the cumulative number of ground truth boxes, boxes predicted by
the RCNN model, and the manual corrections required on the OpenImages/Person
dataset. Images are annotated in a random order (left) and in an order sorted
by the # of boxes per image (right). The reduction in workload is
significantly better in the sorted order (right).

###  IV-B Datasets

We selected three datasets for our experiments. The intention is to include
both large scale datasets (OpenImages) as well as small scale sets (Indoor).
The large datasets represent the upper bound in the size of an annotation
campaign, while the small scale is the common setup occurring in practice.

PASCAL VOC—PASCAL VOC dataset [6] is a popular benchmark dataset for object
detection. The dataset consists of 17k images having 40k object instances from
20 class categories, including person, bus, car, and motorbike. Two sets of
independent experiments were conducted in this dataset: first with all classes
and second with individual class categories. In the latter case, we used the
top ten object categories from VOC 2012 dataset, listed in Table III.

OpenImages—OpenImages [8] is yet another very large dataset for object
detection, classification and instance segmentation. The OpenImages V4
contains 9.2M images, 15.4M bounding boxes for 600 object classes. In our
experiment, we used a subset of the Open Image Dataset: 10.5k images are
selected from the person class; filtering the occluded, truncated, and groups
of objects with a single label (multiple objects inside a single bounding
box), as these annotations tend to be very noisy.

Indoor—Indoor dataset [17] is a moderate size dataset collected from
university indoor premises. The fully annotated object detection dataset
consists of about 2,200 images and about 5,000 object instances. Images were
extracted from a series of videos. Therefore, this dataset is also associated
with a temporal order of samples, which we will exploit later.

Table I summarizes the characteristics of these three datasets. Note that
although all datasets used in our experiments are fully labeled, we
investigate how their relabeling could benefit from training in the annotation
loop. The scope of this research is to experiment how bounding box annotation
cloud be done faster with minimal human involvement in an iterative-train
loop.

TABLE I: Comparison of Indoor [17], PASCAL VOC 2012 [6] and OpenImages [8] datasets. Source, size, annotation features and usages are presented in rows respectively. Indoor | PASCAL VOC | OpenImages
---|---|---
Indoor videos | Online (Flickr) | Online (Flickr)
| 2.2k images
---
4.5k instances
7 classes
| 17.1k images
---
40k instances
20 classes
| 9.2 M images
---
15.4M instances
600 classes
| Fully labelled by
---
one annotator;
annotations are
of high quality
| Fully labelled by
---
multiple annotators;
annotations are of
good quality
| Partial labelled
---
multiple annotators &
machine generated labels;
annotations contain noise
object detection |  | classification,
---
detection,
segmentation
| classification,
---
detection,
visual relationship
TABLE II: Reduction of manual workload (%) with different strategies on Indoor, PASCAL VOC 2012 and OpenImages datasets. Numbers in bold represent the best performing approach on each section.  Network - Approach | Indoor |  | PASCAL VOC
---
| OpenImages
---
Person
RCNN - Shuffled | 75.86 | 18.40 | 45.62
RCNN - Sorted | 56.97 | 20.93 | 60.05
RCNN - Original | 35.78 | 25.23 | 45.73
SSD - Shuffled | 47.38 | 3.46 | 20.28
SSD - Sorted | 31.58 | 5.66 | 35.13
SSD - Original | 19.24 | 7.97 | 20.04
TABLE III: Comparison of the manual workload reduction (%) on individual class categories from PASCAL VOC 2012 dataset. | Airplane | Bird | Boat | Bottle | Car | Cat | Chair | Dog | Person | Plant | Average
---|---|---|---|---|---|---|---|---|---|---|---
RCNN - Shuffled | 56.14 | 50.30 | 35.70 | 44.49 | 51.96 | 55.34 | 29.31 | 57.87 | 44.61 | 38.72 | 46.44
RCNN - Sorted | 62.07 | 60.43 | 35.65 | 46.68 | 56.27 | 59.53 | 32.44 | 63.28 | 61.24 | 32.75 | 51.03
RCNN - Original | 53.87 | 50.41 | 32.50 | 41.54 | 55.14 | 61.58 | 29.30 | 61.38 | 57.16 | 34.64 | 47.75

###  IV-C Order of annotation

For each iteration, we use a batch size of 50 images in all our experiments.
The input image size of 1024x600 pixels is used to train all RCNN models and
the input size of 300x300 pixels is used to train all SSD models. The
following three annotation orders are experimented on the above mentioned
datasets.

Shuffled—All images on the dataset are shuffled in random order and divided
into small batches of 50 images. All these small batches have randomly
selected images from the whole dataset. The human annotator manually annotates
the first batch, then fine-tune the detection model on that batch, and
remaining batches are used for annotation proposal in an iterative loop.

Sorted—In this approach images from the dataset are sorted in the decreasing
order of number of objects per image. Images having more objects (in both
single and multiclass cases) are presented first and so on. In this setup, the
first batch of 50 images contains comparatively more objects than the last
batch. Hence, it takes more time to annotate the first batch than in any other
setups.

Original—In our next approach, images are presented in the original order
defined either by the filename (PASCAL VOC and OpenImages) or temporal order
in a video (Indoor) or some other inherent way of ordering the examples. This
is likely to differ from the shuffled order only for temporal sequences such
as video, but we also experiment with this order with the non-temporal
datasets for the sake of completeness.

###  IV-D Results

An example of the progression of our method experimented on OpenImages person
class using the RCNN detection model is shown in Figure 2. The amount of
ground truth, model prediction, and manual correction in terms of numbers of
bounding boxes as a function of the number of images are presented with
shuffled and sorted approaches.

The left graph shows the experimental result based on the shuffled order of
images from the dataset, and the right graph shows the experimental result
based on the sorted order. The manual workload is less in the sorted order
approach; only 13,414 manual corrections would be needed instead of 33,573
ground truth bounding boxes. In the case of the random shuffle approach,
19,938 manual corrections would be required instead of 36,659 ground truth
bounding boxes.

The higher the gap between ground truth and manual correction, the better the
annotation performance in terms of manual workload reduction. The first stage
manually annotated bounding boxes from the first batch ($B_{0}$) of images are
not included in these graphs. For the sorted approach, the annotation workload
for the very first batch is usually more than other approaches.

The reductions of manual workload required to correct the proposed bounding
boxes in experimented approaches are shown in Table II. The prediction
performances of the two-stage RCNN model are comparatively better than those
of the single-stage SSD model. The RCNN model capacity and higher input
resolution for training images result in good proposals for bounding boxes and
class labels. However, the two-stage models are computationally expensive
compared to single-stage detection models like SSD. Moreover, the results
follow the same pattern for both methods in all of our experimented
approaches. The minimum amount of manual workload reduction noted is 3.46 %
with the SSD model on the VOC multiclass dataset with the shuffling approach.
On the other hand, the maximum amount of reduction recorded is 75.86% with the
RCNN model on the Indoor dataset with the shuffling approach.

Interestingly, it is seen that shuffling images helps to improve the overall
performance of the detection model only in the case where images are
continuous frames of video (Indoor). As shown in Table II, with the RCNN
model, 75.86% of manual work required to draw bounding boxes can be reduced by
randomly shuffling the images from the indoor dataset. However, in the
shuffling approach, there is a high probability of having every next image
from the sequence in different batches. The catastrophic forgetting effect
seems to be least in this approach hence, providing accurate proposals for
bounding boxes and class labels. Moreover, the results on OpenImages and VOC
datasets show that the shuffled approach is the worst performing among the
compared approaches.

For multi-class datasets, the annotations can be done one class at a time
(iterating over all images for each class) or all classes simultaneously.
Therefore, we experimented with the ten most populated classes of the VOC
dataset with the RCNN detection model, with a single category fully annotated
iteratively at a time. The results are shown in Table III. Interestingly, the
workload reduction is doubled when annotations are done one class at a time
(average reduction up to 51.03%) compared to the multi-class iterative
annotation (reduction 25.23%). In terms of individual categories, the
reduction ranges from 32.4% (chair) to 62.1% (airplane). The likely reason for
the improved performance is that the detection model does not have to learn
away from the other categories and can focus on learning a single class at a
time. Obviously, this approach requires that images are initially sorted by
category: Otherwise we would unnecessarily present, e.g., non-airplane images
while annotating the airplane class.

Additionally, it is found that the sorted approach is optimal for the manual
workload reduction in most of the single class categories. On the OpenImages
person class, as shown in Table II, the workload reduction with the sorted
approach is higher than other setups. The reduction in manual workload with
RCNN model is 60.05% and with SSD model is 35.13%. Most of the larger
reductions in Table III come from the sorted setup.

On the other hand, by splitting images into different batches based on the
filename or temporal order gives the best result for the multiclass dataset.
The original order approach gives best performance for VOC multiclass and
second best performance for VOC and OpenImages single class datasets.

TABLE IV: Comparison of the manual workload reduction (%) with Iterative annotation and Two-stage method on Indoor dataset [17]. All experiments are done with faster RCNN ResNet101 and 0.5 IoU threshold is used. Approach | Reduction (%)
---|---
Two-stage (5%) [17] | 79.47
Two-stage (6%) [17] | 81.21
Two-stage (8%) [17] | 78.68
Two-stage (10%) [17] | 79.03
Two-stage (20%) [17] | 72.46
Ours (iterative) | 79.56
Ours (cumulative) | 80.56

We performed some more experiments on the Indoor dataset to have a comparison
with the previous method [17]. In [17], a two-stage approach was used, with
first fold annotated fully manually, and the second part using the proposals
of a model trained with the first fold. The proportion of samples in the first
and second folds is a tuning parameter.

Table IV shows the results of the two-stage approach [17] for selected split
ratios; with 6% for the first fold and 94% for the second fold reducing the
workload the most (81.21%). Using the fully iterative approach of this paper
results in a comparable accuracy (79.56%), but does not require the selection
of the split ratio.

However, the sweet spot of 6% is the only split ratio exceeding the workload
reduction of the proposed iterative approach. In fact, it is impossible to
know the optimal split ratio a priori for an unlabeled dataset; for example,
the 5% – 95% split is already almost 2% worse. Thus, our iterative method is
economical compared to the earlier two-stage approach.

In addition to the iterative approach, we experimented on a modified version
of the proposed method. Namely, instead of training on the most recent batch,
one can train with all previously annotated batches at each iteration. This
cumulative approach was tested on the Indoor dataset and the results are shown
on the last line of Table IV. It turns out that the cumulative approach is
better compared to the iterative approach; however, its training becomes
significantly slower due to larger amount of training data.

In general, the two-stage approach with other amounts of manually labeled
images has less workload reduction than our iterative approach trained with
the same approach and same model. The significant benefit iterative approach
over this is that the model is improving over time; object proposals are
getting better, hence require less correction work. Also, labeling a small
batch of images is more relaxed and less error-prone compared to mass
annotation.

##  V Conclusion

This paper presented an iterative human-in-the-loop annotation method to
minimize human involvement in image annotation campaigns for the task of
object detection. The proposed method utilizes human-machine collaboration
resulting in high-quality bounding box annotations on small and medium-sized
datasets. Extensive experiments on the proposed method on three datasets show
that our iterative annotation is able to reduce the manual workload by up to
75%. However, the reduction of manual annotation workload appears to be
dependent on the dataset size, image source, and object class categories. We
also noted an adequate performance of proposed approaches on the already
existing platform for the bounding box annotation campaign.

Our implementation uses a commonly used threshold value 0.5 IoU threshold
threshold for detection performance measurement and accepting the label
proposals. In our future work, we will consider the effect of requiring a
higher IoU for the annotation results ($>0.5$ IoU). In fact, we already
experimented with a 0.8 IoU threshold, and discovered that the manual workload
reduction is even higher since less manual correction work is needed on the
good quality proposals. It would also be interesting to experiment on the
effect of an IoU threshold on the network proposals and its tradeoff between
correction workload. The resource constraints and latency of the detection
model could be studied in the future with parameters such as batch size,
training step, and input size of images for the model training.

Furthermore, it would be nice to experiment on an active learning pipeline
that could reduce human workload even more by automatically selecting
informative images for labeling on earlier iterations.

## References

  * [1] E. Hjelmås and B. K. Low, “Face detection: A survey,” _Computer Vision and Image Understanding_ , vol. 83, 2001.
  * [2] A. Angelova, A. Krizhevsky, V. Vanhoucke, A. Ogale, and D. Ferguson, “Real-time pedestrian detection with deep network cascades,” in _BMVC_ , 2015.
  * [3] A. Raghunandan, Mohana, P. Raghav, and H. V. R. Aradhya, “Object detection algorithms for video surveillance applications,” _ICCSP_ , 2018.
  * [4] A. Geiger, P. Lenz, C. Stiller, and R. Urtasun, “Vision meets robotics: The kitti dataset,” _International Journal of Robotics Research (IJRR)_ , 2013\.
  * [5] S. Chadwick, W. Maddern, and P. Newman, “Distant vehicle detection using radar and vision,” _arXiv preprint arXiv:1901.10951_ , 2019.
  * [6] M. Everingham, S. M. A. Eslami, L. Van Gool, C. K. I. Williams, J. Winn, and A. Zisserman, “The pascal visual object classes challenge: A retrospective,” _International Journal of Computer Vision_ , 2015.
  * [7] T. Lin, M. Maire, S. J. Belongie, L. D. Bourdev, R. B. Girshick, J. Hays, P. Perona, D. Ramanan, P. Dollár, and C. L. Zitnick, “Microsoft COCO: common objects in context,” _Computing Research Repository_ , vol. abs/1405.0312, 2014.
  * [8] A. Kuznetsova, H. Rom, N. Alldrin, J. Uijlings, I. Krasin, J. Pont-Tuset, S. Kamali, S. Popov, M. Malloci, T. Duerig _et al._ , “The open images dataset v4: Unified image classification, object detection, and visual relationship detection at scale,” _arXiv preprint arXiv:1811.00982_ , 2018\.
  * [9] H. Su, J. Deng, and L. Fei-fei, “Crowdsourcing Annotations for Visual Object Detection,” in _AAAI Human Computation Workshop_ , 2012, pp. 40–46.
  * [10] “Hasty,” https://hasty.ai/, 2020.
  * [11] S. Berg, D. Kutra, T. Kroeger, C. N. Straehle, B. X. Kausler, C. Haubold, M. Schiegg, J. Ales, T. Beier, M. Rudy, K. Eren, J. I. Cervantes, B. Xu, F. Beuttenmueller, A. Wolny, C. Zhang, U. Koethe, F. A. Hamprecht, and A. Kreshuk, “ilastik: interactive machine learning for (bio)image analysis,” _Nature Methods_ , Sep. 2019.
  * [12] J. Kirkpatrick, R. Pascanu, N. C. Rabinowitz, J. Veness, G. Desjardins, A. A. Rusu, K. Milan, J. Quan, T. Ramalho, A. Grabska-Barwinska, D. Hassabis, C. Clopath, D. Kumaran, and R. Hadsell, “Overcoming catastrophic forgetting in neural networks,” _arXiv preprint arXiv:1612.00796_ , 2016.
  * [13] D. P. Papadopoulos, J. R. R. Uijlings, F. Keller, and V. Ferrari, “We don’t need no bounding-boxes: Training object class detectors using only human verification,” in _CVPR_ , 2016, pp. 854–863.
  * [14] ——, “Training object class detectors with click supervision,” in _CVPR_ , 2017, pp. 180–189.
  * [15] ——, “Extreme clicking for efficient object annotation,” in _ICCV_ , 2017, pp. 4940–4949.
  * [16] K. Konyushkova, J. R. R. Uijlings, C. H. Lampert, and V. Ferrari, “Learning intelligent dialogs for bounding box annotation,” in _CVPR_ , 2018, pp. 9175–9184.
  * [17] B. Adhikari, J. Peltomaki, J. Puura, and H. Huttunen, “Faster bounding box annotation for object detection in indoor scenes,” in _7th European Workshop on Visual Information Processing (EUVIP)_ , 2018.
  * [18] S. J. Pan and Q. Yang, “A survey on transfer learning,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 22, no. 10, Oct 2010.
  * [19] S. Ren, K. He, R. Girshick, and J. Sun, “Faster R-CNN: towards real-time object detection with region proposal networks,” in _Advances in neural information processing systems_ , 2015, pp. 91–99.
  * [20] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 770–778.
  * [21] W. Liu, D. Anguelov, D. Erhan, C. Szegedy, S. Reed, C.-Y. Fu, and A. C. Berg, “SSD: single shot multibox detector,” in _European conference on computer vision_ , 2016, pp. 21–37.
  * [22] M. Sandler, A. Howard, M. Zhu, A. Zhmoginov, and L.-C. Chen, “Mobilenetv2: Inverted residuals and linear bottlenecks,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2018, pp. 4510–4520.