1. Introduction
Let
be an
matrix. The permanent of
is defined as
where
is the symmetric group of degree
. Valiant [1] proved that even for (0,1)-matrices, computing the permanent is
-complete.
Let
be a simple connected graph with
vertices, and let
denote the degree of vertex
in
. The adjacency matrix and degree matrix of graph
are denoted by
and
, respectively. The Laplacian matrix of graph
is defined as
. 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
vertices. They also gave bounds for
.
Theorem 1. ([8]) Let
be an
-vertex tree. Then
The lower bound is achieved if and only if
is a star, and the upper bound is achieved if and only if
is a path.
When
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
-vertex tree with maximum degree
, what is the maximum value of the Laplacian permanent?
Problem 2. ([8]) For an
-vertex tree with matching number
, what is the maximum value of the Laplacian permanent?
Problem 3. ([8]) For an
-vertex tree that is a
-bipartition, what is the maximum value of the Laplacian permanent?
Brualdi and Goldwasser [8] defined the Laplacian permanent
of a graph.
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
. 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
-vertex trees with maximum degree
?
Problem 5. ([8]) What is the minimum value of the Laplacian ratios of
-vertex trees with
-matching?
Problem 6. ([8]) What is the maximum value of the Laplacian ratios of
-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
-vertex caterpillar tree
, there exists an
-vertex caterpillar tree
such that
. 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
be a graph. If
has a
-path, then the distance between
and
(denoted by
, or simply
) is the length of the shortest
-path. The diameter is defined as
.
is a path with diameter
. A caterpillar is a tree that consists of a central path with leaves attached to it. A broom graph
is obtained by attaching
pendant vertices to one end of a path
with
vertices.
is the star graph with
vertices.
denotes the Laplacian matrix of graph
after removing the rows and columns corresponding to the vertices in
. In particular, if
and
, then
can be abbreviated as
. Let
be an
matrix.
denotes the
submatrix obtained by deleting the
-th and
-th rows and columns of
.
denotes the
submatrix obtained by deleting the
-th row and column of
. Let
be the
submatrix obtained by deleting the first row and column of
.
Lemma 2. Let
be an
matrix and
. Then
Lemma 3. ([8]) Let
be a tree. Then
Lemma 4. ([8]) Let
and
be integers. Then
and
Lemma 5. ([16]) Let
be a path. Let
be the tree obtained by attaching
pendant vertices to vertex
of path
. Then
Lemma 6. ([11]) A tree is a caterpillar if and only if it contains no
-structure (see Figure 1).
Figure 1.
-structure.
3. Main Results
Lemma 7. Let
and
be the graphs shown in Figure 2. Then
(i)
,
(ii)
.
Figure 2.
and
.
Proof. By expanding the first row and column of
, we obtain the permanent of the Laplacian matrix of
.
By Lemma 2, the permanent of
can be expanded as
.
By Lemma 4,
.
By expanding the first row and column of
, we obtain the permanent of the Laplacian matrix of
.
By Lemma 2, the permanent of
can be expanded as
.
By Lemma 4,
.
□
Lemma 8. Let
and
be two trees. Then
(i)
,
(ii)
.
Proof. By Lemma 5,
,
.
By Lemma 4,
□
Definition 1. Let
be a tree containing a
-structure, where
is the central vertex of the
-structure, and
, where
are pendant vertices in
, and
are non-pendant vertices in
.
is obtained by contracting the edges
and then attaching all vertices
to
. We call
the graph obtained from
by Graph Transformation 1.
Theorem 9. Let
and
be the graphs shown in Figure 3. Then
.
Figure 3. Graph Transformation 1.
Proof. Let
be the set of all
-matchings of
, and let
be the set of all
-matchings of
. We can partition the
-matchings of
into two types: those that do not contain vertex
, denoted by
, and those that contain vertex
, denoted by
. Clearly,
. Let the edges incident to
in
be labeled as
, where
are non-pendant edges, and
are pendant edges. Let
be the corresponding edges in
(without applying Graph Transformation 4). Let
be the set of all
-matchings of
that contain
, denoted by
, and those that do not contain
, denoted by
. Clearly,
. Due to the structure of
and
, for any
, there exists a
such that
. We further partition
into two subsets:
(those
-matchings that contain one of
) and
(those
-matchings that contain one of
). Clearly,
. Similarly, we partition
into two subsets:
(those
-matchings that contain one of
) and
(those
-matchings that contain one of
). Clearly,
. Due to the structure of
and
, we have
. Therefore, for any
, there exists a
, such that
. Now consider
and
. For
,
For
,
Since
, we have
. Therefore,
. Thus, we have
, and hence
. □
Theorem 10. For any
-vertex caterpillar tree
, there exists an
-vertex caterpillar tree
such that
.
Proof. Since
is a caterpillar tree, by Lemma 6,
must contain a
-structure. By applying Graph Transformation 1, we can reduce the number of
-structures in
. If
still contains a
-structure, we can apply Graph Transformation 1 again to transform
into a graph
without any
-structure. By Lemma 6,
is a caterpillar tree, and
. □
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.