Ordering of Unicyclic Graphs with Perfect Matchings by Minimal Matching Energies ()
1. Introduction
Let G be a simple and undirected graph with n vertices and
be its adjacency matrix. Let
be the eigenvalues of
. Then the energy of G, denoted by
, is defined as [1]
A fundamental problem encountered within the study of graph energy is the characterization of the graphs that belong to a given class of graphs having maximal or minimal energy, for example, Trees with extremal energies [2] - [15] ; Unicyclic graphs with extremal energies [16] - [21] ; Bicyclic graphs with extremal energies [22] [23] [24] [25] ; Tricyclic graphs with extremal energies [26] [27] [28] . For more details, they can be found in the recent book [29] and review [30] .
A matching in a graph G is a set of pairwise nonadjacent edges. A matching is called k-matching if its size is k. Let
be the number of k-matching of G, where
for
or
. In addition, we assume that
.
The matching polynomial of a graph G is defined as
Recently, Gutman and Wagner [31] generalized the concept of graph energy and defined the matching energy of a graph G based on the zeros of its matching polynomial.
Definition 1.1. Let G be a simple graph of order n and
be the zeros of its matching polynomial. Then
Further, Gutman and Wagner [31] pointed out that the matching energy is a quantity of relevance for chemical applications. They arrived at the simple relation:
where
is the so-called topological resonance energy of G, in connection with the chemical applications of matching energy, for more details see [32] [33] [34] .
Similar to the integral formula for the energy of graph, Gutman and Wagner [31] have shown a beautiful integral formula for the matching energy of a graph G as follows:
(1)
Then
is a strictly monotonically increasing function of those numbers
. In the followings, the method of the quasi-order relation “
” is an important tool of comparing the matching energies of a pair of graphs.
Definition 1.2. Let
and
be two graphs of order n. If
for all k with
, then we write
.
Furthermore, if
and there exists at least one index j such that
, then we write
. If
for all k, then we write
. According to the integral formula (1), we have for two graphs
and
of order n that
In [31] , Gutman and Wagner shown that its matching energy coincides with its energy if T is a forest. Many properties of the matching energy are analogous to those of the graph energy. However, there are some notable differences. Then they raised a question: is it true that the matching energy of a graph G coincides with its energy if and only if G is a forest? Up to now, the question is still open.
The study on extremal matching energies is very interesting. In [31] , Gutman and Wagner characterized the unicyclic graphs with the minimal and maximal matching energy. Zhu and Yang [35] determined the unicyclic graphs with the first eight minimal matching energies. In [36] , Chen and Liu characterized the bipartite unicyclic graphs with the first
largest matching energies. Moreover, Chen et al. [37] determined the unicyclic odd-cycle graphs with the second to the fourth maximal matching energies. For bicyclic graph, Ji et al. [38] obtained the graphs with the minimal and maximal matching energy. In [39] , Liu et al. further determined the bicyclic graphs with first five minimal matching energies and the second maximal matching energies, respectively. Chen and Shi [40] characterized tricyclic graph with maximal matching energy, for more results about extremal matching energies, see [41] - [47] .
A fundamental problem encountered within the study of the matching energy is the characterization of the graphs that belong to a given class of graphs having maximal or minimal matching energy. One of the graph classes that are quite interestingly studied is the class of all unicyclic graphs with perfect matchings. As far as we are concerned, no results are on this topic. In this paper, we first present a new technique of directly comparing the matching energies of
and
in Section 2 (see Figure 2). As the applications of the technique, then we can determine the unicyclic graphs with perfect matchings of order 2n with the first to the ninth smallest matching energies for all
in Section 3.
For simplicity, if
is isomorphic to
, then we write
. If
is not isomorphic to
, then we write
. Let
be the set of the unicyclic graphs with perfect matchings of order 2n. Let the unicyclic graphs
,
,
,
,
,
,
,
,
,
be shown in Figure 1. The following theorem is the main result of this paper.
Theorem 1.1. Let
and
. If
, then
.
2. A New Technique of Directly Comparing the Matching Energies of
and
By Definition 1.2, we can see that the quasi-order method can be used to compare the matching energies of two graphs. However, if the quantities
cannot be compared uniformly, then the common comparing method is invalid, and this happens quite often. Recently much effort has been made to tackle these quasi-order incomparable problems [35] [39] [40] .
Let u and v be the non-isolated vertices of the graphs G and H with the same order, respectively. Let
be a non-isolated vertex of graph
where
. We use
(respectively,
) to denote the graph which is the coalescence of G (repectively, H) and
by identifying the vertices u (respectively, v) and
(see Figure 2). In [14] , He et al. presented a new method of directly comparing the energies of the bipartite graphs
and
. In this section, we apply the main idea of this method to present a new technique of comparing the matching energies of the graphs
and
which can be used to tackle these quasi-order incomparable problems.
In this paper, we assume that
(2)
By Equation (2), we can immediately obtain the following results.
Lemma 2.1. If two graphs G and H are disjoint, then
Lemma 2.2. ( [35] ) Let
be a graph. If u is a vertex of G, then
The coalescence of two graphs G and H with respect to vertex u in G and vertex v in H, denoted by
(sometimes abbreviated as
), is the graph obtained by identifying the vertices u and v. Zhu and Yang [35] shown the recurrence relation of
in the following. For convenience of the reader, we present a full proof.
Lemma 2.3. ( [35] ) Let
be the coalescence of two graphs G and H with respect to vertex u in G and vertex v in H. Then
Proof. Using Lemmas 2.1 and 2.2, we can show
Figure 1. The graphs in
with the first to the ninth smallest matching energies. For each graph
, the dashed lines denote the copies of
attached to the maximal degree vertex.
Figure 2. The graphs
and
.
From Lemma 2.3, we can get the recurrence relations of the graphs
and
which is a generalization of the formula for
.
Lemma 2.4. Let
and
be defined as above (see Figure 2). Then we have the followings.
1)
2)
Proof. 1) We prove the result by induction on k. When
, by Lemma 2.3 we have
which implies that the result holds. We assume that the result holds for
in what follows. For simplicity, we write
. By Lemmas 2.1 and 2.3, we can show
Then we can see that the result holds.
2) The proof is similar to 1).
The following lemma illustrates an integral formula for the difference of the matching energies of two graphs with the same order which was obtained by Zhu and Yang [35] .
Lemma 2.5. ( [35] ) Let
and
be the matching polynomials of two graphs G and H with the same order, respectively. Then
Let
. For simplicity, we write
From Lemma 2.2, we have
and
holds for any positive integer
.
In what follows, we define two sets M and
as follows:
It is easily checked that
. Furthermore, we write
Combining Lemma 2.4 with Lemma 2.5, we can present a new technique for directly comparing the matching energies of two graphs
and
in the following theorem.
Theorem 2.2. Let M,
,
and
be defined as above. For all positive integers
, we have
Proof. By some calculations, we can obtain that
Thus, If
, then
. If
, then
.
Moreover, by Lemmas 2.4 and 2.5, we have
Then the result can be obtained immediately.
Next, we use the new technique to compare the matching energies of the quasi-order incomparable graphs
and
,
and
(see Figure 1), respectively. Denote by
and
the cycle of length k and the path of length
, respectively.
Lemma 2.6. If
, then
.
Proof. Let G be the graph obtained by attaching a pendent edge to a vertex u of
. Let H be the graph obtained by attaching a pendent edge and a pendent path of length 2 to the vertices w and v of
, respectively. Let
and
be the pendent vertex of
. Then
and
(see Figure 1). By some calculations, we can show
It follows that
This implies that
and
. By Theorem 2.2 and some calculations using the software MATLAB, we have
Thus,
.
Lemma 2.7. If
, then
.
Proof. Let G be the graph obtained by attaching two pendent paths of length 2 to the same vertex of
. Let H be the graph obtained by first attaching a pendent edge to each vertex of
and then attaching a pendent path of length 2 to one vertex of
. Let u be the vertex of degree 4 in G and v be the vertex of degree 3 in H, respectively. Let
and
be the pendent vertex of
. Then
and
(see Figure 1). By some calculations, we can get the followings.
which implies that
It follows that
and
. By Theorem 2.2 and some calculations using the software MATLAB, we have
Consequently,
.
3. Minimal Matching Energies of Unicyclic Graphs with Perfect Matchings of Order 2n
In this section, we will determine the unicyclic graphs with perfect matchings of order 2n with the first to the ninth smallest matching energies (i.e., to prove Theorem 1.1).
In what follows, we denote by
a perfect matching of a graph G. Let
, where
is the set of isolated vertices in
. We call
the capped graph of G and G the original graph of
. For example, the capped graphs of
are shown in Figure 3.
Let
. Denote by
the edge set of G. It is easy to see that
. Thus each k-matching
of G can be partitioned into two parts:
, where
and
. Let
be the number of ways to choose k independent edges in G such that just j edges are in
. We agree that
and
. For example:
and
.
Then we have
(3)
where
This is the main method to compute
of a graph G in what follows.
Figure 3. The capped graphs of
and
. For each graph, the dashed lines denote the copies of
attached to the maximal degree vertex.
Let
be the star of order n. Let
be the graph of order n obtained by attaching
pendent edges to a pendent vertex of
. Let
be the graph of order n obtained from
by attaching
and one pendent edges to
and
, respectively. In [2] and [31] , the following results were shown.
Lemma 3.1. ( [2] ) Let T be a tree of order
. Then
, and the equalities do not hold for all k, where
and
.
Lemma 3.2. ( [31] ) Suppose that G is a connected graph and T is an induced subgraph of G such that T is a tree and T is connected to the rest of G only by a cut vertex v. If T is replaced by a star of the same order, centered at v, then the quasi-order decreases (unless T is already such a star).
Let
be the unicyclic graph of order n obtained by attaching
pendent edges to one vertex of
.
Lemma 3.3. ( [43] ) Let G be a unicyclic graph of order n with a cycle of length l. If
, then
.
Let
be the graph of order n obtained by attaching
and one pendent edges to
and
of
, respectively. Let
be the unicyclic graph obtained by attaching
pendent edges to
of
, respectively. Let
be the graph of order n obtained by attaching
pendent edges to the pendent vertex of
. The graphs
,
and
are shown in Figure 4.
Lemma 3.4. Let G be a unicyclic graph of order
. If
, then
.
Proof. Let G be a unicyclic graph with the unique cycle of length l. We consider the following cases.
Case 1:
.
By Lemma 3.10, we have
. Then
.
Case 2:
.
Using Lemma 3.10, we can show
. So,
.
Case 3:
.
Denote by
the degree of the vertex u in G. Let
be the unique cycle of the unicyclic graph G and
.
Figure 4. The graphs
,
and
in Lemma 3.4. For each graph, the dashed lines denote the copies of
attached to the maximal degree vertex.
Subcase 3.1:
.
Without loss of generality, we can assume that
. Let T be the rooted tree of order
with the root
in G. If
, then
(
). Then
. If
, then
. If
, then by Lemma 3.8 we have
.
Subcase 3.2:
.
Without loss of generality, we can assume that
and
. Let
and
be the rooted tree with the root
and
in G, respectively.
If
or
, then by Lemma 3.9 we can show
. Since
, we have
.
If
and
, then by Lemma 3.9 we have
(
). Thus,
.
Subcase 3.3:
.
According to Lemma 3.9, we have
(
). Then we have
Thus we have completed the proof.
Lemma 3.5. Let
and
. If
, then
.
Proof. We consider the following cases.
Case 1:
is a connected graph.
Subcase 1.1:
is a tree.
It can easily be verified that
as
and
as
. Thus,
. By Lemma 3.8, we have
.
Subcase 1.2:
is a connected unicyclic graph.
It can be shown that
as
and
as
. Therefore,
. According to Lemma 3.11, we have
.
Case 2:
is a unconnected graph.
Subcase 2.1:
is only composed of trees.
It can be checked that
as
. Then,
. Let
be the coalescence of all trees in a way such that
. It is clear that
. Similar to Subcase 1.1, we have
.
Subcase 2.2:
is composed of trees and unicyclic graphs.
Let
be the coalescence of all trees and unicyclic graphs in a way such that
. It is obvious that
. Similar to Subcase 1.2, we have
.
Then we have completed the proof.
From Lemma 3.5, we can immediately derive the following result.
Lemma 3.6. Let
and
. If
, then
.
Proof. By Equation (3) and Lemma 3.12, when
, we can get
Furthermore, by some calculations we have
Then we can see that
.
Combining Lemma 2.6 with Lemma 2.7, we can show the followings.
Lemma 3.7. If
, then
.
Proof. Using Equation (4) and some calculations, we can get
It implies that
and
. From Lemmas 2.6 and 2.7, the result can be easily obtained.
Proof of Theorem 1.1:
Proof. The result can follow immediately by Lemmas 3.13 and 3.14.
4. Conclusions
In this paper, we first present a new technique of directly comparing the matching energies of
and
, which can tackle some quasi-order incomparable problems. As the applications of the technique, we then determine the unicyclic graphs with perfect matchings of order 2n with the first to the ninth smallest matching energies for all
. Furthermore, we can consider characterizing the extremal graphs with maximal or minimal matching energy for other classes of graphs, e.g. graphs with different parameters. These are our work in the future.
The results presented in this paper are for a fixed graph. In reality, most of the graphs or networks are evolving. Some graph invariants have been studied in this setting, e.g. the Estrada index of evolving graphs [48] ; Laplacian Estrada and normalized Laplacian Estrada indices of evolving graphs [49] . Then we can consider studying the matching energy of evolving graphs in the future.
Acknowledgements
We thank the editor and the referee for their valuable comments. This work is supported by the National Natural Science Foundation of China (No. 11501356) and (No. 11426149).