Open Journal of Discrete Mathematics
Vol.09 No.01(2019), Article ID:90223,16 pages
10.4236/ojdm.2019.91004

Ordering of Unicyclic Graphs with Perfect Matchings by Minimal Matching Energies

Jianming Zhu

Department of Applied Mathematics, Shanghai University of International Business and Economics, Shanghai, China

Copyright © 2019 by author(s) and Scientific Research Publishing Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

Received: December 28, 2018; Accepted: January 25, 2019; Published: January 28, 2019

ABSTRACT

In 2012, Gutman and Wagner proposed the concept of the matching energy of a graph and pointed out that its chemical applications can go back to the 1970s. The matching energy of a graph is defined as the sum of the absolute values of the zeros of its matching polynomial. Let u and v be the non-isolated vertices of the graphs G and H with the same order, respectively. Let w i be a non-isolated vertex of graph G i where i = 1 , 2 , , k . We use G u ( k ) (respectively, H v ( k ) ) to denote the graph which is the coalescence of G (respectively, H) and G 1 , G 2 , , G k by identifying the vertices u (respectively, v) and w 1 , w 2 , , w k . In this paper, we first present a new technique of directly comparing the matching energies of G u ( k ) and H v ( k ) , which can tackle some quasi-order incomparable problems. 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 n 211 .

Keywords:

Matching Energy, Unicyclic Graph, Perfect Matching

1. Introduction

Let G be a simple and undirected graph with n vertices and A ( G ) be its adjacency matrix. Let λ 1 , λ 2 , , λ n be the eigenvalues of A ( G ) . Then the energy of G, denoted by E ( G ) , is defined as [1]

E ( G ) = i = 1 n | λ i | .

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 m ( G , k ) be the number of k-matching of G, where m ( G , k ) = 0 for k > n / 2 or k < 0 . In addition, we assume that m ( G , 0 ) = 1 .

The matching polynomial of a graph G is defined as

α ( G ) = α ( G , x ) = k = 0 n / 2 ( 1 ) k m ( G , k ) x n 2 k .

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 μ 1 , μ 2 , , μ n be the zeros of its matching polynomial. Then

M E ( G ) = i = 1 n | μ i | .

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:

T R E ( G ) = E ( G ) M E ( G ) ,

where T R E ( G ) 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:

M E ( G ) = 2 π 0 + 1 x 2 ln ( k = 0 n / 2 m ( G , k ) x 2 k ) d x . (1)

Then M E ( G ) is a strictly monotonically increasing function of those numbers m ( G , k ) ( k = 0 , 1 , , n / 2 ) . 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 G 1 and G 2 be two graphs of order n. If m ( G 1 , k ) m ( G 2 , k ) for all k with 1 k n / 2 , then we write G 1 G 2 .

Furthermore, if G 1 G 2 and there exists at least one index j such that m ( G 1 , j ) < m ( G 2 , j ) , then we write G 1 G 2 . If m ( G 1 , k ) = m ( G 2 , k ) for all k, then we write G 1 G 2 . According to the integral formula (1), we have for two graphs G 1 and G 2 of order n that

G 1 G 2 M E ( G 1 ) M E (G2)

G 1 G 2 M E ( G 1 ) < M E ( G 2 ) .

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 ( n 3 ) / 4 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 G u ( k ) and H v ( k ) 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 n 211 in Section 3.

For simplicity, if G 1 is isomorphic to G 2 , then we write G 1 = G 2 . If G 1 is not isomorphic to G 2 , then we write G 1 G 2 . Let A ( 2 n ) be the set of the unicyclic graphs with perfect matchings of order 2n. Let the unicyclic graphs A 1 , A 2 , A 3 , A 4 , A 4 * , A 5 , A 6 , A 7 , A 8 , A 9 be shown in Figure 1. The following theorem is the main result of this paper.

Theorem 1.1. Let G A ( 2 n ) and n 211 . If G A 1 , A 2 , A 3 , A 4 , A 4 * , A 5 , A 6 , A 7 , A 8 , A 9 , then M E ( A 1 ) < M E ( A 2 ) < M E ( A 3 ) < M E ( A 4 ) = M E ( A 4 * ) < M E ( A 5 ) < M E ( A 6 ) < M E ( A 7 ) < M E ( A 8 ) < M E ( A 9 ) < M E ( G ) .

2. A New Technique of Directly Comparing the Matching Energies of G u ( k ) and H v (k)

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 m ( G , k ) 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 w i be a non-isolated vertex of graph G i where i = 1 , 2 , , k . We use G u ( k ) (respectively, H v ( k ) ) to denote the graph which is the coalescence of G (repectively, H) and G 1 , G 2 , , G k by identifying the vertices u (respectively, v) and w 1 , w 2 , , w k (see Figure 2). In [14] , He et al. presented a new method of directly comparing the energies of the bipartite graphs G u ( k ) and H v ( k ) . In this section, we apply the main idea of this method to present a new technique of comparing the matching energies of the graphs G u ( k ) and H v ( k ) which can be used to tackle these quasi-order incomparable problems.

In this paper, we assume that

α ˜ ( G ) = α ˜ ( G , x ) = k = 0 n / 2 m ( G , k ) x n 2 k . (2)

By Equation (2), we can immediately obtain the following results.

Lemma 2.1. If two graphs G and H are disjoint, then

α ˜ ( G H ) = α ˜ ( G ) α ˜ ( H ) .

Lemma 2.2. ( [35] ) Let G = ( V ( G ) , E ( G ) ) be a graph. If u is a vertex of G, then

α ˜ ( G ) = x α ˜ ( G u ) + u v E ( G ) α ˜ ( G u v ) .

The coalescence of two graphs G and H with respect to vertex u in G and vertex v in H, denoted by G u H v (sometimes abbreviated as G H ), is the graph obtained by identifying the vertices u and v. Zhu and Yang [35] shown the recurrence relation of α ˜ ( G H ) in the following. For convenience of the reader, we present a full proof.

Lemma 2.3. ( [35] ) Let G H be the coalescence of two graphs G and H with respect to vertex u in G and vertex v in H. Then

α ˜ ( G H ) = α ˜ ( G ) α ˜ ( H v ) + α ˜ ( G u ) ( α ˜ ( H ) x α ˜ ( H v ) ) .

Proof. Using Lemmas 2.1 and 2.2, we can show

α ˜ ( G H ) = x α ˜ ( G H u ) + u w E ( G ) α ˜ ( G H u w ) + v t E ( H ) α ˜ ( G H v t ) = x α ˜ ( G u ) α ˜ ( H v ) + u w E ( G ) α ˜ ( G u w ) α ˜ ( H v ) + v t E ( H ) α ˜ ( G u ) α ˜ ( H v t ) = ( x α ˜ ( G u ) + u w E ( G ) α ˜ ( G u w ) ) α ˜ ( H v ) + α ˜ ( G u ) v t E ( H ) α ˜ ( H v t ) = α ˜ ( G ) α ˜ ( H v ) + α ˜ ( G u ) ( α ˜ ( H ) x α ˜ ( H v ) ) .

Figure 1. The graphs in A ( 2 n ) with the first to the ninth smallest matching energies. For each graph A i , the dashed lines denote the copies of P 3 attached to the maximal degree vertex.

Figure 2. The graphs G u ( k ) and H v ( k ) .

From Lemma 2.3, we can get the recurrence relations of the graphs α ˜ ( G u ( k ) ) and α ˜ ( H v ( k ) ) which is a generalization of the formula for α ˜ ( G H ) .

Lemma 2.4. Let G u ( k ) and H v ( k ) be defined as above (see Figure 2). Then we have the followings.

1) α ˜ ( G u ( k ) ) = i = 1 k α ˜ ( G i w i ) ( α ˜ ( G ) + α ˜ ( G u ) ( i = 1 k α ˜ ( G i ) α ˜ ( G i w i ) k x ) ) ;

2) α ˜ ( H v ( k ) ) = i = 1 k α ˜ ( G i w i ) ( α ˜ ( H ) + α ˜ ( H v ) ( i = 1 k α ˜ ( G i ) α ˜ ( G i w i ) k x ) ) .

Proof. 1) We prove the result by induction on k. When k = 1 , by Lemma 2.3 we have

α ˜ ( G u ( 1 ) ) = α ˜ ( G G 1 ) = α ˜ ( G ) α ˜ ( G 1 w 1 ) + α ˜ ( G u ) ( α ˜ ( G 1 ) x α ˜ ( G 1 w 1 ) ) ,

which implies that the result holds. We assume that the result holds for k 1 in what follows. For simplicity, we write h k = i = 1 k α ˜ ( G i ) α ˜ ( G i w i ) k x . By Lemmas 2.1 and 2.3, we can show

α ˜ ( G u ( k ) ) = α ˜ ( G u ( k 1 ) G k ) = α ˜ ( G u ( k 1 ) ) α ˜ ( G k w k ) + α ˜ ( G u ( k 1 ) u ) ( α ˜ ( G k ) x α ˜ ( G k w k ) ) = i = 1 k 1 α ˜ ( G i w i ) ( α ˜ ( G ) + α ˜ ( G u ) h k 1 ) α ˜ ( G k w k ) + i = 1 k 1 α ˜ ( G i w i ) α ˜ ( G u ) ( α ˜ ( G k ) x α ˜ ( G k w k ) ) = i = 1 k 1 α ˜ ( G i w i ) ( ( α ˜ ( G ) + α ˜ ( G u ) h k 1 ) α ˜ ( G k w k )

+ α ˜ ( G u ) ( α ˜ ( G k ) α ˜ ( G k w k ) ) ) = i = 1 k 1 α ˜ ( G i w i ) α ˜ ( G k w k ) ( α ˜ ( G ) + α ˜ ( G u ) h k 1 + α ˜ ( G u ) ( α ˜ ( G k ) α ˜ ( G k w k ) x ) ) = i = 1 k α ˜ ( G i w i ) ( α ˜ ( G ) + α ˜ ( G u ) h k 1 + α ˜ ( G u ) ( α ˜ ( G k ) α ˜ ( G k w k ) x ) ) = i = 1 k α ˜ ( G i w i ) ( α ˜ ( G ) + α ˜ ( G u ) ( h k 1 + α ˜ ( G k ) α ˜ ( G k w k ) x ) ) = i = 1 k α ˜ ( G i w i ) ( α ˜ ( G ) + α ˜ ( G u ) h k )

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 α ( G , x ) and α ( H , x ) be the matching polynomials of two graphs G and H with the same order, respectively. Then

M E ( G ) M E ( H ) = 2 π 0 + ln α ˜ ( G , x ) α ˜ ( H , x ) d x .

Let x > 0 . For simplicity, we write

h k = i = 1 k α ˜ ( G i ) α ˜ ( G i w i ) k x = i = 1 k α ˜ ( G i ) x α ˜ ( G i w i ) α ˜ ( G i w i ) .

From Lemma 2.2, we have h k > 0 and h l < h k holds for any positive integer l < k .

In what follows, we define two sets M and M c as follows:

M = { x > 0 | α ˜ ( G u ) α ˜ ( H ) α ˜ ( G ) α ˜ ( H v ) > 0 }

M c = { x > 0 | α ˜ ( G u ) α ˜ ( H ) α ˜ ( G ) α ˜ ( H v ) 0 } .

It is easily checked that M M c = ( 0, + ) . Furthermore, we write

m k ( x ) = α ˜ ( G ) + h k α ˜ ( G u ) α ˜ ( H ) + h k α ˜ ( H v )

m ( x ) = α ˜ ( G u ) α ˜ ( H v ) .

Combining Lemma 2.4 with Lemma 2.5, we can present a new technique for directly comparing the matching energies of two graphs G u ( k ) and H v ( k ) in the following theorem.

Theorem 2.2. Let M, M c , m k ( x ) and m ( x ) be defined as above. For all positive integers 1 l < k , we have

M ln m l ( x ) d x + M c ln m ( x ) d x π 2 ( M E ( G u ( k ) ) M E ( H v ( k ) ) ) M ln m ( x ) d x + M c ln m l ( x ) d x .

Proof. By some calculations, we can obtain that

m k ( x ) m l ( x ) = α ˜ ( G ) + h k α ˜ ( G u ) α ˜ ( H ) + h k α ˜ ( H v ) α ˜ ( G ) + h l α ˜ ( G u ) α ˜ ( H ) + h l α ˜ ( H v ) = ( h k h l ) ( α ˜ ( G u ) α ˜ ( H ) α ˜ ( G ) α ˜ ( H v ) ) ( α ˜ ( H ) + h k α ˜ ( H v ) ) ( α ˜ ( H ) + h l α ˜ ( H v ) ) .

m k ( x ) m ( x ) = α ˜ ( G ) + h k α ˜ ( G u ) α ˜ ( H ) + h k α ˜ ( H v ) α ˜ ( G u ) α ˜ ( H v ) = ( α ˜ ( G u ) α ˜ ( H ) α ˜ ( G ) α ˜ ( H v ) ) ( α ˜ ( H ) + h k α ˜ ( H v ) ) α ˜ ( H v ) .

Thus, If x M , then m l ( x ) m k ( x ) m ( x ) . If x M c , then m ( x ) m k ( x ) m l ( x ) .

Moreover, by Lemmas 2.4 and 2.5, we have

π 2 ( M E ( G u ( k ) ) M E ( H v ( k ) ) ) = 0 + ln m k ( x ) d x = M ln m k ( x ) d x + M c ln m k ( x ) d x .

Then the result can be obtained immediately.

Next, we use the new technique to compare the matching energies of the quasi-order incomparable graphs A 5 and A 6 , A 8 and A 9 (see Figure 1), respectively. Denote by C k and P k the cycle of length k and the path of length k 1 , respectively.

Lemma 2.6. If n 6 , then M E ( A 5 ) < M E ( A 6 ) .

Proof. Let G be the graph obtained by attaching a pendent edge to a vertex u of C 5 . 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 C 3 , respectively. Let G 1 = G 2 = = G n 3 = P 3 and w i be the pendent vertex of G i . Then G u ( n 3 ) = A 5 and H v ( n 3 ) = A 6 (see Figure 1). By some calculations, we can show

α ˜ ( G ) = x 6 + 6 x 4 + 8 x 2 + 1

α ˜ ( G u ) = x ( x 4 + 3 x 2 + 1 )

α ˜ ( H ) = x 6 + 6 x 4 + 7 x 2 + 1

α ˜ ( H v ) = ( x 2 + 1 ) ( x 3 + 2 x ) .

It follows that

α ˜ ( G u ) α ˜ ( H ) α ˜ ( G ) α ˜ ( H v ) = 2 x 7 9 x 5 9 x 3 x .

This implies that M = and M c = ( 0 , + ) . By Theorem 2.2 and some calculations using the software MATLAB, we have

π 2 ( M E ( A 5 ) M E ( A 6 ) ) = π 2 ( M E ( G u ( n 3 ) ) M E ( H v ( n 3 ) ) ) 0 + ln m 3 ( x ) d x = 0 + ln ( x 2 + 1 ) 2 ( x 8 + 10 x 6 + 23 x 4 + 12 x 2 + 1 ) ( x 2 + 1 ) 3 ( x 6 + 9 x 4 + 13 x 2 + 1 ) d x 0.0248 < 0.

Thus, M E ( A 5 ) < M E ( A 6 ) .

Lemma 2.7. If n 211 , then M E ( A 8 ) < M E ( A 9 ) .

Proof. Let G be the graph obtained by attaching two pendent paths of length 2 to the same vertex of C 4 . Let H be the graph obtained by first attaching a pendent edge to each vertex of C 3 and then attaching a pendent path of length 2 to one vertex of C 3 . Let u be the vertex of degree 4 in G and v be the vertex of degree 3 in H, respectively. Let G 1 = G 2 = = G n 4 = P 3 and w i be the pendent vertex of G i . Then G u ( n 4 ) = A 8 and H v ( n 4 ) = A 9 (see Figure 1). By some calculations, we can get the followings.

α ˜ ( G ) = x 8 + 8 x 6 + 17 x 4 + 12 x 2 + 2

α ˜ ( G u ) = ( x 2 + 1 ) 2 ( x 3 + 2 x )

α ˜ ( H ) = x 8 + 8 x 6 + 15 x 4 + 8 x 2 + 1

α ˜ ( H v ) = x ( x 6 + 5 x 4 + 5 x 2 + 1 ) ,

which implies that

α ˜ ( G u ) α ˜ ( H ) α ˜ ( G ) α ˜ ( H v ) = x 3 ( x 2 + 1 ) 2 ( x 6 + 8 x 4 + 11 x 2 + 1 ) .

It follows that M = and M c = ( 0 , + ) . By Theorem 2.2 and some calculations using the software MATLAB, we have

π 2 ( M E ( A 8 ) M E ( A 9 ) ) = π 2 ( M E ( G u ( n 4 ) ) M E ( H v ( n 4 ) ) ) 0 + ln m 207 ( x ) d x = 0 + ln ( x 2 + 1 ) 208 ( x 6 + 214 x 4 + 424 x 2 + 2 ) ( x 2 + 1 ) 206 ( x 10 + 216 x 8 + 1055 x 6 + 1055 x 4 + 216 x 2 + 1 ) d x 7.43 × 10 5 < 0.

Consequently, M E ( A 8 ) < M E ( A 9 ) .

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 M ( G ) a perfect matching of a graph G. Let G ^ = G M ( G ) S 0 , where S 0 is the set of isolated vertices in G M ( G ) . We call G ^ the capped graph of G and G the original graph of G ^ . For example, the capped graphs of A 1 , A 2 , A 3 , A 5 are shown in Figure 3.

Let G A ( 2 n ) . Denote by E ( G ) the edge set of G. It is easy to see that E ( G ) = E ( G ^ ) M ( G ) . Thus each k-matching Ω of G can be partitioned into two parts: Ω = Φ Ψ , where Φ E ( G ^ ) and Ψ M ( G ) . Let r j ( 2 k ) ( G ) be the number of ways to choose k independent edges in G such that just j edges are in G ^ . We agree that r 0 ( 0 ) ( G ) = 1 and r j ( 2 k ) ( G ) = 0 ( k < 0 ) . For example: r 0 ( 2 k ) ( G ) = ( n k ) and r 1 ( 2 k ) ( G ) = n ( n 2 k 1 ) .

Then we have

m ( G , k ) = j = 0 k r j ( 2 k ) ( G ) = p + j = 2 k r j ( 2 k ) ( G ) , (3)

where

p = ( n k ) + n ( n 2 k 1 ) .

This is the main method to compute m ( G , k ) of a graph G in what follows.

Figure 3. The capped graphs of A 1 , A 2 , A 3 and A 5 . For each graph, the dashed lines denote the copies of P 2 attached to the maximal degree vertex.

Let X n be the star of order n. Let Y n be the graph of order n obtained by attaching n 3 pendent edges to a pendent vertex of P 3 . Let Z n be the graph of order n obtained from P 4 = v 1 v 2 v 3 v 4 by attaching n 5 and one pendent edges to v 2 and v 3 , respectively. In [2] and [31] , the following results were shown.

Lemma 3.1. ( [2] ) Let T be a tree of order n 5 . Then m ( X n , k ) m ( Y n , k ) m ( Z n , k ) m ( T , k ) , and the equalities do not hold for all k, where T X n , Y n , Z n and 0 k n / 2 .

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 S n l be the unicyclic graph of order n obtained by attaching n l pendent edges to one vertex of C l .

Lemma 3.3. ( [43] ) Let G be a unicyclic graph of order n with a cycle of length l. If G S n l , then G S n l .

Let R n 3 be the graph of order n obtained by attaching n 4 and one pendent edges to v 1 and v 2 of C 3 = v 1 v 2 v 3 v 1 , respectively. Let C 3 ( a , b , c ) be the unicyclic graph obtained by attaching a , b , c pendent edges to v 1 , v 2 , v 3 of C 3 = v 1 v 2 v 3 v 1 , respectively. Let Q n 3 be the graph of order n obtained by attaching n 4 pendent edges to the pendent vertex of C 3 ( 1,0,0 ) . The graphs S n 3 , R n 3 and Q n 3 are shown in Figure 4.

Lemma 3.4. Let G be a unicyclic graph of order n 9 . If G S n 3 , R n 3 , then m ( G ,2 ) 2 n 6 .

Proof. Let G be a unicyclic graph with the unique cycle of length l. We consider the following cases.

Case 1: l 5 .

By Lemma 3.10, we have G S n l . Then m ( G ,2 ) m ( S n l ,2 ) ( n l ) ( l 2 ) 3 ( n 5 ) 2 n 6 .

Case 2: l = 4 .

Using Lemma 3.10, we can show G S n 4 . So, m ( G , 2 ) m ( S n 4 , 2 ) = 2 n 6 .

Case 3: l = 3 .

Denote by d G ( u ) the degree of the vertex u in G. Let C 3 = v 1 v 2 v 3 v 1 be the unique cycle of the unicyclic graph G and N ( G ) = { v i | d G ( v i ) 3 , i = 1 , 2 , 3 } .

Figure 4. The graphs S n 3 , R n 3 and Q n 3 in Lemma 3.4. For each graph, the dashed lines denote the copies of P 2 attached to the maximal degree vertex.

Subcase 3.1: | N ( G ) | = 1 .

Without loss of generality, we can assume that d G ( v 1 ) 3 . Let T be the rooted tree of order n 2 with the root v 1 in G. If T = X n 2 , then G = Q n 3 ( G S n 3 ). Then m ( G , 2 ) = 3 n 11 > 2 n 6 . If T = Y n 2 , then m ( G , 2 ) ( n 3 ) + m ( Y n 2 , 2 ) + 2 = ( n 3 ) + ( n 5 ) + 2 = 2 n 6 . If T X n 2 , Y n 2 , then by Lemma 3.8 we have

m ( G , 2 ) ( n 3 ) + m ( T , 2 ) ( n 3 ) + m ( Z n 2 , 2 ) = n 3 + 2 ( n 6 ) = 3 n 15 2 n 6 .

Subcase 3.2: | N ( G ) | = 2 .

Without loss of generality, we can assume that d G ( v 1 ) 3 and d G ( v 2 ) 3 . Let T 1 and T 2 be the rooted tree with the root v 1 and v 2 in G, respectively.

If T 1 = P 2 or T 2 = P 2 , then by Lemma 3.9 we can show m ( G , 2 ) m ( R n 3 , 2 ) = 2 n 7 . Since G R n 3 , we have m ( G ,2 ) 2 n 6 .

If T 1 P 2 and T 2 P 2 , then by Lemma 3.9 we have G C 3 ( a , b ,0 ) ( a + b = n 3 ). Thus, m ( G , 2 ) m ( C 3 ( a , b , 0 ) , 2 ) a + b + a b n 3 + 2 ( n 5 ) = 3 n 13 > 2 n 6 .

Subcase 3.3: | N ( G ) | = 3 .

According to Lemma 3.9, we have G C 3 ( a , b , c ) ( a + b + c = n 3 ). Then we have

m ( G , 2 ) a + b + c + a b + b c + a c n 3 + a + b 1 + b + c 1 + a + c 1 = n 3 + 2 ( n 3 ) 3 = 3 n 12 > 2 n 6.

Thus we have completed the proof.

Lemma 3.5. Let G A ( 2 n ) and n 9 . If G A 1 , A 2 , A 3 , A 4 , A 4 * , A 5 , A 6 , A 7 , A 8 , A 9 , then m ( G ^ ,2 ) 2 n 6 .

Proof. We consider the following cases.

Case 1: G ^ is a connected graph.

Subcase 1.1: G ^ is a tree.

It can easily be verified that G = A 1 as G ^ = X n + 1 and G = A 3 , A 4 , A 4 * , A 6 as G ^ = Y n + 1 . Thus, G ^ X n + 1 , Y n + 1 . By Lemma 3.8, we have m ( G ^ , 2 ) m ( Z n + 1 , 2 ) = 2 n 6 .

Subcase 1.2: G ^ is a connected unicyclic graph.

It can be shown that G = A 2 as G ^ = S n 3 and G = A 9 as G ^ = R n 3 . Therefore, G ^ S n 3 , R n 3 . According to Lemma 3.11, we have m ( G ^ ,2 ) 2 n 6 .

Case 2: G ^ is a unconnected graph.

Subcase 2.1: G ^ is only composed of trees.

It can be checked that G = A 5 , A 7 , A 8 as G ^ = X n P 2 . Then, G ^ X n P 2 . Let G ^ 1 be the coalescence of all trees in a way such that G ^ 1 X n + 1 , Y n + 1 . It is clear that m ( G ^ , 2 ) > m ( G ^ 1 , 2 ) . Similar to Subcase 1.1, we have m ( G ^ , 2 ) > 2 n 6 .

Subcase 2.2: G ^ is composed of trees and unicyclic graphs.

Let G ^ 2 be the coalescence of all trees and unicyclic graphs in a way such that G ^ 2 S n 3 , R n 3 . It is obvious that m ( G ^ , 2 ) > m ( G ^ 2 , 2 ) . Similar to Subcase 1.2, we have m ( G ^ , 2 ) > 2 n 6 .

Then we have completed the proof.

From Lemma 3.5, we can immediately derive the following result.

Lemma 3.6. Let G A ( 2 n ) and n 9 . If G A 1 , A 2 , A 3 , A 4 , A 4 * , A 5 , A 6 , A 7 , A 8 , A 9 , then G A 9 .

Proof. By Equation (3) and Lemma 3.12, when k 2 , we can get

m ( G , k ) = p + j = 2 k r j ( 2 k ) ( G ) p + r 2 ( 2 k ) ( G ) p + m ( G ^ ,2 ) ( n 4 k 2 ) p + ( 2 n 6 ) ( n 4 k 2 ) .

Furthermore, by some calculations we have

m ( A 9 , k ) = p + ( 2 n 7 ) ( n 4 k 2 ) .

Then we can see that G A 9 .

Combining Lemma 2.6 with Lemma 2.7, we can show the followings.

Lemma 3.7. If n 211 , then M E ( A 1 ) < M E ( A 2 ) < M E ( A 3 ) < M E ( A 4 ) = M E ( A 4 * ) < M E ( A 5 ) < M E ( A 6 ) < M E ( A 7 ) < M E ( A 8 ) < M E ( A 9 ) .

Proof. Using Equation (4) and some calculations, we can get

m ( A 1 , k ) = p

m ( A 2 , k ) = p + ( n 3 ) ( n 4 k 2 )

m ( A 3 , k ) = p + ( n 2 ) ( n 4 k 2 )

m ( A 4 , k ) = p + ( n 3 k 2 ) + ( n 3 ) ( n 4 k 2 )

m ( A 4 * , k ) = p + ( n 3 k 2 ) + ( n 3 ) ( n 4 k 2 )

m ( A 5 , k ) = p + 2 ( n 3 k 2 ) + ( n 3 ) ( n 4 k 2 )

m ( A 6 , k ) = p + ( n 3 ) ( n 3 k 2 )

m ( A 7 , k ) = p + ( n 1 ) ( n 3 k 2 )

m ( A 8 , k ) = p + ( n 2 k 2 ) + ( n 2 ) ( n 3 k 2 )

m ( A 9 , k ) = p + ( 2 n 7 ) ( n 4 k 2 ) .

It implies that A 1 A 2 A 3 A 4 A 5 and A 6 A 7 A 8 . 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 G u ( k ) and H v ( k ) , 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 n 211 . 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).

Conflicts of Interest

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

Cite this paper

Zhu, J.M. (2019) Ordering of Unicyclic Graphs with Perfect Matchings by Minimal Matching Energies. Open Journal of Discrete Mathematics, 9, 17-32. https://doi.org/10.4236/ojdm.2019.91004

References

  1. 1. Gutman, I. (1978) The Energy of a Graph. Berichte Mathematisch-statistische Sektion Forschungszentrum Graz, 103, 1-22.

  2. 2. Gutman, I. (1977) Acyclic Systems with Extremal Hukel-Electron Energy. Theoretica Chimica Acta, 45, 79-87. https://doi.org/10.1007/BF00552542

  3. 3. Li, N. and Li, S. (2008) On the Extremal Energy of Trees. MATCH Communications in Mathematical and in Computer Chemistry, 59, 291-314.

  4. 4. Gutman, I., Radenkovic, S., Li, N. and Li, S. (2008) Extremal Energy of Trees. MATCH Communications in Mathematical and in Computer Chemistry, 59, 315-320.

  5. 5. Wang, W. and Kang, L. (2010) Ordering of the Trees by Minimal Energy. Journal of Mathematical Chemistry, 47, 937-958. https://doi.org/10.1007/s10910-009-9616-3

  6. 6. Shan, H. and Shao, J. (2010) Graph Energy Change Due to Edge Grafting Operations and Its Applications. MATCH Communications in Mathematical and in Computer Chemistry, 64, 25-40.

  7. 7. Huo, B., Ji, S., Li, X. and Shi, Y. (2011) Complete Solution to a Conjecture on the Fourth Maximal Energy Tree. MATCH Communications in Mathematical and in Computer Chemistry, 66, 903-912.

  8. 8. Shan, H. and Shao, J. (2012) The Proof of a Conjecture on the Comparison of the Energies of Trees. Journal of Mathematical Chemistry, 50, 2637-2647. https://doi.org/10.1007/s10910-012-0052-4

  9. 9. Andriantiana, E.O.D. (2012) More Trees with Large Energy. MATCH Communications in Mathematical and in Computer Chemistry, 68, 675-695.

  10. 10. Shan, H., Shao, J., Zhang, L. and He, C. (2012) A New Method of Comparing the Energies of Subdivision Bipartite Graphs. MATCH Communications in Mathematical and in Computer Chemistry, 68, 721-740.

  11. 11. Shan, H., Shao, J., Zhang, L. and He, C. (2012) Proof of a Conjecture on Trees with Lagre Energy. MATCH Communications in Mathematical and in Computer Chemistry, 68, 703-720.

  12. 12. Gutman, I., Furtula, B., Andriantiana, E.O.D. and Cvetic, M. (2012) More Trees with Large Energy and Small Size. MATCH Communications in Mathematical and in Computer Chemistry, 68, 697-702.

  13. 13. MArn, C., Monsalve, J. and Rada, J. (2015) Maximum and Minimum Energy Trees with Two and Three Branched Vertices. MATCH Communications in Mathematical and in Computer Chemistry, 74, 285-306.

  14. 14. He, C., Lei, L., Shan, H. and Peng, A. (2017) Two Subgraph Grafting Theoerms on the Energy of Bipartite Graphs. Linear Algebra and its Applications, 515, 96-110. https://doi.org/10.1016/j.laa.2016.11.010

  15. 15. Zhu, J. and Yang, J. (2018) Minimal Energies of Trees with Three Branched Vertices. MATCH Communications in Mathematical and in Computer Chemistry, 79, 263-274.

  16. 16. Hou, Y. (2001) Unicyclic Graphs with Minimal Energy. Journal of Mathematical Chemistry, 29, 163-168. https://doi.org/10.1023/A:1010935321906

  17. 17. Hou, Y., Gutman, I. and Woo, C. (2002) Unicyclic Graphs with Maximal Energy. Linear Algebra and Its Applications, 356, 27-36. https://doi.org/10.1016/S0024-3795(01)00609-7

  18. 18. Andriantiana, E.O.D. (2011) Unicylic Bipartite Graphs with Maximum Energy. MATCH Communications in Mathematical and in Computer Chemistry, 66, 913-926.

  19. 19. Huo, B., Li, X. and Shi, Y. (2011) Complete Solution to a Conjecture on the Maximal Energy of Unicyclic Graphs. European Journal of Combinatorics, 32, 662-673. https://doi.org/10.1016/j.ejc.2011.02.011

  20. 20. Wang, W. (2011) Ordering of Unicyclic Graphs with Perfect Matchings by Minimal Energies. MATCH Communications in Mathematical and in Computer Chemistry, 66, 927-942.

  21. 21. Zhu, J. (2013) On Minimal Energies of Unicyclic Graphs with Perfect Mathching. MATCH Communications in Mathematical and in Computer Chemistry, 70, 97-118.

  22. 22. Zhang, J. and Zhou, B. (2005) On Bicyclic Graphs with Minimal Energies. Journal of Mathematical Chemistry, 37, 423-431. https://doi.org/10.1007/s10910-004-1108-x

  23. 23. Li, X. and Zhang, J. (2007) On Bicyclic Graphs with Maximal Energy. Linear Algebra and Its Applications, 427, 87-98. https://doi.org/10.1016/j.laa.2007.06.022

  24. 24. Huo, B., Ji, S., Li, X. and Shi, Y. (2011) Solution to a Conjecture on the Maximal Energy of Bipartite Bicyclic Graphs. Linear Algebra and Its Applications, 435, 804-810. https://doi.org/10.1016/j.laa.2011.02.001

  25. 25. Ji, S. and Li, J. (2012) An Approach to the Problem of the Maximal Energy of Bicyclic Graphs. MATCH Communications in Mathematical and in Computer Chemistry, 68, 741-762.

  26. 26. Li, S., Li, X. and Zhu, Z. (2008) On Tricyclic Graphs with Minimal Energy. MATCH Communications in Mathematical and in Computer Chemistry, 59, 397-419.

  27. 27. Li, X., Shi, Y. and Wei, M. (2014) On a Conjecture about Tricyclic Graphs with Maximal Energy. MATCH Communications in Mathematical and in Computer Chemistry, 72, 183-214.

  28. 28. Li, X., Mao, Y. and Liu, M. (2015) More on a Conjecture about Tricyclic Graphs with Maximal Energy. MATCH Communications in Mathematical and in Computer Chemistry, 73, 11-26. https://doi.org/10.1016/j.comcom.2015.07.003

  29. 29. Li, X., Shi, Y. and Gutman, I. (2012) Graph Energy. Springer, New York. https://doi.org/10.1007/978-1-4614-4220-2

  30. 30. Gutman, I. (2001) The Energy of a Graph: Old and New Results, Algebraic Combinatorics and Applications. Springer-Verlag, Berlin, 196-211.

  31. 31. Gutman, I. and Wagner, S. (2012) The Matching Energy of a Graph. Discrete Applied Mathematics, 160, 2177-2187. https://doi.org/10.1016/j.dam.2012.06.001

  32. 32. Aihara, J. (1976) A New Definition of Dewar-Type Resonance Energies. Journal of the American Chemical Society, 98, 2750-2758. https://doi.org/10.1021/ja00426a013

  33. 33. Gutman, I., Milun, M. and Trinajstic, N. (1975) Topological Definition of Delocalisation Energy. MATCH Communications in Mathematical and in Computer Chemistry, 1, 171-175.

  34. 34. Gutman, I., Milun, M. and Trinajstic, N. (1977) Graph Theory and Molecular Orbitals 19. Nonparametric Resonance Energies of Arbitrary Conjugated Systems. Journal of the American Chemical Society, 99, 1692-1704. https://doi.org/10.1021/ja00448a002

  35. 35. Zhu, J. and Yang, J. (2018) On the Minimal Matching Energies of Unicyclic Graphs. Discrete Applied Mathematics. https://doi.org/10.1016/j.dam.2018.06.013

  36. 36. Chen, L. and Liu, J. (2015) The Bipartite Unicyclic Graphs with the First Largest Matching Energies. Applied Mathematics and Computation, 268, 644-656. https://doi.org/10.1016/j.amc.2015.06.115

  37. 37. Chen, L., Liu, J. and Shi, Y. (2016) Bounds on the Matching Energy of Unicyclic Odd-Cycle Graphs. MATCH Communications in Mathematical and in Computer Chemistry, 75, 315-330.

  38. 38. Ji, S., Li, X. and Shi, Y. (2013) Extremal Matching Energy of Bicyclic Graphs. MATCH Communications in Mathematical and in Computer Chemistry, 70, 697-706.

  39. 39. Liu, X., Wang, L. and Xiao, P. (2018) Ordering of Bicyclic Graphs by Matching Energy. MATCH Communications in Mathematical and in Computer Chemistry, 79, 341-365.

  40. 40. Chen, L. and Shi, Y. (2015) The Maximal Matching Energy of Tricyclic Graphs. MATCH Communications in Mathematical and in Computer Chemistry, 73, 105-119.

  41. 41. Ji, S. and Ma, H. (2014) The Extremal Matching Energy of Graphs. Ars Combinatoria, 115, 343-355.

  42. 42. Li, S. and Yan, W. (2014) The Matching Energy of Graphs with Given Parameters. Discrete Applied Mathematics, 162, 415-420. https://doi.org/10.1016/j.dam.2013.09.014

  43. 43. Li, H., Zhou, Y. and Su, L. (2014) Graphs with Extremal Matching Energies and Prescribed Paramaters. MATCH Communications in Mathematical and in Computer Chemistry, 72, 239-248.

  44. 44. Wang, W. and So, W. (2015) On Minimum Matching Energy of Graphs. MATCH Communications in Mathematical and in Computer Chemistry, 74, 399-410.

  45. 45. Xu, K., Das, K.C. and Zheng, Z. (2015) The Minimal Matching Energy of -Graphs with a Given Matching Number. MATCH Communications in Mathematical and in Computer Chemistry, 73, 93-104.

  46. 46. Chen, L., Liu, J. and Shi, Y. (2015) Matching Energy of Unicyclic and Bicyclic Graphs with a Given Diameter. Complexity, 21, 224-238. https://doi.org/10.1002/cplx.21599

  47. 47. Zou, L. and Li, H. (2016) The Minimum Matching Energy of Bicyclic Graphs with Given Girth. Rocky Mountain Journal of Mathematics, 46, 1275-1291. https://doi.org/10.1216/RMJ-2016-46-4-1275

  48. 48. Shang, Y.L. (2015) The Estrada Index of Evolving Graphs. Applied Mathematics and Computation, 250, 415-423. https://doi.org/10.1016/j.amc.2014.10.129

  49. 49. Shang, Y.L. (2015) Laplacian Estrada and Normalized Laplacian Estrada Indices of Evolving Graphs. PLoS ONE, 10, e0123426. https://doi.org/10.1371/journal.pone.0123426