The Laplacian Permanents and Laplacian Ratios of Trees

Xiangshuai Dong

School of Mathematics and Statistics, Qinghai Nationalities University, Xining, China.

DOI: 10.4236/am.2025.164017                

Abstract

Brualdi and Goldwasser characterized the Laplacian permanents of trees. In this paper, we study the Laplacian permanents of trees. We characterize some Laplacian permanents of trees. The Laplacian ratio of $G$ is the Laplacian permanent of $G$ divided by the product of degrees of all vertices. In this paper, we obtain that for any $n$ -vertex caterpillar tree $T$ , there exists an $n$ -vertex caterpillar tree $C_n$ such that $\pi \left(C_n\right)\le \pi \left(T\right)$ .

Keywords

Laplacian Permanents, Laplacian Ratio, Tree, Caterpillar

1. Introduction

Let $M=\left[a_{ij}\right]\left(i,j\in 1,2,3,\cdots ,n\right)$ be an $n\times n$ matrix. The permanent of $M$ is defined as

$\text{per}M={\displaystyle \sum }_{\sigma \in {\text{Λ}}_n}{\displaystyle \prod }_{i=1}^n{a}_{i\varphi \left(i\right)},$

where ${\text{Λ}}_n$ is the symmetric group of degree $n$ . Valiant [1] proved that even for (0,1)-matrices, computing the permanent is $\#P$ -complete.

Let $G=\left(V\left(G\right),E\left(G\right)\right)$ be a simple connected graph with $n$ vertices, and let $d_{v_i}$ denote the degree of vertex $v_i\left(i=1,2,\cdots ,n\right)$ in $V\left(G\right)$ . The adjacency matrix and degree matrix of graph $G$ are denoted by $A\left(G\right)$ and $D\left(G\right)$ , respectively. The Laplacian matrix of graph $G$ is defined as $L\left(G\right)=D\left(G\right)-A\left(G\right)$ . Based on the Laplacian matrix of graphs, researchers began to study the Laplacian permanents of graphs. For more research on the permanent, refer to [2]-[7]. Brualdi and Goldwasser [8] obtained some results on the Laplacian permanents of bipartite graphs: the minimum and maximum values of the Laplacian permanents of bipartite graphs with $n$ vertices. They also gave bounds for $\text{per}L\left(G\right)$ .

Theorem 1. ([8]) Let $T$ be an $n$ -vertex tree. Then

$2\left(n-1\right)\le \text{per}T\le \frac{2-\sqrt{2}}{2}{\left(1+\sqrt{2}\right)}^n+\frac{2+\sqrt{2}}{2}{\left(1-\sqrt{2}\right)}^n.$

The lower bound is achieved if and only if $T$ is a star, and the upper bound is achieved if and only if $T$ is a path.

When $G$ is a tree, the minimum value of the Laplacian permanent can be obtained directly from the degrees of the vertices and the size of the matching. For the maximum value of the Laplacian permanent, it is related to the degrees of the vertices and the size of the matching. The following problems are proposed:

Problem 1. ([8]) For an $n$ -vertex tree with maximum degree $k$ , what is the maximum value of the Laplacian permanent?

Problem 2. ([8]) For an $n$ -vertex tree with matching number $k$ , what is the maximum value of the Laplacian permanent?

Problem 3. ([8]) For an $n$ -vertex tree that is a $\left(p,q\right)$ -bipartition, what is the maximum value of the Laplacian permanent?

Brualdi and Goldwasser [8] defined the Laplacian permanent $\pi \left(G\right)$ of a graph.

$\pi \left(G\right)=\frac{\text{per}L\left(G\right)}{d_{v_1}{d}_{v_2}\cdots d_{v_n}}.$

Brualdi and Goldwasser [8] first studied the Laplacian ratios of graphs and systematically studied the properties of the Laplacian ratios of graphs. They characterized the lower bounds of the Laplacian ratios of some graphs. Goldwasser [9] studied the maximum and minimum values of the Laplacian ratios of graphs with matching number $k$ . The Laplacian ratio of graph plays an important role in statistics, chemistry, and communication. The Laplacian ratio can also be used to count the number of spanning trees of a graph. Brualdi and Goldwasser [8] first studied the Laplacian ratios of graphs and obtained some results on the Laplacian ratios of trees. They further proposed the following problems in 1983:

Problem 4. ([8]) What is the minimum value of the Laplacian ratios of $n$ -vertex trees with maximum degree $k$ ?

Problem 5. ([8]) What is the minimum value of the Laplacian ratios of $n$ -vertex trees with $k$ -matching?

Problem 6. ([8]) What is the maximum value of the Laplacian ratios of $n$ -vertex trees?

In the past few decades, Goldwasser [9] solved Problem 5. Currently, the study of the Laplacian ratios of graphs has attracted widespread attention. The Laplacian ratio theory is well elaborated in [10]-[16].

We further study the Laplacian ratios of trees. Through graph transformations, we determine the graph that minimizes the Laplacian ratios among all caterpillar trees.

In this paper, in Section 2, we provide some preliminary knowledge. In Section 3, we study some Laplacian permanents of trees. We also characterize a graph transformation related to the Laplacian ratio. We obtain that for any $n$ -vertex caterpillar tree $T$ , there exists an $n$ -vertex caterpillar tree $C_n$ such that $\pi \left(C_n\right)\le \pi \left(T\right)$ . In Section 4, we provide a conclusion related to the Laplacian permanent and the Laplacian ratio.

2. Preliminaries

To facilitate the proofs in the following sections, we introduce some basic concepts in this section.

Let $G$ be a graph. If $G$ has a $u,v$ -path, then the distance between $u$ and $v$ (denoted by $d_G\left(u,v\right)$ , or simply $d\left(u,v\right)$ ) is the length of the shortest $u,v$ -path. The diameter is defined as ${\max }_{u,v\in V\left(G\right)}d\left(u,v\right)$ . $P_k$ is a path with diameter $k-1$ . A caterpillar is a tree that consists of a central path with leaves attached to it. A broom graph $B\left(n,k\right)$ is obtained by attaching $n-k$ pendant vertices to one end of a path $P_k$ with $k$ vertices. $S_n$ is the star graph with $n$ vertices. $L_S\left(G\right)$ denotes the Laplacian matrix of graph $G$ after removing the rows and columns corresponding to the vertices in $S\left(S\subseteq V\left(G\right)\right)$ . In particular, if $S=\left\{v\right\}$ and $v\in V\left(G\right)$ , then $L_{\left\{v\right\}}\left(G\right)$ can be abbreviated as $L_v\left(G\right)$ . Let $A$ be an $n\times n$ matrix. $A\left(i,j\right)$ denotes the $\left(n-2\right)\times \left(n-2\right)$ submatrix obtained by deleting the $i$ -th and $j$ -th rows and columns of $A$ . $A_{ij}$ denotes the $\left(n-1\right)\times \left(n-1\right)$ submatrix obtained by deleting the $i$ -th row and column of $A$ . Let $Q_n$ be the $n\times n$ submatrix obtained by deleting the first row and column of $L\left(P_n\right)$ .

Lemma 2. Let $A$ be an $n\times n$ matrix and $i,j\in \left\{1,2,\cdots ,n\right\}$ . Then

$\text{per}A={\displaystyle \sum }_i{a}_{ij}\text{per}{A}_{ij}\text{and}\text{per}A={\displaystyle \sum }_j{a}_{ij}\text{per}{A}_{ij}.$

Lemma 3. ([8]) Let $T$ be a tree. Then

$\pi \left(T\right)={\displaystyle \sum }_{k=0}^{\lfloor \frac{n}{2}\rfloor }{\pi }_k\left(T\right)$

Lemma 4. ([8]) Let $k\ge 2$ and $r\ge 1$ be integers. Then

$\text{per}L\left(B\left(n,k\right)\right)=\left(2n-2k+1\right)\text{per}{Q}_{k-1}+\text{per}{Q}_{k-2},$

$\text{per}{Q}_k=\frac{1}{2}{\left(1+\sqrt{2}\right)}^k+\frac{1}{2}{\left(1-\sqrt{2}\right)}^k,$

and

$\text{per}{P}_k=\frac{2-\sqrt{2}}{2}{\left(1+\sqrt{2}\right)}^k+\frac{2+\sqrt{2}}{2}{\left(1-\sqrt{2}\right)}^k.$

Lemma 5. ([16]) Let $P_{k+1}=u_1{u}_2\cdots u_i\cdots u_{k+1}$ be a path. Let $T_{n,k,i}$ be the tree obtained by attaching $n-k-1$ pendant vertices to vertex $u_i$ of path $P_{k+1}$ . Then

$\text{per}L\left(T_{n,k,i}\right)=\text{per}L\left(P_{k+1}\right)+2\left(n-k-1\right)\text{per}{Q}_{i-1}\text{per}{Q}_{k-i+1}.$

Lemma 6. ([11]) A tree is a caterpillar if and only if it contains no $Y$ -structure (see Figure 1).

Figure 1. $Y$ -structure.

3. Main Results

Lemma 7. Let $R_n^2$ and $R_n^{i-1}$ be the graphs shown in Figure 2. Then

(i) $\text{per}L\left(R_n^2\right)=\frac{216-127\sqrt{2}}{2}{\left(1+\sqrt{2}\right)}^{n-5}+\frac{216+127\sqrt{2}}{2}{\left(1-\sqrt{2}\right)}^{n-5}$ ,

(ii) $\text{per}L\left(R_n^{i-1}\right)=\frac{4-\sqrt{2}}{2}{\left(1+\sqrt{2}\right)}^{n-2}+\frac{4-\sqrt{2}}{2}{\left(1-\sqrt{2}\right)}^{n-2}+{\left(1+\sqrt{2}\right)}^{n-4i+1}+$ ${\left(1-\sqrt{2}\right)}^{n-4i+1}$ .

Figure 2. $R_n^2$ and $R_n^{i-1}$ .

Proof. By expanding the first row and column of $\text{per}{R}_n^2$ , we obtain the permanent of the Laplacian matrix of $R_n^2$ .

$L\left(R_n^2\right)=\left[\begin{array}{l}\begin{array}{cccccccccccc}3& -1& 0& -1& 0& 0& 0& -1& 0& \cdots & 0& 0\\ -1& 2& -1& & & & & & & & & \\ 0& -1& 1& & & & & & & & & \\ -1& & & 2& -1& & & & & & & \\ 0& & & -1& 2& -1& & & & & & \\ 0& & & & -1& 2& -1& & & & & \\ 0& & & & & -1& 1& & & & & \\ -1& & & & & & & 2& -1& & & \\ 0& & & & & & & -1& 2& & & \\ ⋮& & & & & & & & & \ddots & & \\ 0& & & & & & & & & & 2& -1\\ 0& & & & & & & & & & -1& 1\end{array}\hfill \end{array}\right].$

By Lemma 2, the permanent of $L\left(R_n^2\right)$ can be expanded as

$\text{per}L\left(R_n^2\right)=3\times 3\times \text{per}{Q}_4\text{per}{Q}_{n-7}+\text{per}{Q}_4\text{per}{Q}_{n-7}+3\times \text{per}{Q}_3\text{per}{Q}_{n-7}+3\times \text{per}{Q}_4\text{per}{Q}_{n-8}$ .

By Lemma 4,

$\begin{array}{c}\text{per}L\left(R_n^1\right)=3\times 3\times \left(\frac{1}{2}{\left(1+\sqrt{2}\right)}^4+\frac{1}{2}{\left(1-\sqrt{2}\right)}^4\right)\left(\frac{1}{2}{\left(1+\sqrt{2}\right)}^{n-7}+\frac{1}{2}{\left(1-\sqrt{2}\right)}^{n-7}\right)\\ +\left(\frac{1}{2}{\left(1+\sqrt{2}\right)}^4+\frac{1}{2}{\left(1-\sqrt{2}\right)}^4\right)\left(\frac{1}{2}{\left(1+\sqrt{2}\right)}^{n-7}+\frac{1}{2}{\left(1-\sqrt{2}\right)}^{n-7}\right)\\ +3\times \left(\frac{1}{2}{\left(1+\sqrt{2}\right)}^4+\frac{1}{2}{\left(1-\sqrt{2}\right)}^4\right)\left(\frac{1}{2}{\left(1+\sqrt{2}\right)}^{n-7}+\frac{1}{2}{\left(1-\sqrt{2}\right)}^{n-7}\right)\\ +3\times \left(\frac{1}{2}{\left(1+\sqrt{2}\right)}^4+\frac{1}{2}{\left(1-\sqrt{2}\right)}^4\right)\left(\frac{1}{2}{\left(1+\sqrt{2}\right)}^{n-8}+\frac{1}{2}{\left(1-\sqrt{2}\right)}^{n-8}\right)\\ =\frac{216-127\sqrt{2}}{2}{\left(1+\sqrt{2}\right)}^{n-5}+\frac{216+127\sqrt{2}}{2}{\left(1-\sqrt{2}\right)}^{n-5}\end{array}$ .

By expanding the first row and column of $\text{per}{R}_n^{i-1}$ , we obtain the permanent of the Laplacian matrix of $R_n^{i-1}$ .

$L\left(R_n^2\right)=\left[\begin{array}{l}\begin{array}{ccccccccccc}3& -1& 0& -1& 0& \cdots & 0& 0& \cdots & 0& 0\\ -1& 2& -1& & & & & & & & \\ 0& -1& 1& & & & & & & & \\ -1& & & 2& -1& & & & & & \\ 0& & & -1& 2& & & & & & \\ ⋮& & & & & \ddots & & & & & \\ 0& & & & & & 2& -1& & & \\ 0& & & & & & -1& 1& & & \\ ⋮& & & & & & & & \ddots & & \\ 0& & & & & & & & & 2& -1\\ 0& & & & & & & & & -1& 1\end{array}\hfill \end{array}\right].$

By Lemma 2, the permanent of $L\left(R_n^{i-1}\right)$ can be expanded as

$\text{per}L\left(R_n^2\right)=3\times 3\times \text{per}{Q}_{2i-2}\text{per}{Q}_{n-2i-1}+\text{per}{Q}_{2i-2}\text{per}{Q}_{n-2i-1}+3\times \text{per}{Q}_{2i-3}\text{per}{Q}_{n-2i-1}+3\times \text{per}{Q}_{2i-2}\text{per}{Q}_{n-2i-2}$ .

By Lemma 4,

$\begin{array}{c}\text{per}L\left(R_n^1\right)=3\times 3\times \left(\frac{1}{2}{\left(1+\sqrt{2}\right)}^{2i-2}+\frac{1}{2}{\left(1-\sqrt{2}\right)}^{2i-2}\right)\left(\frac{1}{2}{\left(1+\sqrt{2}\right)}^{n-2i-1}+\frac{1}{2}{\left(1-\sqrt{2}\right)}^{n-2i-1}\right)\\ +\left(\frac{1}{2}{\left(1+\sqrt{2}\right)}^{2i-2}+\frac{1}{2}{\left(1-\sqrt{2}\right)}^{2i-2}\right)\left(\frac{1}{2}{\left(1+\sqrt{2}\right)}^{n-2i-1}+\frac{1}{2}{\left(1-\sqrt{2}\right)}^{n-2i-1}\right)\\ +3\times \left(\frac{1}{2}{\left(1+\sqrt{2}\right)}^{2i-3}+\frac{1}{2}{\left(1-\sqrt{2}\right)}^{2i-3}\right)\left(\frac{1}{2}{\left(1+\sqrt{2}\right)}^{n-2i-1}+\frac{1}{2}{\left(1-\sqrt{2}\right)}^{n-2i-1}\right)\\ +3\times \left(\frac{1}{2}{\left(1+\sqrt{2}\right)}^{2i-2}+\frac{1}{2}{\left(1-\sqrt{2}\right)}^{2i-2}\right)\left(\frac{1}{2}{\left(1+\sqrt{2}\right)}^{n-2i-2}+\frac{1}{2}{\left(1-\sqrt{2}\right)}^{n-2i-2}\right)\\ =\frac{4-\sqrt{2}}{2}{\left(1+\sqrt{2}\right)}^{n-2}+\frac{4-\sqrt{2}}{2}{\left(1-\sqrt{2}\right)}^{n-2}+{\left(1+\sqrt{2}\right)}^{n-4i+1}+{\left(1-\sqrt{2}\right)}^{n-4i+1}\end{array}$ .

□

Lemma 8. Let $T_{n,k,6}$ and $T_{n,k,2i}$ be two trees. Then

(i)

$\text{per}L\left(T_{n,k,6}\right)=\left(41n-41k-12+\frac{41\sqrt{2}}{2}\right){\left(1+\sqrt{2}\right)}^{k-5}+\left(41n-41k-12-\frac{41\sqrt{2}}{2}\right){\left(1-\sqrt{2}\right)}^{k-5}$ ,

(ii) $\begin{array}{c}\text{per}L\left(T_{n,k,2i}\right)=\left(\frac{\left(n-k-1\right){\left(2\sqrt{2}-3\right)}^{2i-1}+n-k+\sqrt{2}-1}{2}\right){\left(1+\sqrt{2}\right)}^k\\ +\left(-\frac{\left(n-k-1\right){\left(2\sqrt{2}+3\right)}^{2i-1}+n-k-\sqrt{2}-1}{2}\right){\left(1-\sqrt{2}\right)}^k\end{array}$ .

Proof. By Lemma 5,

$\text{per}L\left(T_{n,k,6}\right)=\text{per}L\left(P_{k+1}\right)+2\left(n-k-1\right)\text{per}{Q}_5\text{per}{Q}_{k-5}$ ,

$\text{per}L\left(T_{n,k,2i}\right)=\text{per}L\left(P_{k+1}\right)+2\left(n-k-1\right)\text{per}{Q}_{2i-1}\text{per}{Q}_{k-2i+1}$ .

By Lemma 4,

$\begin{array}{c}\text{per}L\left(T_{n,k,6}\right)=\text{per}L\left(P_{k+1}\right)+2\left(n-k-1\right)\text{per}{Q}_5\text{per}{Q}_{k-5}\\ =\frac{2-\sqrt{2}}{2}{\left(1+\sqrt{2}\right)}^{k+1}+\frac{2+\sqrt{2}}{2}{\left(1-\sqrt{2}\right)}^{k+1}\\ +2\left(n-k-1\right)\text{per}{Q}_5\times \left(\frac{1}{2}{\left(1+\sqrt{2}\right)}^{k-5}+\frac{1}{2}{\left(1-\sqrt{2}\right)}^{k-5}\right)\\ =\left(41n-41k-12+\frac{41\sqrt{2}}{2}\right){\left(1+\sqrt{2}\right)}^{k-5}\\ +\left(41n-41k-12-\frac{41\sqrt{2}}{2}\right){\left(1-\sqrt{2}\right)}^{k-5},\end{array}$

$\begin{array}{c}\text{per}L\left(T_{n,k,2i}\right)=\text{per}L\left(P_{k+1}\right)+2\left(n-k-1\right)\text{per}{Q}_{2i}\text{per}{Q}_{k-2i+1}\\ =\frac{2-\sqrt{2}}{2}{\left(1+\sqrt{2}\right)}^{k+1}+\frac{2+\sqrt{2}}{2}{\left(1-\sqrt{2}\right)}^{k+1}\\ +2\left(n-k-1\right)\times \left(\frac{1}{2}{\left(1+\sqrt{2}\right)}^{2i-1}+\frac{1}{2}{\left(1-\sqrt{2}\right)}^{2i-1}\right)\\ \times \left(\frac{1}{2}{\left(1+\sqrt{2}\right)}^{n-2i+1}+\frac{1}{2}{\left(1-\sqrt{2}\right)}^{n-2i+1}\right)\\ =\left(\frac{\left(n-k-1\right){\left(2\sqrt{2}-3\right)}^{2i-1}+n-k+\sqrt{2}-1}{2}\right){\left(1+\sqrt{2}\right)}^k\\ +\left(-\frac{\left(n-k-1\right){\left(2\sqrt{2}+3\right)}^{2i-1}+n-k-\sqrt{2}-1}{2}\right){\left(1-\sqrt{2}\right)}^k.\end{array}$

□

Definition 1. Let $T$ be a tree containing a $Y$ -structure, where $u$ is the central vertex of the $Y$ -structure, and $v_1,v_2,\cdots ,v_t,w_1,w_2,\cdots ,w_s\in N\left(v\right)$ , where $w_1,w_2,\cdots ,w_s$ are pendant vertices in $T$ , and $v_1,v_2,\cdots ,v_t$ are non-pendant vertices in $T$ . $T\left[v_i\to u;4\right]$ is obtained by contracting the edges $u{v}_i\left(1\le i\le t\right)$ and then attaching all vertices $v_1,v_2,\cdots ,v_t$ to $u$ . We call $T\left[v_i\to u;4\right]$ the graph obtained from $T$ by Graph Transformation 1.

Theorem 9. Let $T$ and $T\left[v_i\to u;1\right]$ be the graphs shown in Figure 3. Then $\pi \left(T\right)>\pi \left(T\left[v_i\to u;1\right]\right)$ .

Figure 3. Graph Transformation 1.

Proof. Let ${\mathcal{T}}_k\left(T\right)$ be the set of all $k$ -matchings of $T$ , and let ${\mathcal{T}}_k\left(T\left[v_i\to u;4\right]\right)$ be the set of all $k$ -matchings of $T\left[v_i\to u;4\right]$ . We can partition the $k$ -matchings of $T\left[v_i\to u;4\right]$ into two types: those that do not contain vertex $u$ , denoted by ${\mathcal{T}}_{k,u}^{-}\left(T\left[v_i\to u;4\right]\right)$ , and those that contain vertex $u$ , denoted by ${\mathcal{T}}_{k,u}^{+}\left(T\left[v_i\to u;4\right]\right)$ . Clearly, ${\mathcal{T}}_k\left(T\left[v_i\to u;4\right]\right)={\mathcal{T}}_{k,u}^{+}\left(T\left[v_i\to u;4\right]\right)\cup {\mathcal{T}}_{k,u}^{-}\left(T\left[v_i\to u;4\right]\right)$ . Let the edges incident to $u$ in $T\left[v_i\to u;4\right]$ be labeled as $h_1,h_2,\cdots ,h_p,e_1,e_2,\cdots ,e_{s+t}$ , where $h_1,h_2,\cdots ,h_p$ are non-pendant edges, and $e_1,e_2,\cdots ,e_{s+t}$ are pendant edges. Let ${h^{\prime }}_1,{h^{\prime }}_2,\cdots ,{h^{\prime }}_p,{e^{\prime }}_1,{e^{\prime }}_2,\cdots ,{e^{\prime }}_{s+t}$ be the corresponding edges in $T$ (without applying Graph Transformation 4). Let ${\mathcal{T}}_k\left(T\right)$ be the set of all $k$ -matchings of $T$ that contain ${h^{\prime }}_1,{h^{\prime }}_2,\cdots ,{h^{\prime }}_p,{e^{\prime }}_1,{e^{\prime }}_2,\cdots ,{e^{\prime }}_{s+t}$ , denoted by ${\mathcal{T}}_k^{+}\left(T\right)$ , and those that do not contain ${h^{\prime }}_1,{h^{\prime }}_2,\cdots ,{h^{\prime }}_p,{e^{\prime }}_1,{e^{\prime }}_2,\cdots ,{e^{\prime }}_{s+t}$ , denoted by ${\mathcal{T}}_k^{-}\left(T\right)$ . Clearly, ${\mathcal{T}}_k\left(T\right)={\mathcal{T}}_k^{+}\left(T\right)\cup {\mathcal{T}}_k^{-}\left(T\right)$ . Due to the structure of $T$ and $T\left[v_i\to u;4\right]$ , for any $\mu \in {\mathcal{T}}_{k,u}^{-}\left(T\left[v_i\to u;4\right]\right)$ , there exists a ${\mu }^{\prime }\in {\mathcal{T}}_k^{-}\left(T\right)$ such that $d\left({\mu }^{\prime }\right)=d\left(\mu \right)$ . We further partition ${\mathcal{T}}_{k,u}^{+}\left(T\left[v_i\to u;4\right]\right)$ into two subsets: ${\mathcal{T}}_{k,u}^{++}\left(T\left[v_i\to u;4\right]\right)$ (those $k$ -matchings that contain one of $h_1,h_2,\cdots ,h_p$ ) and ${\mathcal{T}}_{k,u}^{+-}\left(T\left[v_i\to u;4\right]\right)$ (those $k$ -matchings that contain one of $e_1,e_2,\cdots ,e_{s+t}$ ). Clearly, ${\mathcal{T}}_{k,u}^{+}\left(T\left[v_i\to u;4\right]\right)={\mathcal{T}}_{k,u}^{++}\left(T\left[v_i\to u;4\right]\right)\cup {\mathcal{T}}_{k,u}^{+-}\left(T\left[v_i\to u;4\right]\right)$ . Similarly, we partition ${\mathcal{T}}_k^{+}\left(T\right)$ into two subsets: ${\mathcal{T}}_k^{++}\left(T\right)$ (those $k$ -matchings that contain one of ${h^{\prime }}_1,{h^{\prime }}_2,\cdots ,{h^{\prime }}_p$ ) and ${\mathcal{T}}_k^{+-}\left(T\right)$ (those $k$ -matchings that contain one of ${e^{\prime }}_1,{e^{\prime }}_2,\cdots ,{e^{\prime }}_{s+t}$ ). Clearly, ${\mathcal{T}}_k^{+}\left(T\right)={\mathcal{T}}_k^{++}\left(T\right)\cup {\mathcal{T}}_k^{+-}\left(T\right)$ . Due to the structure of $T$ and $T\left[v_i\to u;4\right]$ , we have $d\left({h^{\prime }}_i\right)>d\left(h_i\right)\left(1\le i\le p\right)$ . Therefore, for any $\mu \in {\mathcal{T}}_{k,u}^{++}\left(T\left[v_i\to u;4\right]\right)$ , there exists a ${\mu }^{\prime }\in {\mathcal{T}}_k^{++}\left(T\right)$ , such that $d\left({\mu }^{\prime }\right)>d\left(\mu \right)$ . Now consider ${\mathcal{T}}_{k,u}^{+-}\left(T\left[v_i\to u;4\right]\right)$ and ${\mathcal{T}}_k^{+-}\left(T\right)$ . For $T\left[v_i\to u;4\right]$ ,

$\frac{1}{d\left(e_1\right)}+\frac{1}{d\left(e_2\right)}+\cdots +\frac{1}{d\left(e_{s+t}\right)}=\frac{s+t}{d_{v_1}+d_{v_2}+\cdots +d_{v_t}+s}.$

For $T$ ,

$\frac{1}{d\left({e^{\prime }}_1\right)}+\frac{1}{d\left({e^{\prime }}_2\right)}+\cdots +\frac{1}{d\left({e^{\prime }}_{s+t}\right)}=\frac{1}{s+t}\left(\frac{1}{d_{v_1}}+\frac{1}{d_{v_2}}+\cdots +\frac{1}{d_{v_t}}+s\right).$

Since $\frac{d_{v_1}+d_{v_2}+\cdots +d_{v_t}+1\times s}{s+t}\ge \sqrt[s+t]{d_{v_1}{d}_{v_2}\cdots d_{v_t}\times 1^s}\ge \frac{s+t}{\frac{1}{d_{v_1}}+\frac{1}{d_{v_2}}+\cdots +\frac{1}{d_{v_t}}+\frac{1}{1}\times s}$ , we have $\frac{1}{s+t}\left(\frac{1}{d_{v_1}}+\frac{1}{d_{v_2}}+\cdots +\frac{1}{d_{v_t}}+s\right)\ge \frac{s+t}{d_{v_1}+d_{v_2}+\cdots +d_{v_t}+s}$ . Therefore, ${\displaystyle \sum }_{\mu \in {\mathcal{T}}_k^{+-}\left(T\right)}\frac{1}{d\left(\mu \right)}\ge {\displaystyle \sum }_{\mu \in {\mathcal{T}}_{k,u}^{+-}\left(T\left[v_i\to u;4\right]\right)}\frac{1}{d\left(\mu \right)}$ . Thus, we have ${\pi }_k\left(T\right)>{\pi }_k\left(T\left[v_i\to u;4\right]\right)$ , and hence $\pi \left(T\right)>\pi \left(T\left[v_i\to u;4\right]\right)$ . □

Theorem 10. For any $n$ -vertex caterpillar tree $T$ , there exists an $n$ -vertex caterpillar tree $C_n$ such that $\pi \left(C_n\right)\le \pi \left(T\right)$ .

Proof. Since $T$ is a caterpillar tree, by Lemma 6, $T$ must contain a $Y$ -structure. By applying Graph Transformation 1, we can reduce the number of $Y$ -structures in $T$ . If $T$ still contains a $Y$ -structure, we can apply Graph Transformation 1 again to transform $T$ into a graph $C_n$ without any $Y$ -structure. By Lemma 6, $C_n$ is a caterpillar tree, and $\pi \left(C_n\right)\le \pi \left(T\right)$ . □

4. Conclusion

In this paper, we studied the Laplacian permanents and the Laplacian ratios of trees. We characterized some Laplacian permanents of trees. We also obtained a graph transformation related to the Laplacian ratio. In future research, we will further study the Laplacian permanents and the Laplacian ratios of graphs.

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Valiant, L.G. (1979) The Complexity of Computing the Permanent. Theoretical Computer Science, 8, 189-201. https://doi.org/10.1016/0304-3975(79)90044-6
[2]	Cvetkovic, D. (2005) Signless Laplacians and Line Graphs. Bulletin: Classe des sciences mathematiques et natturalles, 131, 85-92. https://doi.org/10.2298/bmat0530085c
[3]	Cvetković, D., Rowlinson, P. and Simić, S.K. (2007) Signless Laplacians of Finite Graphs. Linear Algebra and its Applications, 423, 155-171. https://doi.org/10.1016/j.laa.2007.01.009
[4]	Cvetković, D., Doob, M. and Sachs, H. (1980) Spectra of Graphs. Johann Ambrosius Barth Verlag.
[5]	Haemers, W.H. and Spence, E. (2004) Enumeration of Cospectral Graphs. European Journal of Combinatorics, 25, 199-211. https://doi.org/10.1016/s0195-6698(03)00100-8
[6]	Cash, G.G. and Gutman, I. (1990) The Laplacian Permanental Polynomial: Formulas and Algorithms. MATCH Communications in Mathematical and in Computer Chemistry, 51, 129-136.
[7]	Liu, S. (2019) On the (Signless) Laplacian Permanental Polynomials of Graphs. Graph Combine, 35, 787-803.
[8]	Brualdi, R.A. and Goldwasser, J.L. (1984) Permanent of the Laplacian Matrix of Trees and Bipartite Graphs. Discrete Mathematics, 48, 1-21. https://doi.org/10.1016/0012-365x(84)90127-4
[9]	Goldwasser, J.L. (1986) Permanent of the Laplacian Matrix of Trees with a Given Matching. Discrete Mathematics, 61, 197-212. https://doi.org/10.1016/0012-365x(86)90091-9
[10]	Cvetkovic, D., Rowlinson, P. and Simic, S. (2004) Spectral Generalizations of Line Graphs. Cambridge University Press. https://doi.org/10.1017/cbo9780511751752
[11]	West, D.B. (2001) Introduction to Graph Theory. Prentice Hall.
[12]	Geng, X., Hu, X. and Li, S. (2010) Further Results on Permanental Bounds for the Laplacian Matrix of Trees. Linear and Multilinear Algebra, 58, 571-587. https://doi.org/10.1080/03081080902765583
[13]	Geng, X., Hu, S. and Li, S. (2014) Permanental Bounds of the Laplacian Matrix of Trees with Given Domination Number. Graphs and Combinatorics, 31, 1423-1436. https://doi.org/10.1007/s00373-014-1451-z
[14]	Li, S. and Zhang, L. (2011) Permanental Bounds for the Signless Laplacian Matrix of a Unicyclic Graph with Diameter D. Graphs and Combinatorics, 28, 531-546. https://doi.org/10.1007/s00373-011-1057-7
[15]	Li, S. and Zhang, L. (2011) Permanental Bounds for the Signless Laplacian Matrix of Bipartite Graphs and Unicyclic Graphs. Linear and Multilinear Algebra, 59, 145-158. https://doi.org/10.1080/03081080903261467
[16]	Li, S., Li, Y. and Zhang, X. (2013) Edge-Grafting Theorems on Permanents of Laplacian Matrices of Graphs and Their Applications. The Electronic Journal of Linear Algebra, 26, 28-48. https://doi.org/10.13001/1081-3810.1637