J. Appl. Math. Comput. DOI 10.1007/s12190-017-1139-7 ORIGINAL RESEARCH On the least distance eigenvalues of the second power of a graph Fangguo He1 Received: 30 July 2017 © Korean Society for Computational and Applied Mathematics 2017 Abstract The k-th power of a graph G, denoted by G k , is the graph obtained from G by adding an edge between each pair of vertices with distance at most k. This paper investigates the least distance eigenvalues of the second power of a connected graph, and determine the trees and unicyclic√graphs with least distance eigenvalues of the second power in [− 3, − 2] and (− 3+2 5 , − 1], respectively. Keywords Distance eigenvalues · k-th Power of a graph · Tree · Unicyclic graph Mathematics Subject Classification 05C50 · 15A18 1 Introduction All graphs considered here are simple, undirected and connected. Let G be a graph with vertex set V (G) = {v1 , v2 , . . . , vn } and edge set E(G) = {e1 , e2 , . . . , em }. If m = n − 1 + c, then G is called a c-cyclic graph. If c = 0, 1 and 2, then G is a tree, unicyclic graph and bicyclic graph, respectively. We denote by N G (v) the neighbor set of vertex v in a graph G, and denote by K n , Pn , Sn the complete graph, the path, the star of order n respectively. The distance between vertices vi and v j of G, denoted by dG (vi , v j ) or di j , is defined to be the length of the shortest path from vi to v j . The diameter of G, denoted by d(G), is the maximum distance between any pair of vertices of G. B 1 Fangguo He hfg0118@126.com College of Mathematics and Physics, Huanggang Normal University, Huanggang 438000, People’s Republic of China 123 F. He The distance matrix D(G) of a connected graph G is the n ×n matrix with its (i, j)entry equal to di j (i, j = 1, 2, . . . , n). We call the eigenvalues of D(G) the distance eigenvalues of G, and denote by λ1 (G), λ2 (G), . . . , λn (G). Let λ1 = λ1 (G) be the least distance eigenvalue. The distance matrix of a graph is very useful in different fields including the design of communication network, graph embedding theory as well as molecular stability. The problem concerning the distance eigenvalues of a connected graph has been studied extensively recently (see [4,14,17,20,21],etc.). Merris [13] found relations between the distance eigenvalues and the Laplacian eigenvalues for trees. Ruzieh and Powers [15] showed that the path is the unique connected graph of order n with maximum largest distance eigenvalue. Stevanovic and Ilic [17] showed that the star is the unique tree on n vertices with minimum largest distance eigenvalue, and determined the unique tree with maximum largest distance eigenvalue when the maximum degree are fixed. Ilić [7] determined the unique tree with minimum largest distance eigenvalue when the the matching number are fixed. In [11], Lin and Zhou determined the trees, the unicyclic and bicyclic graphs with least distance eigenvalues. Xing and Zhou [18] gave sharp lower bounds for the largest and the second largest distance eigenvalues of graph powers. For more information on distance eigenvalues of graphs, see [1,9,10,19]. For a positive integer k, the k-th power of G, denoted by G k , is the graph obtained from G by adding an edge between each pair of vertices with distance at most k. It is easy to see that G k is isomorphic to the complete graph if integer k ≥ d(G). In particular, the graph G 2 is called the second power of G. Graph powers are useful in distributed computing (see [12]) and designing algorithms for certain combinatorial optimization problems. Moreover, graph powers are of great interest and have a number of possible applications in different disciplines. More work on this line may be found in [2,3,5,8,16,18]. Motivated by these works, in this paper, we investigate the least distance eigenvalues of the second power of connected graphs, and determine the trees and unicyclic graphs√with least distance eigenvalues of the second power of graph in [−3, −2] and (− 3+2 5 , −1], respectively. We also determine the unicyclic graph (graph contains a triangle with diameter 3) such that the least distance eigenvalue of the second power of graph is minimum. 2 Preliminaries Lemma 2.1 [6] Let Hn denote the set of all n×n Hermitian matrices. Suppose A ∈ Hn with eigenvalues λ1 ≥ λ2 ≥ · · · ≥ λn . B is a m × m principal matrix of A. Suppose B has eigenvalues μ1 ≥ μ2 ≥ · · · ≥ μm . Then λi ≥ μi ≥ λn−m+i for i = 1, 2, . . . , m. Let G be a connected graph, and S ⊆ V (G). G[S] denotes the subgraph of G induced by S. If H is a connected induced subgraph of a connected graph G and d H (u, v) = dG (u, v) for u, v ∈ V (H ), then we write H G. In view of Lemma 2.1, we have Lemma 2.2 Let G be a connected graph with H G. Then λ1 (H ) ≥ λ1 (G). 123 On the least distance eigenvalues of the second power of… Suppose that G is a connected graph with V (G) = {v1 , . . . , vn }. A column vector x = (xv1 , . . . , xvn )T ∈ R n can be considered as a function defined on V (G) which maps vertex vi to xvi , i.e. x(vi ) = xvi for 1 ≤ i ≤ n. According to the definition of eigenvalue, λ is a distance eigenvalue corresponding to eigenvector x(x = 0) if and only if λxvi = v j ∈V (G) di j xv j for each vi ∈ V (G). Obviously, the distance eigenvalues of G are the roots of |D(G) − λIn | = 0, where In is the identity matrix of order n. Lemma 2.3 Let G be a connected n-vertex graph, and Vi ⊂ V (G), where |Vi | = ri and i = 1, 2, 3, r1 +r2 +r3 = n. If the induced subgraphs G[V1 ∪ V2 ] and G[V3 ∪ V2 ] are complete, and dG (u, v) = 2 for u ∈ V1 , v ∈ V3 , then λ1 (G) is the least root of the equation fr1 ,r2 ,r3 (λ) = 0, where fr1 ,r2 ,r3 (λ) = λ3 − (n − 3)λ2 − (2n + 3r1r3 − 3)λ + r1r2 r3 − 3r1r3 + 1 − n. Proof Let x be the eigenvector of D(G) corresponding to the eigenvalue λ = λ(G). For any z ∈ V1 , we can get ⎛ λx z = ⎝ ⎞ xu − x z ⎠ + xw + 2 w∈V2 u∈V1 xv . v∈V3 Then we have (λ + 1)x z = u∈V1 xu + w∈V2 xw + 2 xv . v∈V3 Thus, for distinct vertices z, z ∈ V1 , we have (λ + 1)(x z − x z ) = 0. Consider that P3 is the induced subgraph of G, that is P3 G, from Lemma 2.2, we have λ1 (G) ≤ λ1 (P3 ) = −2 = 1. Therefore x z = x z . Similarly, for distinct vertices w, w ∈ V2 and v, v ∈ V3 , it follows that xw = xw and xv = xv . Let u ∈ V1 , w ∈ V2 and v ∈ V3 . Then one has λxu = (r1 − 1)xu + r2 xw + 2r3 xv λxw = r1 xu + (r2 − 1)xw + r3 xv Let A = r1 −1 r2 2r3 r1 r2 −1 r3 2r1 r2 r3 −1 λxv = 2r1 xu + r2 xw + (r3 − 1)xv . Because of the fact that λ is the eigenvalue of the matrix A, we get the characteristic equation fr1 ,r2 ,r3 (λ) = |A − λI3 | = 0. The result follows. 3 The least distance eigenvalues of the square of trees Let Dn,q be n-vertex double star obtained from Sn−q−1 and Sq+1 by connecting the centers of the two stars, where 1 ≤ q ≤ n−2 2 . We have the following lemma. 123 F. He 2 2 Lemma 3.1 Let q be an integer, if 2 ≤ q ≤ n−2 2 , then λ1 (Dn,q−1 ) > λ1 (Dn,q ). Proof Let u, v be the centers of the double star Dn,q , and let V1 , V3 be the neighbors of u, v respectively, where d(w) = 1 for any w ∈ V1 ∪ V3 . From the Lemma 2.3, 2 ) is the least root of the equation f 2 λ1 (Dn,q n−q−2,2,q (λ) = 0. Let λ1 = λ1 (Dn,q ) and 2 λ1 = λ1 (Dn,q−1 ), we have gq (λ) = f n−q−2,2,q (λ) = λ3 − (n − 3)λ2 − (2n + 3qn − 3q 2 − 6q − 3)λ + q 2 − qn + 2q − n + 1. (3.1) Note that gq−1 (λ 1 ) = 0, then gq (λ 1 ) = gq (λ 1 ) − gq−1 (λ 1 ) = (3q 2 + 6q − 3qn)λ 1 + q 2 − qn + 2q − [(3(q − 1)2 + 6(q − 1) − 3n(q − 1))λ 1 + (q − 1)2 − (q − 1)n + 2(q − 1)] = −(n − 1 − 2q)(3λ 1 + 1). 2 . By Lemma 2.2, we get λ 1 ≤ Consider that P4 Dn,q−1 , then P42 Dn,q−1 2 λ1 (P4 ) = −2, that is 3λ1 + 1 < 0. Therefore gq (λ 1 ) > 0 = gq (λ1 ). 2 2 ). ) > λ1 (Dn,q Since gq (x) > gq (λ1 ) for x > λ1 , thus λ 1 > λ1 , i.e., λ1 (Dn,q−1 2 ), the following result is immediate. By the monotonicity of λ1 (Dn,q 2 ) > λ (D 2 ) > · · · > λ (D 2 Corollary 3.2 λ1 (Dn,1 1 1 n,2 n, n−2 2 ). 2 ) < −3 for n ≥ 9, and λ (D 2 ) ≥ −3 for 4 ≤ n ≤ 8. (ii) Lemma 3.3 (i) λ1 (Dn,1 1 n,1 2 2 ) ≥ −3 for n = 4, 5, 6. λ1 (Dn,2 ) < −3 for n ≥ 7, and λ1 (Dn,2 2 ) is the least root of the equation Proof According to Lemma 2.3 and Eq.(3.1), λ1 (Dn,q 3 gq (λ) = 0(q = 1, 2), where g1 (λ) = λ − (n − 3)λ2 − (5n − 12)λ − 2n + 4, g2 (λ) = λ3 − (n − 3)λ2 − (8n − 27)λ − 3n + 9. We know that gq (0) = (q + 1)(q + 1 − n) < 0, gq (−1) = 2q(n − 2 − q) > 0. g2 (−3) = 12n − 72. g1 (−3) = 4n − 32, Obviously, g1 (−3) > 0 for n ≥ 9, and g1 (−3) ≤ 0 for 4 ≤ n ≤ 8. Taking into account the fact that gq (λ) is a polynomial of degree three with respect to λ, we get the least root of the equation g1 (λ) = 0 belongs to (−∞, −3) for n ≥ 9, and [−3, −1) for 4 ≤ n ≤ 8, respectively. Similarly, the result (ii) also follows. 123 On the least distance eigenvalues of the second power of… Suppose that A, B, C and D are m × m, m × n, n × m and n × n matrices, respectively, and D is invertible. The following result is well known. det A B C D = det D · det (A − B D −1 C). (3.2) Let S p+q+1 be a star with the center v0 and the pendant vertices v1 , . . . , vq , vq+1 , . . . , vq+ p , and T p,q be a n-vertex graph obtained from S p+q+1 by attaching a pendant vertex to each vertex of v1 , . . . , vq . Denote by Jm×n and 0m×n the all-one and all-zero m × n matrices, respectively. Let Jm = Jm×m , 1m = Jm×1 , 0m = 0m×1 . 2 ) ≥ −3 Lemma 3.4 Assume that p, q are integers and q ≥ 2, p ≥ 0, then λ1 (T p,q 2 for p + q ≤ 4 or q = 2, p = 3, and λ1 (T p,q ) < −3 for p + q ≥ 5 except in the case of q = 2, p = 3. Proof Let u i be the pendant vertex which is adjacent to vi (i = 1, 2, . . . , q) in the graph T p,q , and let V1 = {vq+1 , vq+2 , . . . , vq+ p }, V2 = {v1 , v2 , . . . , vq }, V3 = {u 1 , u 2 , . . . , u q }. It is clear that v0 ∪ V1 ∪ V2 ∪ V3 = V (T p,q ) and 1 + p + 2q = n. 2 ) is as follows. The characteristic polynomial of D(T p,q −λ 1Tp 1qT 1qT 1 p J p − (λ + 1)I p J p×q 2J p×q 2 det (D(T p,q ) − λIn ) = Jq× p Jq − (λ + 1)Iq 2Jq − Iq 1q 1 2Jq× p 2Jq − Iq 2Jq − (λ + 2)Iq q 1 −1 1Tp −1qT −21qT 0 −λ 1Tp 1qT 1qT = 0 p 1 p J p − (λ + 1)I p J p×q 2J p×q Jq× p Jq − (λ + 1)Iq 2Jq − Iq 0q 1q 0 1 2J 2J − I 2J − (λ + 2)I q q q× p q q q q 1 −1 1Tp −1qT −21qT 0 −λ 1Tp 1qT 1qT = 1 p 0p −(λ + 1)I p 0 p×q 0 p×q 0q 0q× p −(λ + 1)Iq −Iq 1q 0 (2λ + 1)1 0 −I −(λ + 2)I q q q× p q q −1 2(λ + 1) − (2λ + 1)q − 1 −1Tp −1qT 0qT T T T 1 −(λ + 1) 0p 0q −1q = 1p 0p −(λ + 1)I p 0 p×q 0 p×q −(λ + 1)(2λ + 1)1q 0q× p −(λ + 1)Iq −Iq 1q 0 0q 0q× p −Iq −(λ + 2)Iq q = (−λ − 2)q |A − B[−(λ + 2)Iq ]−1 C| = (−λ − 2)q |A + (λ + 2)−1 BC| 123 F. He ⎛ −1 Where A = ⎝ (1−q)(2λ+1) −1Tp −1qT 1 −(λ+1) 0Tp 0qT 1p 0p −(λ+1)I p 0 p×q 1q −(λ+1)(2λ+1)1q 0q× p −(λ+1)Iq ⎠, B ⎞ 0qT ⎜ −1T ⎟ q ⎟ ⎜ ⎝ 0 p×q ⎠ and −Iq ⎛ ⎞ = C = 0q 0q 0q× p −Iq . (−λ − 2)q |A + (λ + 2)−1 BC| −1 (1 − q)(2λ + 1) −1Tp −1qT 1 −(λ + 1) 0Tp 1qT q 1 λ+2 = (−λ − 2) 0p −(λ + 1)I p 0 p×q 1p 1 1 −(λ + 1)(2λ + 1)1 0 [ − (λ + 1)]I q q q× p q λ+2 −1 − p (1 − q)(2λ + 1) −1Tp −1qT λ+1 1 T T 1 −(λ + 1) 0 1 p q q λ+2 = (−λ − 2) 0p 0p −(λ + 1)I p 0 p×q 2 +3λ+1 λ 1q −(λ + 1)(2λ + 1)1q 0q× p − λ+2 Iq λ+ p+1 − (1 − q)(2λ + 1) −1qT λ+1 1 T q p 1 −(λ + 1) 1q = (−λ − 2) (−λ − 1) λ+2 2 1q −(λ + 1)(2λ + 1)1q − λ +3λ+1 Iq λ+2 λ+ p+1 (λ+2)q (λ+2)(λ+1)q − −1qT λ+1 − λ2 +3λ+1 (2λ + 1)[(1 − q) + λ2 +3λ+1 ] q (2λ+1)q q p 1 T 1 + λ2 +3λ+1 −(λ + 1)[1 + λ2 +3λ+1 ] 1 = (−λ − 2) (−λ − 1) q λ+2 λ2 +3λ+1 0q 0q − λ+2 Iq = (−1) p+1 (λ + 1) p (λ2 + 3λ + 1)q−1 f p,q (λ). Where f p,q (λ) = λ3 −( p+3q −3)λ2 −(3 p+2q +2 pq +2q 2 −1)λ−( p+q + pq +q 2 ). √ √ 2 . Since q ≥ 2, therefore −3−2 5 and −3+2 5 must be the distance eigenvalues of T p,q We distinguish the following cases to discuss. Case 1. q = 2, 3, 4. In this case, the polynomial f p,q (λ) can be written respectively by the following forms. f p,2 (λ) = λ3 −( p+3)λ2 −(7 p+11)λ−(3 p+6), f p,3 (λ) = λ3 − ( p+6)λ2 −(9 p+23)λ−(4 p+12), f p,4 (λ) = λ3 −( p+9)λ2 −(11 p+39)λ−(5 p+20). Then we have f p,q (0) = −( p + q + pq + q 2 ) < 0, f p,q (−1) = (q − 1)2 + pq + 1 > 0. f p,2 (−3) = 9 p − 27, f p,3 (−3) = 14 p − 24, f p,4 (−3) = 19 p − 11. It is easy to see that f p,2 (−3) > 0 for p > 3 and f p,2 (−3) ≤ 0 for 0 ≤ p ≤ 3. Notice that f p,2 (λ) is a polynomial of degree three, then the least root of f p,2 (λ) = 0 belongs to [−3, −1) for 0 ≤ p ≤ 3, and (−∞, −3) for p > 3. Similar to the analysis mentioned above, we get the least root of f p,q (λ) = 0 belongs to [−3, −1) for 3 ≤ p + q ≤ 4, and (−∞, −3) for p + q > 4. Case 2. q ≥ 5. We know that f p,q (0) < 0, f p,q (−1) > 0, f p,q (−3) = 5q 2 − 22q − 3 + (5q − 1) p > 0. Hence the least root of f p,q (λ) = 0 belongs to (−∞, −3) for q ≥ 5. 123 On the least distance eigenvalues of the second power of… Let P5 = v1 v2 · · · v5 be a path, we denote by T1 the graph formed by attaching a pendant vertex to v2 of P5 . Theorem 3.5 Let G be a tree with at least two vertices. Then λ1 (G 2 ) ∈ [−3, −2] if and only if (i) G = Dn,1 for 4 ≤ n ≤ 8, or G = Dn,2 for n = 4, 5, 6, or (ii) G = T p,q for p + q ≤ 4 or p = 3, q = 2. Proof If d(G) = 1, 2, then G 2 ∼ = K n . It is well known that the least eigenvalue of K n is equal to −1, thus λ1 (G 2 ) = −1 > −2, a contradiction. If d(G) ≥ 5, then P6 G, implying that P62 G 2 , and by Lemma 2.2, we get λ1 (G 2 ) ≤ λ1 (P62 ) ≈ −3.88 < −3, a contradiction. Therefore d(G) = 3, 4. Since P4 G for d(G) = 3, 4, we have λ1 (G 2 ) ≤ λ1 (P42 ) = −2. For d(G) = 3, it is easy to see that G ∼ = Dn,q , where 1 ≤ q ≤ n−2 2 . If q = 1, 2, then by Lemma 3.3, we arrive at the theorem (i). If q ≥ 3, by Corollary 3.2 and Lemma 3.3(ii), we have λ1 (G 2 ) < −3. For d(G) = 4, it is clear that T1 ⊆ G or G = T p,q ( p ≥ 0, q ≥ 2). In the case of T1 ⊆ G, by Lemma 2.2 and a direct computation, λ1 (G 2 ) ≤ λ1 (T12 ) ≈ −3.12 < −3. For the latter case, applying Lemma 3.4, we get the theorem (ii). 4 The least distance eigenvalues of the square of trees Let Ck = v1 · · · vk v1 be a cycle, and Ck (n 1 , n 2 · · · , n k ) a unicyclic graph obtained from Ck by attaching n i pendant vertices to vi (i = 1, 2 · · · , k). Lemma 4.1 Suppose that r1 , r2 , r3 are integers with r1 ≥ r2 ≥ r3 ≥ 0, and let G = C3 (r1 , r2 , r3 ), G = C3 (r1 , r2 + 1, r3 − 1), where r1 + r2 + r3 + 3 = n and r1 ≥ 1, r2 ≥ 1. Then λ1 (G 2 ) > λ1 (G 2 ). Proof Assume that C3 = v1 v2 v3 v1 is the cycle of the graph G, and denote by Vi the set of pendant vertices which are adjacent to vi (i = 1, 2, 3). Let x be the eigenvector corresponding to λ(λ = −1). For any u ∈ V1 , we have ⎛ λxu = ⎝ p∈V1 ⎞ x p − xu ⎠ + 2 w∈V2 xw + 2 t∈V3 xt + xv . v∈V (C3 ) Therefore, for distinct vertices u, u ∈ V1 , we get (λ + 1)(xu − xu ) = 0. Note that λ = −1, thus xu = xu . Similarly, the result holds for V2 , V3 and V (C3 ). Since V (G) = V1 ∪ V2 ∪ V3 ∪ V (C3 ), then λxu = (r1 − 1)xu + 2r2 xw + 2r3 xt + 3xv λxw = 2r1 xu + (r2 − 1)xw + 2r3 xt + 3xv λxt = 2r1 xu + 2r2 xw + (r3 − 1)xt + 3xv λxv = r1 xu + r2 xw + r3 xt + 2xv 123 F. He r Let A = 1 −1 2r2 2r3 3 2r1 r2 −1 2r3 3 2r1 2r2 r3 −1 3 r1 r2 r3 2 , then the eigenvalue of D(G 2 ) with λ = −1 satisfies gr1 ,r2 ,r3 (λ) = 0, where gr1 ,r2 ,r3 (λ) = |A − λIn | = λ4 − (n − 4)λ3 − 3(n − 2 + r1r2 + r1r3 + r2 r3 )λ2 −(3n − 4 + 3r1r2 + 3r2 r3 + 3r1r3 + 5r1r2 r3 )λ −(n − 1 − r1r2 r3 ). (4.1) Claim 1 λ1 (G 2 ) ∈ [−1 − r1 , −1 − r2 ]. According to Eq.(4.1), we have gr1 ,r2 ,r3 (−1 − r1 ) = r1 (2r1 + 3)(r1 − r2 )(r1 − r3 ) ≥ 0, gr1 ,r2 ,r3 (−1 − r2 ) = r2 (2r2 + 3)(r2 − r1 )(r2 − r3 ) ≤ 0, gr1 ,r2 ,r3 (−1) = 6r1r2 r3 ≥ 0, gr1 ,r2 ,r3 (1) = −8(r1 + r2 + r3 ) − 6(r1r2 − r1r3 − r2 r3 ) − 4r1r2 r3 − 8 < 0. Note that gr1 ,r2 ,r3 (λ) is a polynomial of degree four, then the least root of gr1 ,r2 ,r3 (λ) = 0 belongs to [−1 − r1 , −1 − r2 ]. Let λ1 = λ1 (G 2 ), λ 1 = λ1 (G 2 ). In view of claim 1, we get 1 + r1 ≥ |λ 1 |. Then gr1 ,r2 ,r3 (λ 1 ) = gr1 ,r2 ,r3 (λ 1 ) − gr1 ,r2 +1,r3 −1 (λ 1 ) = −(r2 − r3 + 1)[(5r1 + 3 + 3λ 1 )λ 1 − r1 ] > 0 = gr1 ,r2 ,r3 (λ1 ) Because of the fact that gr1 ,r2 ,r3 (x) > 0 = gr1 ,r2 ,r3 (λ1 ) for x < λ1 , thus λ 1 < λ1 . Lemma 4.2 For all n-vertex graph C32 (r1 , r2 , r3 ), where r1 + r2 + r3 + 3 = n and n−3 r1 ≥ 1, r2 ≥ 1, C32 ( n−3 2 , 2 , 0) is the graph having the minimum least distance eigenvalue. Proof Let G = C3 (r1 , r2 , r3 ). Applying lemma 4.1 for the graph G repeatedly, we can get the graph H p = C3 (n − p − 3, p, 0) with λ1 (H p2 ) < λ1 (G 2 ), where r2 < 2 2 p ≤ n−3 2 . Denote by μ, μ (μ, μ ≤ −2) the least distance eigenvalue of H p , H p−1 , respectively. By (4.1), we have gn− p−3, p,0 (μ ) = gn− p−3, p,0 (μ ) − gn− p−2, p−1,0 (μ ) = 3μ (2 p − n + 2)(μ + 1) < 0 = gn− p−3, p,0 (μ) 2 ) > λ (H 2 ). Therefore λ (H 2 ) > λ (H 2 ) > It implies that μ > μ, i.e., λ1 (H p−1 1 1 1 p 1 2 2 · · · > λ1 (H n−3 ). 2 This complete the proof. Let U p,q be the graph obtained by attaching q pendant vertices to a pendant vertex of C3 ( p + 1, 0, 0), and U the set of unicyclic graphs with triangle. 123 On the least distance eigenvalues of the second power of… Theorem 4.3 Suppose that G ∈ U , and d(G) = 3, then λ1 (G 2 ) ≥ λ1 (U 2n−6 2 , n−2 2 ). Proof Let n = p + q + 4. In view of Lemma 2.3, the least distance eigenvalue of 2 is the least root of the equation f U p,q p+2,2,q (x) = 0, where f p+2,2,q (x) = x 3 + (3 − n)x 2 + (3 − 3 pq − 6q − 2n)x − pq − 2q − n + 1. 2 2 When 1 < q ≤ n−2 2 , it is obtained that λ1 (U p+1,q−1 ) > λ1 (U p,q ) in the same way n−2 n−6 as in Lemma 3.1. Because q = 2 implies p = 2 , then U 2n−6 n−2 is the 2 , 2 2 . graph having the minimum least distance eigenvalue for U p,q Given that G ∈ U and d(G) = 3, we have G ∼ C (r = 3 1 , r2 , r3 ) or G ∼ = U p,q . Let n−3 n−3 2 2 t, t be the least distance eigenvalue of U n−6 n−2 , C3 ( 2 , 2 , 0), respec 2 , 2 tively. By Lemma 2.3, it is true that f n−2 ,2, n−2 (t) = 0, f n−3 ,3, n−3 (t ) = 0. 2 2 2 2 According to Claim 1, t ≤ −1 − n−3 2 , that is, 2t ≤ 2 − n if n is even, and 2t ≤ 1 − n if n is odd. Then f n−2 ,2, n−2 (t ) = f n−2 ,2, n−2 (t ) − f n−3 ,3, n−3 (t ) 2 2 2 2 2 2 0.25(n − 2)(2 − n − 6t ) > 0 (n is even) = 0.25(n − 3)(1 − n − 6t ) > 0 (n is odd) Notice that f n−2 ,2, n−2 (x) > 0 = f n−2 ,2, n−2 (t) for x > t, thus t > t. By 2 2 2 2 combining Lemma 4.2, we obtain the theorem. √ Theorem 4.4 Let G be a unicyclic graph, then λ1 (G 2 ) ∈ (− 3+2 5 , −1] if and only if (i) d(G) ≤ 2 or (ii) d(G) = 3 and G is isomorphic to the following graphs: C3 (1, 1, 1), C3 (1, 1, 0), U0,1 , C4 (1, 0, 0, 0), C4 (2, 0, 0, 0), C5 , C5 (1, 0, 0, 0, 0), C6 . Proof If d(G) ≥ 4, then P5 G. It implies that P52 G 2 , and by Lemma 2.2, √ we get λ1 (G 2 ) ≤ λ1 (P52 ) = − 3+2 5 , a contradiction. Therefore d(G) ≤ 3. If d(G) = 1, 2, then G 2 ∼ = K n , we have λ1 (G 2 ) = −1. If d(G) = 3, then G∼ = C3 (r1 , r2 , r3 ), U p,q , C4 (n 1 , n 2 , 0, 0), C5 (k1 , k2 , 0, 0, 0), C6 , C7 . By Claim 1, the result holds when G ∼ = C3 (1, 1, 1), C3 (1, 1, 0). By direct computation, λ1 (C62 ) = −2, λ1 (C72 ) ≈ −2.8. √ 2 ) ≈ −2.65 < − 3+ 5 . Case 1: G ∼ = U p,q . If U1,1 G, then λ1 (G 2 ) ≤ λ1 (U1,1 2 2 2 By Theorem 4.3, λ1 (U0,2 ) < λ1 (U1,1 ). Therefore, U1,1 and U0,2 are not the induced subgraph of G, it means G ∼ = U0,1 . Case 2: G ∼ = C4 (n 1 , n 2 , 0, 0). If C4 (1, 1, 0, 0) √ G or C 4 (3, 0, 0, 0) G, consid3+ 5 2 ering that λ1 (C4 (1, 1, 0, 0)) = − 2 , λ1 (C42 (3, 0, 0, 0)) ≈ −2.66, then √ λ1 (G 2 ) ≤ − 3+2 5 , a contradiction. By computation, G ∼ = C4 (1, 0, 0, 0), C4 (2, 0, 0, 0). 123 F. He Case 3: G ∼ = C5 (k1 , k2 , 0, 0, 0). In the same way as in case 2, we get C5 (1, 1, 0, 0, 0) and C5 (2, 0, 0, 0, 0) are not the induced subgraph of G. Then G ∼ = C5 , C5 (1, 0, 0, 0, 0). In fact, it is true by computation. Based on the above discussion, it follows the theorem. References 1. Aouchiche, M., Hansen, P.: Distance spectra of graphs: a survey. Linear Algebra Appl. 458, 301–386 (2014) 2. Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer, New York (2008) 3. Das, K.C., Guo, J.M.: Laplacian eigenvalues of the second power of a graph. Discrete Math. 313, 626–634 (2013) 4. Gutman, I., Medeleau, M.: On the structure-dependence of the largest eigenvalue of distance matrix of an alkane. Indian J. Chem. A 37, 569–573 (1998) 5. Hajiabolhassan, H.: On colorings of graph powers. Discrete Math. 309, 4299–4305 (2009) 6. Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1990) 7. Ilic, A.: Distance spectral radius of trees with given matching number. Discrete Appl. Math. 158, 1799–1806 (2010) 8. Lau, L.C., Corneil, D.G.: Recognizing powers of proper interval, split and chordal graphs. SIAM J. Discrete Math. 18, 83–102 (2004) 9. Liang, Y.J., Zhou, B.: On the distance spread of cacti and bicyclic graphs. Discrete Appl. Math. 206, 195–202 (2016) 10. Lin, H.: On the least distance eigenvalues and its applications on the distance spread. Discrete Math. 338, 868–874 (2015) 11. Lin, H.Y., Zhou, B.: On least distance eigenvalues of trees, unicyclic graphs and bicyclic graphs. Linear Algebra Appl. 443, 153–163 (2014) 12. Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21, 193–201 (1992) 13. Merris, R.: The distance spectrum of a tree. J. Graph Theory 14, 365–369 (1990) 14. Mihalic, Z., Veljan, D.: The distance matrix in chemistry. J. Math. Chem. 11, 223–258 (1992) 15. Ruzieh, S.N., Powers, D.L.: The distance spectrum of the path Pn and the first distance eigenvector of connected graphs. Linear Multilinear Algebra 28, 75–81 (1990) 16. Sander, J.W., Sander, T.: On the eigenvalues of distance powers of circuits. Linear Algebra Appl. 432, 3132–3140 (2010) 17. Stevanovic, D., Ilic, A.: Distance spectral radius of trees with fixed maximum degree. Electron. J. Linear Algebra 20, 168–179 (2010) 18. Xing, R.D., Zhou, B.: On the two largest distance eigenvalues of graph powers. Inf. Process. Lett. 119, 39–43 (2017) 19. Yu, G.: On the least distance eigenvalue of a graph. Linear Algebra Appl. 439, 2428–2433 (2013) 20. Zhang, X.L., Godsil, C.: Connectivity and minimal distance spectral radius of graphs. Linear Multilinear Algebra 59, 745–754 (2011) 21. Zhou, B., Ilic, A.: On distance spectral radius and distance energy of graphs. MATCH Commun. Math. Comput. Chem. 64, 261–280 (2010) 123

1/--страниц