J Appl Math Comput DOI 10.1007/s12190-013-0714-9

JAMC

O R I G I NA L R E S E A R C H

Some relations on the ordering of trees by minimal energies between subclasses of trees Hongping Ma

Received: 12 March 2013 © Korean Society for Computational and Applied Mathematics 2013

Abstract The energy of a graph is defined as the sum of the absolute values of all eigenvalues of the graph. A tree is said to be non-starlike if it has at least two vertices with degree more than 2. A caterpillar is a tree in which a removal of all pendent vertices makes a path. Let Tn,d , Tn,p be the set of all trees of order n with diameter d, p pendent vertices respectively. In this paper, we investigate the relations on the ordering of trees and non-starlike trees by minimal energies between Tn,d and Tn,n−d+1 . We first show that the first two trees (non-starlike trees, resp.) with minimal energies in Tn,d and Tn,n−d+1 are the same for 3 ≤ d ≤ n − 2 (3 ≤ d ≤ n − 3, resp.). Then we obtain that the trees with third-minimal energy in Tn,d and Tn,n−d+1 are the same when n ≥ 11, 3 ≤ d ≤ n − 2 and d = 8; and the tree with third-minimal energy in Tn,8 is the caterpillar with third-minimal energy in Tn,n−7 for n ≥ 11. Keywords Minimal energy · Characteristic polynomial · Tree · Pendent vertex · Diameter Mathematics Subject Classification (2000) 15A18 · 05C50 · 05C90 · 92E10

1 Introduction Let G be a simple graph with n vertices and A(G) the adjacency matrix of G. The characteristic polynomial φ(G, x) = det(xI − A(G)) of A(G) is called the characteristic polynomial of G. The roots λ1 , λ2 , . . . , λn of φ(G, x) = 0 are called the

Project supported by the National Natural Science Foundation of China (Grant Nos. 11101351 and 11171288) and the NSF of the Jiangsu Higher Education Institutions (Grant No. 11KJB110014).

B

H. Ma ( ) School of Mathematics and Statistics, Jiangsu Normal University, Xuzhou 221116, China e-mail: [email protected]

H. Ma

eigenvalues of G. The energy of G is defined as E = E(G) =

n 

|λi |.

i=1

This concept was intensively studied in chemistry, since it can be used to approximate the total π -electron energy of a molecular. For further details on the mathematical properties and chemical applications of E(G) see [7, 18]. Let G be an acyclic graph on n vertices. Then E(G) can be expressed as the Coulson integral formula [4] 2 E(G) = π



+∞

0

   n2   1 2k ln 1 + m(G, k)x dx, x2

(1)

k=1

where m(G, k) denotes the number of k-matchings in G. This formula led Gutman [3] to introduce a quasi-order relation over the set of all acyclic graphs on n vertices: if G1 and G2 are two acyclic graphs, then G1  G2

⇔

m(G1 , k) ≥ m(G2 , k)

for all k = 1, . . . ,

  n . 2

If G1  G2 and there exists some i such that m(G1 , i) > m(G2 , i), then we write G1 G2 . For acyclic graphs G1 and G2 , G1 G2

⇒

E(G1 ) > E(G2 ).

Gutman [3] determined the n-vertex trees with minimal, second-minimal, thirdminimal, and fourth-minimal energies, as well as the n-vertex trees with maximal and second-maximal energies. Recently, these results were extended in [1, 6, 12, 21, 23, 24, 27]. Minimal or maximal energies have been determined for various subclasses of trees, see [2, 3, 8–11, 13–17, 19, 20, 25, 26, 28–37]. Let Tn,d be the set of all trees with n vertices and diameter d, where 2 ≤ d ≤ n − 1. Obviously, T ∈ Tn,2 is a star Sn , while T ∈ Tn,n−1 is a path Pn . Let P = v0 v1 · · · vk (k ≥ 1) be a path of a tree T . If dT (v0 ) ≥ 3, dT (vk ) = 1 and dT (vi ) = 2 for i = 1, . . . , k − 1, we call P a pendent path of T with root v0 and particularly when k = 1, we call P a pendent edge. A caterpillar is a tree in which a removal of all pendent vertices makes a path. Let T (n, d; n1 , n2 , . . . , nd−1 ) ∈ Tn,d be a caterpillar obtained from a path v0 v1 · · · vd by adding ni (ni ≥ 0) pendent edges to vi (i = 1, . . . , d − 1). Obviously, T (n, d; n1 , n2 , . . . , nd−1 ) has n − d + 1 pendent vertices. For 1 ≤ i ≤ d − 1, denote Tn,d,i = T (n, d; 0, . . . , 0, ni = n − d − 1, 0, . . . , 0). The trees with minimal and second-minimal energies in Tn,d have been considered by [12, 13, 21, 27, 28, 36]. Lemma 1.1 [28] Tn,d,1 is the unique tree with minimal energy in Tn,d .

Some relations on the ordering of trees by minimal energies

Lemma 1.2 (1) [36] T (n, 3; n − 5, 1) is the unique tree with second-minimal energy in Tn,3 for n ≥ 6. (2) [12, 21, 27] T (n, 4; n − 6, 0, 1) is the unique tree with second-minimal energy in Tn,4 for n ≥ 7. (3) T (n, 5; n − 7, 0, 0, 1) if n = 8 [36], Tn,5,2 if n ≥ 9 [13, 27] is the unique tree with second-minimal energy in Tn,5 . For the tree with second-minimal energy in Tn,d , Zhou and Li also gave the following result (Theorem 1 in [36]): (∗) Let T ∈ Tn,d with 6 ≤ d ≤ n − 2. If T = Tn,d,1 , Tn,d,3 , then T Tn,d,3 . In Sect. 4, we will show that the trees T (n, d; n − d − 2, 0, . . . , 0, 1) and Tn,d,3 are quasi-order incomparable when d is odd with 6 ≤ d ≤ n − 3 or when d is even with  2n 3  + 1 ≤ d ≤ n − 3 (see Theorem 4.6). Let Tn,p be the set of all trees of order n with p pendent vertices, where 2 ≤ p ≤ n − 1. The tree with minimal energy in Tn,p has been determined by [33] and [32] independently. Lemma 1.3 [32, 33] Tn,n−p+1,1 is the unique tree with minimal energy in Tn,p . Let l(T ) be the number of vertices of degree greater than two in a tree T . A tree T is said to be starlike if l(T ) ≤ 1 and non-starlike if l(T ) ≥ 2. Obviously, the number of pendent vertices in a non-starlike tree with n vertices is at least 4 and at most n − 2. Let  Tn,k be the class of non-starlike trees of order n with k pendent vertices, where 4 ≤ k ≤ n − 2. Zhang and Zhou [35] characterized the trees with minimal and second-minimal energies in  Tn,k . Lemma 1.4 [35] (1) If n ≥ 6 and 4 ≤ k ≤ n − 2, then T (n, n − k + 1; k − 3, 0, . . . , 0, 1) is the unique tree with minimal energy in  Tn,k . (2) T (n, 3; n − 6, 2) is the unique tree with second-minimal energy in  Tn,n−2 for n ≥ 8. (3) T (n, 4; n − 6, 1, 0) if n = 8, T (n, 4; n − 7, 0, 2) if n ≥ 9 is the unique tree with second-minimal energy in  Tn,n−3 . (4) If n ≥ 8 and 4 ≤ k ≤ n − 4, then T (n, n − k + 1; k − 3, 0, 1, 0, . . . , 0) is the unique tree with second-minimal energy in  Tn,k . Obviously, for a non-starlike tree T of order n, the diameter of T is at least 3 and at most n − 3. Let Tn,s be the set of all non-starlike trees of order n with diameter s, where 3 ≤ s ≤ n − 3. Notice that if T ∈ Tn,d ∩ Tn,n−d+1 , then T must be a caterpillar. By Lemmas 1.1 and 1.3, we see that the tree with minimal energy in Tn,d is exactly the tree with minimal energy in Tn,n−d+1 . In this paper, we investigate the further relations on the ordering of trees by minimal energies between Tn,d and Tn,n−d+1 , and Tn,s and  Tn,n−s+1 respectively.

H. Ma Fig. 1 The tree considered in Lemma 2.3

The rest of this paper is organized as follows. In Sect. 2, we give some preliminary results. In Sect. 3, we prove that the first two trees with minimal energies in Tn,s and  Tn,n−s+1 are the same. In Sect. 4, we obtain that the trees with second-minimal energy in Tn,d and Tn,n−d+1 are also the same for 3 ≤ d ≤ n − 2. In Sect. 5, we show that the trees with third-minimal energy in Tn,d and Tn,n−d+1 are the same when n ≥ 11, 3 ≤ d ≤ n − 2 and d = 8; and the tree with third-minimal energy in Tn,8 is the caterpillar with third-minimal energy in Tn,n−7 for n ≥ 11.

2 Preliminaries In this section, we introduce some notations and properties which we need to use in the next sections. Lemma 2.1 [4] Let T be a tree, and let uv be an edge of T . Then m(T , k) = m(T − uv, k) + m(T − u − v, k − 1). Lemma 2.2 [4] Let T be a forest of order n. Then the characteristic polynomial of T can be written as 2  φ(T , x) = (−1)k m(T , k)x n−2k , n

k=0

where m(T , 0) = 1. Lemma 2.3 [5] Let Xn,i be the graph whose structure is depicted in Fig. 1, where the fragment X is an arbitrary tree. Then Xn,1 Xn,3 · · · Xn, n2   Xn, n2  · · · Xn,4 Xn,2 . Lemma 2.4 [3] Let T be a tree on n vertices. If T is different from the path Pn and the star Sn , then Pn T Sn . Lemma 2.5 [3] For integer i = 1, n − 1, Pn Pi ∪ Pn−i P1 ∪ Pn−1 . Suppose T ∈ Tn,d (3 ≤ d ≤ n − 2). Let P = v0 v1 · · · vd be a diametrical path in T , and C = {T1 , . . . , Tc } be the set of connected components of T − {v0 , . . . , vd }. If vi ∈ V (P ) (1 ≤ i ≤ d − 1), then NT (vi ) = {vi−1 , vi+1 , w1 , . . . , wm }, where wj ∈ V (Tij ), j = 1, . . . , m (see Fig. 2). Choose a Tij ∈ C such that |V (Tij )| = nj > 1, if T  is

Some relations on the ordering of trees by minimal energies Fig. 2 The trees T and T  in Operation I

Fig. 3 The trees T and T  in Operation II

obtained from T by replacing Tij ∪ vi wj with nj pendent edges ui1 vi , . . . , uinj vi , we say that T  is obtained from T by Operation I. It is easy to see that T  ∈ Tn,d . Lemma 2.6 [13] If T  is obtained from T by Operation I, then T T  . Let T be a tree of the form in Fig. 3, where T1 and T2 are subtrees of T with at least two vertices, u ∈ V (T2 ), v ∈ V (T1 ) and s ≥ 3. If T  is obtained from T by replacing Ps with a pendent edge and replacing the edge uv with a path Ps , we say that T  is obtained from T by Operation II. Let p(T ) be the number of pendent paths in T with length more than 1. It is easy to see that T  ∈ Tn,p and p(T  ) = p(T ) − 1. Lemma 2.7 [33] If T  is obtained from T by Operation II, then T T  . Let u be a vertex of a graph G, and T be a rooted tree. Let Gu (T ) denote the graph obtained by attaching T to G such that the root of T is at u. When T is a star Sk+1 with the center as its root, then we simply write Gu (T ) as G∗u (k). Lemma 2.8 [22] Let u be a vertex of a tree G and T be a rooted tree of order k + 1. If Gu (T ) = G∗u (k), then Gu (T ) G∗u (k).

H. Ma Fig. 4 The starlike tree Sn,p (n1 , n2 , . . . , nr )

Lemma 2.9 E(T (n, 4; n − 7, 0, 2)) < E(Tn,4,2 ) for n ≥ 9. Proof Denote Tn1 = T (n, 4; n − 7, 0, 2) and Tn2 = Tn,4,2 . By Lemma 2.1, we have that m(Tn1 , 1) = m(Tn2 , 1) = n − 1, m(Tn1 , 2) = 4n − 21 and m(Tn1 , k) = 0 for k ≥ 3; m(Tn2 , 2) = 2n − 7, m(Tn2 , 3) = n − 5 and m(Tn2 , k) = 0 for k ≥ 4. Thus by Lemma 2.2, 

φ Tn1 , x = x n−4 x 4 − (n − 1)x 2 + (4n − 21) ,

 φ Tn2 , x = x n−6 (x + 1)(x − 1) x 4 − (n − 2)x 2 + (n − 5) . √ √ √ √ Let a1 , a2 be the positive eigenvalues of Tn1 , and b1 = 1, b2 = 1 be the positive eigenvalues of Tn2 . Then a1 + a2 = n − 1, a1 a2 = 4n − 21, b1 + b2 = n − 2 and b1 b2 = n − 5. We have

E(Tn1 ) 2 E(Tn2 ) 2

2

√ √ √ √ = ( a1 + a2 )2 = a1 + a2 + 2 a1 a2 = n − 1 + 2 4n − 21,

2 = (1 +



b1 +







 b2 ) = 1 + b1 + b2 + 2 b1 b2 + 2 b1 + b2 + 2 b1 b2 2

 √ √ = n − 1 + 2 n − 5 + 2 n − 2 + 2 n − 5.

 √ √ √ √ 9, we have that n√ −5+ n−2+2 n−  Since n ≥√ √5 ≥ n − 5 + n +12 = 2n − 3 + 2 (n − 5)(n + 2) > 2n − 3 + 2(n − 9) = 4n − 21. Thus E(Tn ) < E(Tn2 ).  Let T be a starlike tree in Tn,p . Then T is of form as shown in Fig. 4, where n1 ≥ 1, . . . , nr ≥ 1 and n1 + · · · + nr = n − p − 1. Lemma 2.10 E(T (n, 5; n − 7, 0, 0, 1)) < E(Sn,n−4 (1, 1, 1)) for n ≥ 8. Proof Denote Tn1 = T (n, 5; n − 7, 0, 0, 1) and Tn2 = Sn,n−4 (1, 1, 1). By Table 1, we obtain that E(Tn1 ) < E(Tn2 ) for 8 ≤ n ≤ 34. In the following we assume that n ≥ 35. By Lemma 2.1, we have that m(Tn1 , 1) = m(Tn2 , 1) = n − 1, m(Tn1 , 2) = 4n − 19, m(Tn1 , 3) = 2(n − 6) and m(Tn1 , k) = 0 for k ≥ 4; m(Tn2 , 2) = 3n − 12, m(Tn2 , 3) = 3n − 17, m(Tn2 , 4) = n − 7 and m(Tn2 , k) = 0 for k ≥ 5. Thus by Lemma 2.2,

Some relations on the ordering of trees by minimal energies Table 1 The (approximate values of) energies of trees considered in Lemma 2.10 n

E(Tn1 )

E(Tn2 )

n

E(Tn1 )

E(Tn2 )

n

E(Tn1 )

E(Tn2 )

8

8.47214

9.29150

17

12.09372

13.01655

26

14.35509

15.26371

9

9.05997

9.94253

18

12.38091

13.30231

27

14.57230

15.47942

10

9.56314

10.46965

19

12.65682

13.57668

28

14.78453

15.69019

11

10.01083

10.92820

20

12.92271

13.84096

29

14.99212

15.89636

12

10.41839

11.34088

21

13.17959

14.09620

30

15.19535

16.09821

13

10.79515

11.71984

22

13.42833

14.34330

31

15.39449

16.29601

14

11.14726

12.07255

23

13.66967

14.58301

32

15.58978

16.49000

15

11.47905

12.40401

24

13.90422

14.81595

33

15.78144

16.68038

16

11.79373

12.71780

25

14.13253

15.04270

34

15.96966

16.86737



φ Tn1 , x = x n−6 x 6 − (n − 1)x 4 + (4n − 19)x 2 − 2(n − 6) , 

φ Tn2 , x = x n−8 (x + 1)2 (x − 1)2 x 4 − (n − 3)x 2 + (n − 7) . √ √ √ √ √ Let a1 , a2 , a3 be the positive eigenvalues of Tn1 , and b1 = 1, b2 = 1 be the positive eigenvalues of Tn2 . Then a1 + a2 + a3 = n − 1, a1 a2 + a1 a3 + a2 a3 = 4n − 19, a1 a2 a3 = 2(n − 6), b1 + b2 = n − 3 and b1 b2 = n − 7. We have

 √ √ √ E(Tn1 ) 2 = ( a1 + a2 + a3 )2 2 = a1 + a2 + a3  √ √ √ √ + 2 a1 a2 + a2 a3 + a3 a1 + 2 a1 a2 a3 ( a1 + a2 + a3 )  √ √ √ √ √ = n − 1 + 2 4n − 19 + 2 2 n − 6( a1 + a2 + a3 ),

      E(Tn2 ) 2 = (2 + b1 + b2 )2 = 4 + b1 + b2 + 2 b1 b2 + 4 b1 + b2 + 2 b1 b2 2  √ √ = n + 1 + 2 n − 7 + 4 n − 3 + 2 n − 7. Let f (x) = x 3 − (n − 1)x 2 + (4n − 19)x − 2(n − 6). Then a1 , a2 and a3 are three roots of f (x) = 0. Suppose that a1 < a2 < a3 . Since n ≥ 35, we have that f ( 12 ) = 5 7 389 13 7 311 7 1 5 − 14 n+ 23 8 < 0, f ( 8 ) = 64 n+ 512 > 0, f ( 4 ) = 16 n− 64 > 0, f ( 2 ) = − 4 n+ 8 < 0, 1 5 13 7 and f (n) > 0. Hence 2 < a1 < 8 , 4 < a2 < 2 , and a3 = n − 1 − a1 − a2 < n − 19 4 . Therefore   

   √ √ E(Tn1 ) 2 5 7 19 + + n− < n − 1 + 2 4n − 19 + 2 2 n − 6 2 8 2 4       √ √ √ √ 19  = n − 1 + 2 4n − 19 + ( 5 + 2 7) n − 6 + 2 2 (n − 6) n − 4

H. Ma Table 2 The (approximate values of) energies of trees considered in Lemma 2.11 n

E(Tn1 )

E(Tn2 )

n

E(Tn1 )

E(Tn2 )

n

E(Tn1 )

E(Tn2 )

9

9.46410

10.09431

14

11.74548

12.30409

19

13.32284

13.84480

10

10.03405

10.64531

15

12.09513

12.64467

20

13.59782

14.11440

21

13.86290

14.37454

11

10.52734

11.12217

16

12.42498

12.96649

12

10.96873

11.54962

17

12.73808

13.27240

13

11.37193

11.94088

18

13.03675

13.56460

 √ √ ≤ n − 1 + 2 4n − 19 + 57 n − 6 + 3(n − 5)  √ √ = n − 1 + 2 7n − 34 + 57 n − 6 √ ≤ n−1+6 n−7 

 √ √ E(Tn2 ) 2 ,
 φ Tn1 , x = x n−6 x 6 − (n − 1)x 4 + (5n − 26)x 2 − (5n − 33) , 

φ Tn2 , x = x n−8 x 8 − (n − 1)x 6 + (4n − 18)x 4 − (4n − 24)x 2 + (n − 7) . Let a1, a2 , a3 bethethree rootsoff (x) = x 3 − (n −1)x 2 + (5n −26)x − (5n −33) = 0, and b1 , b2 , b3 , b4 be the four roots of g(x) = x 4 − (n − 1)x 3 + (4n − 18)x 2 − (4n − 24)x + n − 7 = 0. Then a1 + a2 + a3 = b1 + b2 + b3 + b4 = n − 1. Suppose that a1 < a2 < a3 and b1 < b2 < b3 < b4 . Since n ≥ 22, we have that f ( 54 ) = 5 3 1 3 7 1 23 29 1 243 − 16 n+ 257 64 < 0, f ( 2 ) = 4 n− 8 > 0, f ( 2 ) = 4 n− 8 > 0, f ( 8 ) = − 64 n− 512 < 0, 11 1869 862319 7 279 11473 and f (n) > 0; g( 32 ) = 32768 n − 1048576 > 0, g( 16 ) = − 4096 n + 65536 < 0, g( 15 16 ) = 239 83633 5 3 77 21 13 10087 − 4096 n + 65536 < 0, g(1) = 1, g( 2 ) = 8 n − 16 > 0, g( 8 ) = − 512 n − 4096 < 0, 23 and g(n) > 0. Hence 54 < a1 < 32 , 72 < a2 < 29 8 , a3 = n − 1 − a1 − a2 < n − 4 ; 7 15 5 21 81 and 11 32 < b1 < 16 , 16 < b2 < 1, 2 < b3 < 8 , b4 = n − 1 − b1 − b2 − b3 > n − 16 .

Some relations on the ordering of trees by minimal energies Table 3 The (approximate values of) energies of trees considered in Lemma 2.12 n

E(Tn1 )

E(Tn2 )

E(Tn3 )

n

E(Tn1 )

E(Tn2 )

E(Tn3 )

10

10.98792

11.12791

11.01570

14

12.92570

12.94887

12.80886

11

11.57194

11.66693

11.54275

15

13.30169

13.30995

13.16721

12

12.07292

12.13722

12.00574

16

13.65321

13.64892

13

12.51916

12.56049

12.42407

Therefore          2

11 15 5 81 + + + n− E Tn = 2( b1 + b2 + b3 + b4 ) > 2 32 16 2 16    

√ √ √ 3 29 23 + + n− > 2( a1 + a2 + a3 ) = E Tn1 . >2 2 8 4 The proof is thus complete.



Lemma 2.12 E(T (n, 7; n − 9, 0, 0, 0, 0, 1)) < E(Tn,7,3 ) for n = 10; E(Tn,7,3 ) < E(T (n, 7; n − 9, 0, 0, 0, 0, 1)) < E(Tn,7,2 ) for 11 ≤ n ≤ 15; E(T (n, 7; n − 9, 0, 0, 0, 0, 1)) > E(Tn,7,2 ) for n ≥ 16. Proof Denote Tn1 = T (n, 7; n − 9, 0, 0, 0, 0, 1), Tn2 = Tn,7,2 and Tn3 = Tn,7,3 . By Lemma 2.1, we get that m(Tn1 , 1) = m(Tn2 , 1) = n − 1, m(Tn1 , 2) = 6n − 34, m(Tn1 , 3) = 9n − 65, m(Tn1 , 4) = 2(n − 8) and m(Tn1 , k) = 0 for k ≥ 5; m(Tn2 , 2) = 5(n − 5), m(Tn2 , 3) = 7n − 46, m(Tn2 , 4) = 3n − 23 and m(Tn2 , k) = 0 for k ≥ 5. By equality (1), we obtain that



E Tn1 − E Tn2  2 +∞ dx 1 + (n − 1)x 2 + (6n − 34)x 4 + (9n − 65)x 6 + 2(n − 8)x 8 ln . = π 0 x 2 1 + (n − 1)x 2 + 5(n − 5)x 4 + (7n − 46)x 6 + (3n − 23)x 8 For a fixed x > 0, let f (y) =

1 + (y − 1)x 2 + (6y − 34)x 4 + (9y − 65)x 6 + 2(y − 8)x 8 . 1 + (y − 1)x 2 + 5(y − 5)x 4 + (7y − 46)x 6 + (3y − 23)x 8

Then we have that f  (y) =

x 4 + 10x 6 + 36x 8 + 56x 10 + 35x 12 + 8x 14 + 2x 16 > 0. [1 + (y − 1)x 2 + 5(y − 5)x 4 + (7y − 46)x 6 + (3y − 23)x 8 ]2

So f (n) is a strictly increase function of n. Therefore, for all n ≥ 16, we have that 1 ) − E(T 2 ) > 0. The result thus follows by Table 3.  E(Tn1 ) − E(Tn2 ) ≥ E(T16 16 Lemma 2.13 E(T (n, 8; n − 10, 0, 0, 0, 0, 0, 1)) < E(Tn,8,4 ) for n ≥ 11.

H. Ma Table 4 The (approximate values of) energies of trees considered in Lemma 2.13 n

E(Tn1 )

E(Tn2 )

n

E(Tn1 )

E(Tn2 )

n

E(Tn1 )

E(Tn2 )

11

12.05468

12.59207

16

14.34695

14.78720

21

15.92658

16.32405

12

12.62923

13.13746

17

14.69726

15.12670

22

16.20181

16.59319

13

13.12512

13.61084

18

15.02764

15.44764

23

16.46711

16.85292

14

13.56819

14.03587

19

15.34116

15.75281

15

13.97255

14.42536

20

15.64019

16.04438

Proof Denote Tn1 = T (n, 8; n − 10, 0, 0, 0, 0, 0, 1) and Tn2 = Tn,8,4 . By Table 4, we obtain that E(Tn1 ) < E(Tn2 ) for 11 ≤ n ≤ 23. In the following we assume that n ≥ 24. By Lemma 2.1, we have that m(Tn1 , 1) = m(Tn2 , 1) = n − 1, m(Tn1 , 2) = 7n − 43, m(Tn1 , 3) = 14n − 110, m(Tn1 , 4) = 7n − 61 and m(Tn1 , k) = 0 for k ≥ 5; m(Tn2 , 2) = 6n − 33, m(Tn2 , 3) = 11n − 79, m(Tn2 , 4) = 6n − 49, m(Tn2 , 5) = n − 9, and m(Tn2 , k) = 0 for k ≥ 6. Thus by Lemma 2.2,

 φ Tn1 , x = x n−8 x 8 − (n − 1)x 6 + (7n − 43)x 4 − (14n − 110)x 2 + (7n − 61) ,



φ Tn2 , x = x n−10 x 2 − x − 1 x 2 + x − 1  × x 6 − (n − 4)x 4 + (3n − 22)x 2 − (n − 9) . Let a1 , a2 , a3 , a4 be the four roots of f (x) = x 4 − (n − 1)x 3 + (7n − 43)x 2 − (14n − 110)x + (7n − 61) = 0, and b1 , b2 , b3 be the three roots of g(x) = x 3 − (n − 4)x 2 + (3n − 22)x − (n − 9) = 0. Then a1 + a2 + a3 + a4 = n − 1, b1 + b2 + b3 = n − 4. Suppose that a1 < a2 < a3 < a4 and b1 < b2 < b3 < b3 . Since n ≥ 24, we have 35431 25 4649 480511 19 83 that f ( 58 ) = 379 512 n − 4096 > 0, f ( 32 ) = − 32768 n − 1048576 < 0, f ( 8 ) = − 512 n + 11945 79 1777 714401 121 2743 1444735 487 4096 < 0, f ( 32 ) = 32768 n + 1048576 > 0, f ( 32 ) = 32768 n − 1048576 > 0, f ( 128 ) = 23927 85235359 11 89 63923 49 )= − 2097152 n − 268435456 < 0, and f (n) > 0; g( 32 ) = − 1024 n + 32768 < 0, g( 128 31 2559377 161 895 1339679 21 1 1587 n + > 0, g( ) = n − > 0, g( ) = − n − < 0, and 16384 2097152 64 4096 262144 8 64 512 19 79 121 487 , < a < , < a < , a = n − 1 − a1 − a2 − g(n) > 0. Hence 58 < a1 < 25 2 3 4 32 8 32 32 128 11 49 161 21 897 ; and < b < , < b < , b = n − 4 − b − b a3 < n − 249 1 2 3 1 2 > n − 128 . 32 32 128 64 8 Therefore      1

√ √ √ √ 25 79 487 249 + + + n− E Tn = 2( a1 + a2 + a3 + a4 ) < 2 32 32 128 32         √ √ 11 161 897 + + n− < 2( 5 + b1 + b2 + b3 ) 5+ <2 32 64 128 2

= E Tn . The proof is thus complete.



Lemma 2.14 E(T (n, 8; n − 10, 0, 0, 0, 0, 0, 1)) < E(Sn,n−7 (2, 2, 2)) for 11 ≤ n ≤ 13; E(T (n, 8; n − 10, 0, 0, 0, 0, 0, 1)) > E(Sn,n−7 (2, 2, 2)) for n ≥ 14.

Some relations on the ordering of trees by minimal energies

Proof Denote Tn1 = T (n, 8; n − 10, 0, 0, 0, 0, 0, 1) and Tn2 = Sn,n−7 (2, 2, 2). By . . . 1)= 2)= 1)= direct computing, we have that E(T11 12.05468, E(T11 12.12899, E(T12 . . . . 2)= 1)= 2)= 1)= 12.66870, E(T13 13.12512, E(T13 13.14017, E(T14 12.62923, E(T12 . 2) = 13.56819 and E(T14 13.56464. By Lemma 2.1, we get that m(Tn1 , 1) = 2 1 m(Tn , 1) = n − 1, m(Tn , 2) = 7n − 43, m(Tn1 , 3) = 14n − 110, m(Tn1 , 4) = 7n − 61 and m(Tn1 , k) = 0 for k ≥ 5; m(Tn2 , 2) = 6n − 33, m(Tn2 , 3) = 12n − 88, m(Tn2 , 4) = 8n − 68 and m(Tn2 , k) = 0 for k ≥ 5. Hence by equality (1),



E Tn1 − E Tn2  2 +∞ dx 1 + (n − 1)x 2 + (7n − 43)x 4 + (14n − 110)x 6 + (7n − 61)x 8 ln . = π 0 x2 1 + (n − 1)x 2 + (6n − 33)x 4 + (12n − 88)x 6 + (8n − 68)x 8 For a fixed x > 0, let f (y) =

1 + (y − 1)x 2 + (7y − 43)x 4 + (14y − 110)x 6 + (7y − 61)x 8 . 1 + (y − 1)x 2 + (6y − 33)x 4 + (12y − 88)x 6 + (8y − 68)x 8

Then we have that f  (y) =

x 4 (2x 2 +1)2 (3x 8 +8x 6 +14x 4 +7x 2 +1) [1+(y−1)x 2 +(6y−33)x 4 +(12y−88)x 6 +(8y−68)x 8 ]2

> 0. So

f (n) is a strictly increase function of n. Therefore, for all n ≥ 14, we have that 1 ) − E(T 2 ) > 0. The result thus follows. E(Tn1 ) − E(Tn2 ) ≥ E(T14  14 . . By computing, we have E(S10,3 (2, 2, 2)) = 11.47548 and E(T10,8,4 ) = 11.91801. Hence combining (the proofs of) Lemmas 2.13 and 2.14, we have the following result. Corollary 2.15 E(Sn,n−7 (2, 2, 2)) < E(Tn,8,4 ) for n ≥ 10. Lemma 2.16 E(T (n, 9; n − 11, 0, 0, 0, 0, 0, 0, 1)) < E(Tn,9,3 ) for n = 12; E(Tn,9,3 ) < E(T (n, 9; n − 11, 0, 0, 0, 0, 0, 0, 1)) < E(Tn,9,4 ) for 13 ≤ n ≤ 15; E(T (n, 9; n − 11, 0, 0, 0, 0, 0, 0, 1)) > E(Tn,9,4 ) for n ≥ 16. Proof Denote Tn1 = T (n, 9; n − 11, 0, 0, 0, 0, 0, 0, 1), Tn2 = Tn,9,4 and Tn3 = Tn,9,3 . By Lemma 2.1, we get that m(Tn1 , 1) = m(Tn2 , 1) = n − 1, m(Tn1 , 2) = 8n − 53, m(Tn1 , 3) = 20n−170, m(Tn1 , 4) = 16n−151, m(Tn1 , 5) = 2(n−10) and m(Tn1 , k) = 0 for k ≥ 6; m(Tn2 , 2) = 7(n − 6), m(Tn2 , 3) = 16n − 125, m(Tn2 , 4) = 13n − 115, m(Tn2 , 5) = 3n − 29 and m(Tn2 , k) = 0 for k ≥ 6. Hence by equality (1),



E Tn1 − E Tn2  2 +∞ dx = π 0 x2 × ln

1 + (n − 1)x 2 + (8n − 53)x 4 + (20n − 170)x 6 + (16n − 151)x 8 + 2(n − 10)x 10 . 1 + (n − 1)x 2 + 7(n − 6)x 4 + (16n − 125)x 6 + (13n − 115)x 8 + (3n − 29)x 10

H. Ma Table 5 The (approximate values of) energies of trees considered in Lemma 2.16 n

E(Tn1 )

E(Tn2 )

E(Tn3 )

n

E(Tn1 )

E(Tn2 )

E(Tn3 )

12

13.51754

13.62490

13.53847

15

15.04588

15.04657

14.94349

13

14.10005

14.15867

14.06387

16

15.45205

15.43322

14

14.60018

14.62562

14.52585

For a fixed x > 0, let f (y) =

1 + (y −1)x 2 + (8y −53)x 4 + (20y −170)x 6 + (16y −151)x 8 + 2(y −10)x 10 . 1 + (y −1)x 2 + 7(y −6)x 4 + (16y −125)x 6 + (13y −115)x 8 + (3y −29)x 10

Then we have that f  (y) =

x 4 (2x 2 +1)(x 14 +9x 12 +5710 +126x 8 +120x 6 +55x 4 +12x 2 +1) [1+(y−1)x 2 +7(y−6)x 4 +(16y−125)x 6 +(13y−115)x 8 +(3y−29)x 10 ]2

> 0. So f (n) is a strictly increase function of n. Therefore, for all n ≥ 16, we have 1 ) − E(T 2 ) > 0. The result thus follows by Table 5.  that E(Tn1 ) − E(Tn2 ) ≥ E(T16 16 Lemma 2.17 T (n, n − p + 1; p − 3, 0, 1, 0, . . . , 0) Tn,n−p+1,3 for 4 ≤ p ≤ n − 4. Proof Denote Tn1 = T (n, n − p + 1; p − 3, 0, 1, 0, . . . , 0) and Tn2 = Tn,n−p+1,3 . By Lemma 2.1, we have

m Tn1 , k = m(Tn−1,p−1,1 , k) + m(Sp ∪ Pn−p−2 , k − 1) = m(Pn−p+2 , k) + (p − 3)m(Pn−p , k − 1) + m(Pn−p−2 , k − 1) + (p − 1)m(Pn−p−2 , k − 2), 2

m Tn , k = m(Pn−p+2 , k) + (p − 2)m(P3 ∪ Pn−p−2 , k − 1) = m(Pn−p+2 , k) + (p − 2)m(Pn−p−2 , k − 1) + 2(p − 2)m(Pn−p−2 , k − 2), and m(Pn , k) = m(Pn−1 , k) + m(Pn−2 , k − 1).

(2)

Therefore we have



m Tn1 , k − m Tn2 , k = (p − 3)m(Pn−p−3 , k − 2) ≥ 0 and m(Tn1 , 2) − m(Tn2 , 2) = p − 3 > 0. The result thus follows.



Lemma 2.18 Sn,n−5 (1, 1, 2) T (n, 5; n − 7, 0, 0, 1) for n ≥ 9. Proof Denote Tn1 = Sn,n−5 (1, 1, 2) and Tn2 = T (n, 5; n − 7, 0, 0, 1). It is easy to obtain that m(Tn1 , 1) = m(Tn2 , 1) = n − 1, m(Tn1 , 2) = 4n − 18, m(Tn1 , 3) = 5n − 31, m(Tn1 , 4) = 2n − 15 and m(Tn1 , k) = 0 for k ≥ 5; m(Tn2 , 2) = 4n − 19, m(Tn2 , 3) = 2n − 12 and m(Tn2 , k) = 0 for k ≥ 4. The proof is thus complete. 

Some relations on the ordering of trees by minimal energies Fig. 5 The tree T considered in Lemma 3.1

n,s 3 The trees with minimal and second-minimal energies in T In this section, we shall determine the trees with minimal and second-minimal energies in Tn,s (3 ≤ s ≤ n − 3). Lemma 3.1 Let T be a tree of the form in Fig. 5. Suppose that l ≥ 0, 3 ≤ i ≤ s − 3 and n − s − l ≥ 3. Then T T (n, s; n − s − 2, 0, 1, 0, . . . , 0). Proof For convenience, let T 0 = T (n, s; n − s − 2, 0, 1, 0, . . . , 0), v0 v1 · · · vs be a longest path in T 0, NT 0 (v1 ) = {v0 , v2 , x1 ,. . . , xn−s−2 }andNT 0 (v3 ) = {v2 , v4 , xn−s−1 }. We prove that T T 0 by induction on l. First suppose that l = 0. Denote y = n − s − 2, then y ≥ 1. We proceed by induction on y. Suppose y = 1. Then by Lemma 2.1, we have m(T , k) = m(T − x1 w1 , k) + m(T − x1 − w1 , k − 1) = m(P1 ∪ Ts+2,s,i , k) + m(Ps+1 , k − 1), and





m T 0 , k = m T 0 − x1 v 1 , k + m T 0 − x1 − v 1 , k − 1 = m(P1 ∪ Ts+2,s,3 , k) + m(P1 ∪ Ts,s−2,1 , k − 1). So we have Ts+2,s,i  Ts+2,s,3 by Lemma 2.3 and Ps+1 P1 ∪ Ps P1 ∪ Ts,s−2,1 by Lemmas 2.4 and 2.5. Hence m(T , k) ≥ m(T 0 , k) for all k ≥ 1 and obviously m(T , 2) > m(T 0 , 2). Therefore T T 0 . Now suppose that y ≥ 2 and T T 0 is true for smaller value of y. Then by Lemma 2.1, m(T , k) = m(T − xy w1 , k) + m(T − xy − w1 , k − 1)

= m(T − xy w1 , k) + m (y − 1)P1 ∪ Ps+1 , k − 1 ,





m T 0 , k = m T 0 − xy v 1 , k + m T 0 − xy − v 1 , k − 1

= m T 0 − xy v1 , k + m(yP1 ∪ Ts,s−2,1 , k − 1). Therefore we have Ps+1 P1 ∪ Ps P1 ∪ Ts,s−2,1 by Lemmas 2.4 and 2.5 and T − xy w1 T 0 − xy v1 by induction hypothesis. Thus it is easy to see that T T 0 .

H. Ma

Now we suppose that l ≥ 1 and T T 0 is true for smaller value of l. Then by Lemma 2.1, m(T , k) = m(T − vi ul , k) + m(T − vi − ul , k − 1)

= m(T − vi ul , k) + m (l − 1)P1 ∪ Pi ∪ Ps−i ∪ Sn−s−l−1 , k − 1 = m(T − vi ul , k) + m(lP1 ∪ Pi ∪ Ps−i ∪ Sn−s−l−2 , k − 1)

+ m (n − s − 4)P1 ∪ Pi ∪ Ps−i , k − 2 ,





m T 0 , k = m T 0 − v1 xn−s−2 , k + m T 0 − v1 − xn−s−2 , k − 1



= m T 0 − v1 xn−s−2 , k + m (n − s − 2)P1 ∪ Ts,s−2,1 , k − 1



= m T 0 − v1 xn−s−2 , k + m (n − s − 1)P1 ∪ Ps−1 , k − 1

+ m (n − s − 1)P1 ∪ Ps−3 , k − 2 . By induction hypothesis, we can obtain that T − vi ul T 0 − v1 xn−s−2 . By Lemma 2.5, Pi ∪ Ps−i P1 ∪ Ps−1 3P1 ∪ Ps−3 . Therefore it is easy to check that T T 0 .  It is easily checked that |T6,3 | = |T7,3 | = 1, T7,4 = {T (7, 4; 1, 0, 1), T (7, 4; 1, 1, 0)}, and E(T (7, 4; 1, 0, 1)) < E(T (7, 4; 1, 1, 0)). Thus, for the trees with second-minimal energy in Tn,s with 3 ≤ s ≤ n − 3, we may assume that n ≥ 8. Theorem 3.2 (1) If n ≥ 6 and 3 ≤ s ≤ n − 3, then T (n, s; n − s − 2, 0, . . . , 0, 1) is the unique tree with minimal energy in Tn,s . (2) If n ≥ 8 and 5 ≤ s ≤ n − 3, then T (n, s; n − s − 2, 0, 1, 0, . . . , 0) is the unique tree with second-minimal energy in Tn,s . (3) If n ≥ 8, then T (n, 3; n − 6, 2) is the unique tree with second-minimal energy in Tn,3 . (4) T (n, 4; n − 6, 1, 0) if n = 8, T (n, 4; n − 7, 0, 2) if n ≥ 9 is the unique tree with second-minimal energy in Tn,4 . Proof For convenience, let  Tn,n−s+1 (1) and  Tn,n−s+1 (2) denote the trees with minimal and second-minimal energies in  Tn,n−s+1 respectively. Let T ∈ Tn,s be a tree and P = v0 v1 · · · vs be one of the longest path in T . Let t (T ) be the number of vertices in {v1 , v2 , . . . , vs−1 } with degree at least 3. Clearly, t (T ) ≥ 1. We consider two cases. Case 1 t (T ) ≥ 2. Suppose T =  Tn,n−s+1 (1),  Tn,n−s+1 (2). If T is a caterpillar, then  T ∈ Tn,n−s+1 and E(T ) > E( Tn,n−s+1 (2)) > E( Tn,n−s+1 (1)) by Lemma 1.4. Otherwise, we can get a caterpillar T  from T by a series of Operation I with t (T  ) = t (T ). It is not difficult to check that T  =  Tn,n−s+1 (1),  Tn,n−s+1 (2). Hence   we have E(T ) > E(T ) > E(Tn,n−s+1 (2)) > E( Tn,n−s+1 (1)) by Lemmas 2.6 and 1.4.

Some relations on the ordering of trees by minimal energies Fig. 6 The tree T  in Theorem 3.2

Case 2 t (T ) = 1. Without loss of generality, we assume that deg(vi ) ≥ 3. Obviously, we have 2 ≤ i ≤ s − 2. Let {Ti1 , . . . , Tic } be the set of connected components of T − {v0 , . . . , vs } with vertices at least 2. Since T is non-starlike, there is at least one vertex, say v, in Ti1 ∪ · · · ∪ Tic with degree at least 3. Without loss of generality, we assume that v ∈ Ti1 . If c > 1, by repeatedly using Operation I c − 1 times, we can finally get a tree T  ∈ Tn,s having the structure as given in Fig. 6, where NT  (vi ) = {vi−1 , vi+1 , w1 , u1 , . . . , ul }, w1 ∈ Ti1 and |V (Ti1 )| = n − s − l − 1 ≥ 3. By Lemma 2.6, we have E(T ) > E(T  ). Let T  = T when c = 1, notice that in this case it may be l = 0. If Ti1 is not a star with w1 as the center, let T  be the tree obtained from T  by replacing the branch Ti1 with a star Sn−s−1−l , where w1 is the center and NT (w1 ) = {vi , x1 , . . . , xn−s−2−l }, (see Fig. 5). It is clear that T  ∈ Tn,s . By Lemma 2.8, we have E(T  ) > E(T  ). Obviously, if i = 2, then x1 w1 v2 v3 · · · vs is a longest path in T  with deg(w1 ) ≥ 3 and deg(v2 ) ≥ 3, and the proof is similar to that of Case 1. So by symmetry we can assume that 3 ≤ i ≤ s − 3. Now by Lemma 3.1, Tn,n−s+1 (2)). we have E(T  ) > E(T (n, s; n − s − 2, 0, 1, 0, . . . , 0)) = E( The proof is thus complete.



From Lemma 1.4 and Theorem 3.2, we obtain that: Remark 3.3 The first two trees with minimal energies in Tn,s and  Tn,n−s+1 are the same for 3 ≤ s ≤ n − 3. 4 The trees with second-minimal energy in Tn,p and Tn,d Notice that |Tn,2 | = |Tn,n−1 | = 1, so in1 the following we assume that 3 ≤ p ≤ n − 2. By Lemma 1.3, Tn,n−p+1,1 is also the unique starlike tree with minimal energy in Tn,p . We first determine the starlike trees with second-minimal and thirdminimal energies in Tn,p . Notice that Tn,3,1 is the unique starlike tree in Tn,n−2 (n ≥ 5). Theorem 4.1 (1) Tn,4,2 is the unique starlike tree with second-minimal energy in Tn,n−3 for n ≥ 6. (2) If n ≥ 7 and 3 ≤ p ≤ n − 4, then Tn,n−p+1,3 is the unique starlike tree with second-minimal energy in Tn,p . Proof Since that Tn,4,1 and Tn,4,2 are the only two starlike trees in Tn,n−3 (n ≥ 6), the result (1) follows from Lemma 1.3. Let T = Tn,n−p+1,1 be a starlike tree in Tn,p ,

H. Ma

where 3 ≤ p ≤ n − 4. Then p(T ) ≥ 2. If p(T ) > 2, then by Lemma 2.7, we can get a tree T  from T by a series of Operation II with T T  and p(T  ) = 2. Then T  = Tn,n−p+1,i for some i ∈ {2, . . . , n − p − 1}. By Lemma 2.3, we have T  Tn,n−p+1,3 if T  = Tn,n−p+1,3 . Hence the result (2) holds. The proof is thus complete.  Theorem 4.2 (1) If n ≥ 7, then Sn,n−4 (1, 1, 1) is the unique starlike tree with third-minimal energy in Tn,n−4 . (2) If 3 ≤ p and p = n − 6 or n − 5, then Tn,n−p+1,2 is the unique starlike tree with third-minimal energy in Tn,p . (3) If n ≥ 10, then Sn,n−7 (2, 2, 2) is the unique starlike tree with third-minimal energy in Tn,n−7 . (4) If n ≥ 11 and 3 ≤ p ≤ n − 8, then Tn,n−p+1,5 is the unique starlike tree with third-minimal energy in Tn,p . Proof (1) It is easy to check that Tn,5,1 , Tn,5,2 (= Tn,5,3 ) and Sn,n−4 (1, 1, 1) are the only three starlike trees in Tn,n−4 (n ≥ 7). Thus the result (1) follows from Lemma 1.3 and Theorem 4.1. (2) Let T = Tn,n−p+1,1 , Tn,n−p+1,3 , Tn,n−p+1,2 be a starlike tree in Tn,p , where n − 6 ≤ p ≤ n − 5. Then it is easy to see that p(T ) ≥ 3. If p(T ) > 3, then by Lemma 2.7, we can get a starlike tree T  from T by a series of Operation II with T T  and p(T  ) = 3. Then T  is a tree of the form Sn,p (n1 , n2 , n3 ). Suppose 1 ≤ n1 ≤ n2 ≤ n3 . Since 4 ≤ n1 + n2 + n3 ≤ 5, we have n1 = 1. By Lemma 2.7, we have T  Tn,n−p+1,2 . Thus the result (2) follows from Lemma 1.3 and Theorem 4.1. (3) Let T = Tn,8,1 , Tn,8,3 , Sn,n−7 (2, 2, 2) be a starlike tree in Tn,n−7 . Then p(T ) ≥ 2. Suppose p(T ) = 2. Then T ∈ {Tn,8,2 , Tn,8,4 }. By Lemma 2.3 and Corollary 2.15, we have E(Tn,8,2 ) > E(Tn,8,4 ) > E(Sn,n−7 (2, 2, 2)). Suppose p(T ) = 3. Then T is a tree of the form Sn,p (n1 , n2 , n3 ) with 1 ≤ n1 ≤ n2 ≤ n3 . Since T = Sn,n−7 (2, 2, 2) and n1 + n2 + n3 = 6, we have n1 = 1. By Lemma 2.7, we have T Tn,8,2 . Suppose p(T ) = 4. Then by Lemma 2.7, we can get a starlike tree T  by Operation II with T T  and p(T  ) = 3. If T  = Sn,n−7 (2, 2, 2), then by the argument above, we have T  Tn,8,2 . If T  = Sn,n−7 (2, 2, 2), then T must be the tree Sn,n−7 (1, 1, 2, 2). Hence we have Sn,n−7 (1, 1, 2, 2) Sn,n−7 (1, 1, 4)

Tn,8,2 by Lemma 2.7. Suppose p(T ) ≥ 5. Then we can get a starlike tree T  by a series of Operation II with T T  and p(T  ) = 4. Hence by the argument above, we have T Tn,8,2 . Thus the result (3) follows from Lemma 1.3 and Theorem 4.1. (4) Let T = Tn,n−p+1,1 , Tn,n−p+1,3 , Tn,n−p+1,5 be a starlike tree in Tn,p , where 3 ≤ p ≤ n − 8. Then p(T ) ≥ 2. If p(T ) = 2, then T = Tn,n−p+1,i for some i. By Lemma 2.3, we have T Tn,n−p+1,5 . If p(T ) > 3, then by Lemma 2.7, we can finally get a starlike tree T  by a series of Operation II with T T  and p(T  ) = 3. Then T  is a tree of the form Sn,p (n1 , n2 , n3 ) with 1 ≤ n1 ≤ n2 ≤ n3 .

Some relations on the ordering of trees by minimal energies

Notice that by Lemma 2.7, we have T  Tn,n−p+1,ni +1 (i = 1, 2, 3). Suppose n1 = 2. Then n1 + 1 = 3, n − p − 2 and so T  Tn,n−p+1,n1 +1  Tn,n−p+1,5 by Lemma 2.3. Suppose n1 = 2. Then n3 + 1 = 3, n − p − 2 and so T 

Tn,n−p+1,n3 +1  Tn,n−p+1,5 by Lemma 2.3. Thus the result (4) follows from  Lemma 1.3 and Theorem 4.1. By the proof of Theorem 4.2(3), we can further obtain the following result. Corollary 4.3 Tn,8,4 (Tn,8,2 , resp.) is the unique starlike tree with fourth-minimal (fifth-minimal) energy in Tn,n−7 for n ≥ 10. Now we characterize the tree with second-minimal energy in Tn,p . Obviously, |T5,3 | = 1. Theorem 4.4 (1) Tn,n−2,2 if n = 6, Tn,n−2,3 if n ≥ 7 is the unique tree with second-minimal energy in Tn,3 . (2) If n ≥ 9 and 4 ≤ p ≤ n − 5, then the second-minimal energy tree in Tn,p is one of the two trees Tn,n−p+1,3 and T (n, n − p + 1; p − 3, 0, . . . , 0, 1). (3) T (n, 5; n − 7, 0, 0, 1) if n = 8, Tn,5,2 if n ≥ 9 is the unique tree with secondminimal energy in Tn,n−4 . (4) T (n, 4; n − 6, 0, 1) is the unique tree with second-minimal energy in Tn,n−3 for n ≥ 7. (5) T (n, 3; n − 5, 1) is the unique tree with second-minimal energy in Tn,n−2 for n ≥ 6. Proof Let T = Tn,n−p+1,1 be a tree in Tn,p . We distinguish the following four cases: Case 1 p = 3. Then T is starlike. So the result (1) follows from Theorem 4.1. Case 2 4 ≤ p ≤ n − 4. Then the result (2) follows from Lemma 1.4(1) and Theorem 4.1 and furthermore the result (3) follows from Lemma 1.2(3). Case 3 p = n − 3. By Lemma 1.4(1) and Theorem 4.1, the tree with second-minimal energy in Tn,n−3 is either T (n, 4; n − 6, 0, 1) or Tn,4,2 . Thus the result (4) follows from Lemma 1.2(2). Case 4 p = n − 2. Then T is non-starlike. So the result (5) follows from Lemma 1.4(1). The proof is thus complete.



Lemma 4.5 Let 4 ≤ p ≤ n − 5, Tn1 = T (n, n − p + 1; p − 3, 0, . . . , 0, 1) and Tn2 = Tn,n−p+1,3 . Then we have    



n−p−k−1 n−p−k−1 m Tn1 , k − m Tn2 , k = (p − 3) − . (3) k−2 k−3

H. Ma

Proof It is easy to obtain that

m Tn1 , k = m(Pn−p+2 , k) + (p − 2)m(Pn−p , k − 1) + (p − 3)m(Pn−p−2 , k − 2),

m Tn2 , k = m(Pn−p+2 , k) + (p − 2)m(Pn−p−2 , k − 1) + 2(p − 2)m(Pn−p−2 , k − 2). Hence by equality (2),



m Tn1 , k − m Tn2 , k = (p − 2)m(Pn−p−3 , k − 2) − m(Pn−p−2 , k − 2) = (p − 3)m(Pn−p−3 , k − 2) − m(Pn−p−4 , k − 3). Since m(Pn , k) =

n−k

k

, the result follows.



Theorem 4.6 Let 4 ≤ p ≤ n − 5, Tn1 = T (n, n − p + 1; p − 3, 0, . . . , 0, 1) and Tn2 = Tn,n−p+1,3 . Then we have (1) If n − p is even or n − p is odd and p ≤  n3 , then Tn1 and Tn2 are quasi-order incomparable. (2) If n − p is odd and p ≥  n3  + 1, then Tn1 Tn2 . Proof Clearly, m(Tn1 , 1) = m(Tn2 , 1). By equality (3), we have



m Tn1 , 2 − m Tn2 , 2 = p − 3 ≥ 1. Notice that the matching number of Tn1 and Tn2 are both  n−p 2  + 1. So we distinguish the following two cases: Case 1 n − p is even with n − p = 2l. Then by equality (3) we have



m Tn1 , l + 1 − m Tn2 , l + 1 = −1. Case 2 n − p is odd with n − p = 2l + 1. Then by equality (3) we have



3p − n − 3 . m Tn1 , l + 1 − m Tn2 , l + 1 = p − l − 2 = 2 Subcase 2.1 p ≤  n3 . Now m(Tn1 , l + 1) − m(Tn2 , l + 1) < 0. Subcase 2.2 p ≥  n3  + 1. Now m(Tn1 , l + 1) − m(Tn2 , l + 1) ≥ 0. Also we have



m Tn1 , k − m Tn2 , k     n−p−k−1 n − p − 3k + 4 n − p − k − 1 = (p − 4) + n − p − 2k + 2 k−2 k−2   n−p−k−1 1 = n − p − 2k + 2 k−2  × (p − 4)(n − p − 2k + 2) + (n − p − 3k + 4) .

Some relations on the ordering of trees by minimal energies

Let f (x) = (p − 4)(n − p − 2x + 2) + (n − p − 3x + 4). Then we have f  (x) = −2p + 5 < 0. So f (k) is a decrease function of k. Therefore for all 3 ≤ k ≤ l + 1, we have f (k) ≥ f (l + 1) = p − l − 2 ≥ 0 and so m(Tn1 , k) − m(Tn2 , k) ≥ 0. The proof is thus complete.



Theorem 4.7 (1) Tn,6,3 is the unique tree with second-minimal energy in Tn,n−5 for n ≥ 9. (2) T (n, 7; n − 9, 0, 0, 0, 0, 1) if n = 10, Tn,7,3 if n ≥ 11 is the unique tree with second-minimal energy in Tn,n−6 . (3) Tn,8,3 is the unique tree with second-minimal energy in Tn,n−7 for n ≥ 11. (4) T (n, 9; n − 11, 0, 0, 0, 0, 0, 0, 1) if n = 12, Tn,9,3 if n ≥ 13 is the unique tree with second-minimal energy in Tn,n−8 . . . Proof Notice that E(T11,8,3 ) = 12.04307 < E(T (11, 8; 1, 0, 0, 0, 0, 0, 1)) = 12.05468, E(Tn,7,2 ) > E(Tn,7,3 ) and E(Tn,9,4 ) > E(Tn,9,3 ). The results follow from Theorems 4.4(2), 4.6(2), Lemmas 2.12 and 2.16.  In the following, we determine the tree with second-minimal energy in Tn,d for 6 ≤ d ≤ n − 2. Theorem 4.8 (1) Tn,n−2,2 if n = 6, Tn,n−2,3 if n ≥ 7 is the unique tree with second-minimal energy in Tn,n−2 . (2) If 10 ≤ d ≤ n − 3, then the second-minimal energy tree in Tn,d is one of the two trees Tn,d,3 and T (n, d; n − d − 2, 0, . . . , 0, 1). (3) Tn,6,3 is the unique tree with second-minimal energy in Tn,6 for n ≥ 9. (4) T (n, 7; n − 9, 0, 0, 0, 0, 1) if n = 10, Tn,7,3 if n ≥ 11 is the unique tree with second-minimal energy in Tn,7 . (5) Tn,8,3 is the unique tree with second-minimal energy in Tn,8 for n ≥ 11. (6) T (n, 9; n − 11, 0, 0, 0, 0, 0, 0, 1) if n = 12, Tn,9,3 if n ≥ 13 is the unique tree with second-minimal energy in Tn,9 . Proof Let T = Tn,d,1 be a tree in Tn,d . Suppose d = n−2. Then T is of form Tn,n−2,i . Hence the result (1) follows from Lemma 2.3. Suppose 6 ≤ d ≤ n − 3. We distinguish the following two cases: Case 1 T is a caterpillar. Then T ∈ Tn,n−d+1 . By Theorem 4.4(2), we have E(T ) > E(Tn,d,3 ) or E(T ) > E(T (n, d; n − d − 2, 0, . . . , 0, 1)) if T = Tn,d,3 , T (n, d; n − d − 2, 0, . . . , 0, 1). Case 2 T is not a caterpillar. Then we can get a caterpillar T  from T by a series of Operation I with E(T ) > E(T  ). Clearly, T  = Tn,d,1 , T (n, d; n − d − 2, 0, . . . , 0, 1). If T  = Tn,d,3 , then similar to Case 1 we have E(T  ) > E(Tn,d,3 ) or E(T  ) > E(T (n, d; n − d − 2, 0, . . . , 0, 1)). If T  = Tn,d,3 , then by the argument similar to Case 2 in Theorem 3.2, from T , we can obtain a tree T  with the struc-

H. Ma

ture as shown in Fig. 5, where s = d, i = 3, l ≥ 0 and n − s − l ≥ 3. Notice that E(T ) ≥ E(T  ). By Lemmas 3.1 and 1.4, E(T  ) > E(T (n, d; n − d − 2, 0, 1, 0, . . . , 0)) > E(T (n, d; n−d −2, 0, . . . , 0, 1)). Therefore we have E(T ) > E(Tn,d,3 ) and E(T ) > E(T (n, d; n − d − 2, 0, . . . , 0, 1)). To sum up, the result (2) holds. Furthermore the results (3)–(6) follow from Theorem 4.7.  Combining Lemmas 1.1, 1.3, 1.2, Theorems 4.4, 4.7 and 4.8, we obtain that: Remark 4.9 The first two trees with minimal energies in Tn,p and Tn,n−p+1 are the same for 3 ≤ p ≤ n − 2.

5 The trees with third-minimal energy in Tn,p and Tn,d We first characterize the tree with third-minimal energy in Tn,p (3 ≤ p ≤ n − 2). Clearly, |T6,3 | = 2. Theorem 5.1 (1) S7,3 (1, 1, 1) if n = 7, Tn,n−2,2 if 8 ≤ n ≤ 9, S10,3 (2, 2, 2) if n = 10, Tn,n−2,5 if n ≥ 11 is the unique tree with third-minimal energy in Tn,3 . (2) Suppose 4 ≤ p ≤ n−9. If E(Tn,n−p+1,3 ) > E(T (n, n−p +1; p −3, 0, . . . , 0, 1)), then Tn,n−p+1,3 is the unique tree with third-minimal energy in Tn,p ; If E(Tn,n−p+1,3 ) < E(T (n, n − p + 1; p − 3, 0, . . . , 0, 1)), then the third-minimal energy tree in Tn,p is one of the two trees Tn,n−p+1,5 and T (n, n − p + 1; p − 3, 0, . . . , 0, 1). (3) Tn,9,3 if n = 12, T (n, 9; n − 11, 0, 0, 0, 0, 0, 0, 1) if 13 ≤ n ≤ 15, Tn,9,4 (= Tn,9,5 ) if n ≥ 16 is the unique tree with third-minimal energy in Tn,n−8 . (4) T (n, 8; n − 10, 0, 0, 0, 0, 0, 1) if 11 ≤ n ≤ 13, Sn,n−7 (2, 2, 2) if n ≥ 14 is the unique tree with third-minimal energy in Tn,n−7 . (5) Tn,7,3 if n = 10, T (n, 7; n − 9, 0, 0, 0, 0, 1) if 11 ≤ n ≤ 15, Tn,7,2 if n ≥ 16 is the unique tree with third-minimal energy in Tn,n−6 . (6) T (n, 6; n − 8, 0, 0, 0, 1) is the unique tree with third-minimal energy in Tn,n−5 for n ≥ 9. (7) Tn,5,2 if n = 8, T (n, 5; n−7, 0, 0, 1) if n ≥ 9 is the unique tree with third-minimal energy in Tn,n−4 . (8) Tn,4,2 if 7 ≤ n ≤ 8, T (n, 4; n − 7, 0, 2) if n ≥ 9 is the unique tree with thirdminimal energy in Tn,n−3 . (9) T (n, 3; n − 6, 2) is the unique tree with third-minimal energy in Tn,n−2 for n ≥ 8. Proof Let T = Tn,n−p+1,1 be a tree in Tn,p . We distinguish the following four cases: Case 1 p = 3. Then T is starlike. So the result (1) follows from Theorem 4.2. Case 2 4 ≤ p ≤ n − 4.

Some relations on the ordering of trees by minimal energies

If E(Tn,n−p+1,3 ) > E(T (n, n − p + 1; p − 3, 0, . . . , 0, 1)), then T (n, n − p + 1; p − 3, 0, . . . , 0, 1) is the unique tree with second-minimal energy in Tn,p by Theorem 4.4(2). It follows from Theorem 4.1(2) and Lemma 1.4(4) that the third-minimal energy tree in Tn,p is either Tn,n−p+1,3 or T (n, n − p + 1; p − 3, 0, 1, 0, . . . , 0). Thus Tn,n−p+1,3 is the unique tree with third-minimal energy in Tn,p by Lemma 2.17. If E(Tn,n−p+1,3 ) < E(T (n, n − p + 1; p − 3, 0, . . . , 0, 1)), then Tn,n−p+1,3 is the unique tree with second-minimal energy in Tn,p by Theorem 4.4(2). It follows from Theorem 4.2 and Lemma 1.4(1) that the third-minimal energy tree in Tn,p is one of the two trees T (n, n − p + 1; p − 3, 0, . . . , 0, 1) and Tn,n−p+1,5 if 4 ≤ p ≤ n − 8, Sn,n−7 (2, 2, 2) if p = n − 7, Tn,n−p+1,2 if n − 6 ≤ p ≤ n − 5, Sn,n−4 (1, 1, 1) if p = n − 4. Hence the result (2) holds. Furthermore, the result (3) follows from Theorem 4.7(4) and Lemma 2.16, the result (4) follows from Theorem 4.7(3) and Lemma 2.14, the result (5) follows from Theorem 4.7(2) and Lemma 2.12, the result (6) follows from Theorem 4.7(1) and Lemma 2.11 and the result (7) follows from Theorem 4.4(3) and Lemma 2.10. Case 3 p = n − 3. Notice that  T7,4 = {T (7, 4; 1, 0, 1), T (7, 4; 1, 1, 0)} with E(T (7, 4; 1, 0, 1)) < E(T (7, 4; 1, 1, 0)). Hence by Theorems 4.4(4), 4.1(1) and Lemma 1.4(3), the tree with third-minimal energy in Tn,n−3 is either T (n, 4; n − 6, 1, 0) if 7 ≤ n ≤ 8, T (n, 4; n − 7, 0, 2) if n ≥ 9 or Tn,4,2 . By direct . . computing, we have E(T8,4,2 ) = 8.15276 < E(T (8, 4; 2, 1, 0)) = 8.26113 and . . E(T7,4,2 ) = 7.59587 < E(T (7, 4; 1, 1, 0)) = 7.66299. Combining the above fact and Lemma 2.9, the result (8) follows. Case 4 p = n − 2. Then T is non-starlike. So the result (9) follows from Lemma 1.4(2). The proof is thus complete.



Theorem 5.2 Let 4 ≤ p ≤ n − 9, Tn1 = T (n, n − p + 1; p − 3, 0, . . . , 0, 1) and Tn2 = Tn,n−p+1,5 . Then Tn1 and Tn2 are quasi-order incomparable. Proof It is easy to obtain that

m Tn1 , k = m(Pn−p+2 , k) + (p − 2)m(Pn−p , k − 1) + (p − 3)m(Pn−p−2 , k − 2),

m Tn2 , k = m(Pn−p+2 , k) + (p − 2)m(P5 ∪ Pn−p−4 , k − 1) = m(Pn−p+2 , k) + (p − 2)m(Pn−p−4 , k − 1) + 4(p − 2)m(Pn−p−4 , k − 2) + 3(p − 2)m(Pn−p−4 , k − 3). Notice that m(Pn , k) =

n−k

k

. Then we have



m Tn1 , 2 − m Tn2 , 2 = p − 3 ≥ 1. Notice that the matching number of Tn1 and Tn2 are both  n−p 2  + 1. So we distinguish the following two cases:

H. Ma

Case 1 n − p is even with n − p = 2l. Then we have



m Tn1 , l + 1 − m Tn2 , l + 1 = (p − 2) + (p − 3) − 3(p − 2) = 1 − p < 0. Case 2 n − p is odd with n − p = 2l + 1. Since l ≥ 4, we have



m Tn1 , l + 1 − m Tn2 , l + 1 = (p − 2)(l + 1) + (p − 3)l − 3(p − 2)(l − 1) = −(p − 1)(l − 4) − 4 < 0. The proof is thus complete.



Now we determine the tree with third-minimal energy in Tn,d (3 ≤ d ≤ n − 2). Clearly, |T7,5 | = 2. Theorem 5.3 (1) Tn,n−2,2 if 8 ≤ n ≤ 9, Tn,n−2,4 if n = 10, Tn,n−2,5 if n ≥ 11 is the unique tree with third-minimal energy in Tn,n−2 . (2) Suppose 10 ≤ d ≤ n − 3. If E(Tn,d,3 ) > E(T (n, d; n − d − 2, 0, . . . , 0, 1)), then Tn,d,3 is the unique tree with third-minimal energy in Tn,d ; If E(Tn,d,3 ) < E(T (n, d; n − d − 2, 0, . . . , 0, 1)), then the third-minimal energy tree in Tn,d is one of the two trees Tn,d,5 and T (n, d; n − d − 2, 0, . . . , 0, 1). (3) Tn,9,3 if n = 12, T (n, 9; n − 11, 0, 0, 0, 0, 0, 0, 1) if 13 ≤ n ≤ 15, Tn,9,4 if n ≥ 16 is the unique tree with third-minimal energy in Tn,9 . (4) T (n, 8; n − 10, 0, 0, 0, 0, 0, 1) is the unique tree with third-minimal energy in Tn,8 for n ≥ 11. (5) Tn,7,3 if n = 10, T (n, 7; n − 9, 0, 0, 0, 0, 1) if 11 ≤ n ≤ 15, Tn,7,2 if n ≥ 16 is the unique tree with third-minimal energy in Tn,7 . (6) T (n, 6; n − 8, 0, 0, 0, 1) is the unique tree with third-minimal energy in Tn,6 for n ≥ 9. (7) Tn,5,2 if n = 8, T (n, 5; n−7, 0, 0, 1) if n ≥ 9 is the unique tree with third-minimal energy in Tn,5 . (8) Tn,4,2 if 7 ≤ n ≤ 8, T (n, 4; n − 7, 0, 2) if n ≥ 9 is the unique tree with thirdminimal energy in Tn,4 . (9) T (n, 3; n − 6, 2) is the unique tree with third-minimal energy in Tn,3 for n ≥ 8. Proof Let T be a tree in Tn,d . Suppose d = n − 2. Then T is of form Tn,n−2,i . Hence the result (1) follows from Lemma 2.3. Suppose d = 3. Then T ∈ Tn,n−2 and so the result (9) holds by Theorem 5.1. In the following, suppose 4 ≤ d ≤ n − 3. For convenience, let Tn,d (1) and Tn,d (2) denote the trees with minimal and secondminimal energies in Tn,d respectively; and Tn,p (1), Tn,p (2) and Tn,p (3) denote the trees with minimal, second-minimal and third-minimal energies in Tn,p respectively. By Remark 4.9, Tn,d (i) = Tn,n−d+1 (i) for i = 1, 2. Notice that Tn,d (1) = Tn,d,1 . Let T = Tn,d (1), Tn,d (2), Tn,n−d+1 (3) be a tree in Tn,d .

Some relations on the ordering of trees by minimal energies

Case 1 10 ≤ d ≤ n − 3. Subcase 1.1 E(Tn,d,3 ) > E(T (n, d; n − d − 2, 0, . . . , 0, 1)). Then by Theorems 4.8 and 5.1, Tn,d (2) = T (n, d; n − d − 2, 0, . . . , 0, 1) and Tn,n−d+1 (3) = Tn,d,3 . If T is a caterpillar, then T ∈ Tn,n−d+1 and so E(T ) > E(Tn,n−d+1 (3)). Otherwise, from T , we can get a caterpillar T  by a series of Operation I with E(T ) > E(T  ). Clearly, T  = Tn,d (1), Tn,d (2), and so E(T  ) ≥ E(Tn,n−d+1 (3)). Also we have E(T ) > E(Tn,n−d+1 (3)). Subcase 1.2 E(Tn,d,3 ) < E(T (n, d; n − d − 2, 0, . . . , 0, 1)). Then by Theorems 4.8 and 5.1, Tn,d (2) = Tn,d,3 and Tn,n−d+1 (3) is either Tn,d,5 or T (n, d; n − d − 2, 0, . . . , 0, 1). If T is a caterpillar, then T ∈ Tn,n−d+1 , and so E(T ) > E(Tn,d,5 ) or E(T ) > E(T (n, d; n − d − 2, 0, . . . , 0, 1)) if T = Tn,d,5 , T (n, d; n − d − 2, 0, . . . , 0, 1). Otherwise, we can get a caterpillar T  by a series of Operation I with E(T ) > E(T  ). Clearly, T  = Tn,d (1). If T  = Tn,d (2), then E(T  ) ≥ E(Tn,d,5 ) or E(T  ) ≥ E(T (n, d; n − d − 2, 0, . . . , 0, 1)). If T  = Tn,d (2), then by the argument similar to Case 2 in Theorem 4.8, we have E(T ) > E(T (n, d; n − d − 2, 0, . . . , 0, 1)). The result (2) thus follows. Case 2 4 ≤ d ≤ 9. Subcase 2.1 T is a caterpillar. Then T ∈ Tn,n−d+1 . Therefore E(T ) > E(Tn,n−d+1 (3)) when d = 8. Notice that Sn,n−7 (2, 2, 2) ∈ / Tn,8 , by Corollary 4.3 and Lemma 2.13, we have E(T ) > E(T (n, 8; n − 10, 0, 0, 0, 0, 0, 1)) when T = T (n, 8; n − 10, 0, 0, 0, 0, 0, 1) and d = 8. Subcase 2.2 T is not a caterpillar. Then we can get a caterpillar T  by a series of Operation I with E(T ) > E(T  ). Clearly, T  = Tn,d (1). If T  = Tn,d (2), then similarly we have E(T ) > E(Tn,n−d+1 (3)) when d = 8 and E(T ) > E(T (n, 8; n − 10, 0, 0, 0, 0, 0, 1)) when T = T (n, 8; n − 10, 0, 0, 0, 0, 0, 1) and d = 8. If T  = Tn,d (2), then 5 ≤ d ≤ 9. Subsubcase 2.2.1 d = 5. Now T  = Tn,5,2 with n ≥ 9. Hence by the argument similar to Case 2 in Theorem 3.2, from tree T , we can obtain a tree T  with the structure as shown in Fig. 5, where s = 5, i = 2, l ≥ 0 and n − s − 2 − l ≥ 1. Notice that E(T ) ≥ E(T  ). If n − 7 − l ≥ 2, then E(T  ) > E(T (n, 5; n − l − 8, l + 2, 0, 0)) > E(T (n, 5; n − 7, 0, 0, 1)) by Lemmas 2.6 and 1.4(1). If n − 7 − l = 1, then T  = Sn,n−5 (1, 1, 2), and so E(T  ) > E(T (n, 5; n − 7, 0, 0, 1)) by Lemma 2.18. Therefore we have E(T ) > E(Tn,n−4 (3)) for n ≥ 9. Subsubcase 2.2.2 d = 7. Now T  = Tn,7,3 with n ≥ 11. Then by the argument similar to Case 2 in Theorem 4.8, we have E(T ) > E(T (n, 7; n − 9, 0, 0, 0, 0, 1)) for n ≥ 11. Furthermore, E(T ) > E(T (n, 7; n − 9, 0, 0, 0, 0, 1)) > E(Tn,7,2 ) for n ≥ 16 by Lemma 2.12. Therefore we have E(T ) > E(Tn,n−6 (3)) for n ≥ 16. Subsubcase 2.2.3 d = 6, 8, 9. By the argument similar to Subsubcase 2.2.2, we can obtain that E(T ) > E(T (n, 8; n − 10, 0, 0, 0, 0, 0, 1)) when d = 8, n ≥ 11 and E(T ) > E(Tn,n−d+1 (3)) when d = 6, n ≥ 9 and d = 9, n ≥ 13. The proof is thus complete.



H. Ma

It follows from Lemma 2.13 and Corollary 4.3 that T (n, 8; n − 10, 0, 0, 0, 0, 0, 1) is the caterpillar with third-minimal energy in Tn,n−7 for n ≥ 11. Hence by Theorems 5.1 and 5.3, we obtain that: Remark 5.4 The trees with third-minimal energy in Tn,d and Tn,n−d+1 are the same when n ≥ 11, 3 ≤ d ≤ n − 2 and d = 8; and the tree with third-minimal energy in Tn,8 is the caterpillar with third-minimal energy in Tn,n−7 for n ≥ 11. Acknowledgements We would like to thank the reviewers for helpful comments and suggestions leading to the clear presentation of the paper, especially for pointing out the error of assertion (∗) and the gap in the proofs of the original submission, in which we thought that the first r trees with minimal energies among all n-vertex trees with p pendent vertices are also the first r trees with minimal energies among all n-vertex trees with diameter n − p + 1 if they are caterpillars.

References 1. Andriantiana, E.O.D.: More trees with large energy. MATCH Commun. Math. Comput. Chem. 68, 675–695 (2012) 2. Guo, J.: On the minimal energy ordering of trees with perfect matchings. Discrete Appl. Math. 156, 2598–2605 (2008) 3. Gutman, I.: Acyclic systems with extremal Hückel π -electron energy of trees. Theor. Chim. Acta 45, 79–87 (1977) 4. Gutman, I., Polansky, O.E.: Mathematical Concepts in Organic Chemistry. Springer, Berlin (1986) 5. Gutman, I., Zhang, F.: On the ordering of graphs with respect to their matching numbers. Discrete Appl. Math. 15, 25–33 (1986) 6. Gutman, I., Radenkovi´c, S., Li, N., Li, S.: Extremal energy trees. MATCH Commun. Math. Comput. Chem. 59, 315–320 (2008) 7. Gutman, I., Li, X., Zhang, J.: Graph energy. In: Dehmer, M., Emmert-Streib, F. (eds.) Analysis of Complex Networks: From Biology to Linguistics, pp. 145–174. Wiley/VCH, New York/Weinheim (2009) 8. He, C., Wu, B., Yu, Z.: On the energy of trees with given domination number. MATCH Commun. Math. Comput. Chem. 64, 169–180 (2010) 9. Heuberger, C., Wagner, S.G.: Chemical trees minimizing energy and Hosoya index. J. Math. Chem. 46, 214–230 (2009) 10. Huo, B., Li, X., Shi, Y., Wang, L.: Determining the conjugated trees with the third- through the sixthminimal energies. MATCH Commun. Math. Comput. Chem. 65, 521–532 (2011) 11. Li, H.: On minimal energy ordering of acyclic conjugated molecules. J. Math. Chem. 25, 145–169 (1999) 12. Li, N., Li, S.: On the extremal energies of trees. MATCH Commun. Math. Comput. Chem. 59, 291– 314 (2008) 13. Li, S., Li, N.: On minimal energies of trees with given diameter. Electron. J. Linear Algebra 17, 414–425 (2008) 14. Li, J., Li, X.: On the maximal energy trees with one maximum and one second maximum degree vertex. MATCH Commun. Math. Comput. Chem. 67, 525–539 (2012) 15. Li, X., Lian, H.: Conjugated chemical trees with extremal energy. MATCH Commun. Math. Comput. Chem. 66, 891–902 (2011) 16. Li, X., Yao, X., Zhang, J., Gutman, I.: Maximum energy trees with two maximum degree vertices. J. Math. Chem. 45, 962–973 (2009) 17. Li, J., Li, X., Shi, Y.: On the maximal energy tree with two maximum degree vertices. Linear Algebra Appl. 435, 2272–2284 (2011) 18. Li, X., Shi, Y., Gutman, I.: Graph Energy. Springer, New York (2012) 19. Lin, X., Guo, X.: On the minimal energy of trees with a given number of vertices of degree two. MATCH Commun. Math. Comput. Chem. 62, 473–480 (2009) 20. Lin, W., Guo, X., Li, H.: On the extremal energies of trees with a given maximum degree. MATCH Commun. Math. Comput. Chem. 54, 363–378 (2005)

Some relations on the ordering of trees by minimal energies 21. Shan, H., Shao, J.: The proof of a conjecture on the comparison of the energies of trees. J. Math. Chem. 50, 2637–2647 (2012) 22. Shan, H., Shao, J., Gong, F., Liu, Y.: An edge grafting theorem on the energy of unicyclic and bipartite graphs. Linear Algebra Appl. 433, 547–556 (2010) 23. Shan, H., Shao, J., Li, S., Li, X.: On a conjecture on the tree with fourth greatest energy. MATCH Commun. Math. Comput. Chem. 64, 181–188 (2010) 24. Shan, H., Shao, J., Zhang, L., He, C.: Proof of a conjecture on trees with large energy. MATCH Commun. Math. Comput. Chem. 68, 703–720 (2012) 25. Wang, W.: Ordering of Hückel trees according to minimal energies. Linear Algebra Appl. 430, 703– 717 (2009) 26. Wang, W., Kang, L.: Ordering of the trees with a perfect matching by minimal energies. Linear Algebra Appl. 431, 946–961 (2009) 27. Wang, W., Kang, L.: Ordering of the trees by minimal energies. J. Math. Chem. 47, 937–958 (2010) 28. Yan, W., Ye, L.: On the minimal energy of trees with a given diameter. Appl. Math. Lett. 18, 1046– 1052 (2005) 29. Yan, W., Ye, L.: On the maximal energy and the Hosoya index of a type of trees with many pendant vertices. MATCH Commun. Math. Comput. Chem. 53, 449–459 (2005) 30. Yao, X.: Maximum energy trees with one maximum and one second maximum degree vertex. MATCH Commun. Math. Comput. Chem. 64, 217–230 (2010) 31. Ye, L., Chen, R.: Ordering of trees with a given bipartition by their energies and Hosoya indices. MATCH Commun. Math. Comput. Chem. 52, 193–208 (2004) 32. Ye, L., Yuan, X.: On the minimal energy of trees with a given number of pendent vertices. MATCH Commun. Math. Comput. Chem. 57, 193–201 (2007) 33. Yu, A., Lv, X.: Minimal energy on trees with k pendent vertices. Linear Algebra Appl. 418, 625–633 (2006) 34. Zhang, F., Li, H.: On acyclic conjugated molecules with minimal energies. Discrete Appl. Math. 92, 71–84 (1999) 35. Zhang, J., Zhou, B.: On minimal energies of non-starlike trees with given number of pendent vertices. MATCH Commun. Math. Comput. Chem. 62, 481–490 (2009) 36. Zhou, B., Li, F.: On minimal energies of trees of a prescribed diameter. J. Math. Chem. 39, 465–473 (2006) 37. Zhu, J.: Minimal energies of trees with given parameters. Linear Algebra Appl. 436, 3120–3131 (2012)