close

Вход

Забыли?

вход по аккаунту

?

s12190-017-1139-7

код для вставкиСкачать
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
Документ
Категория
Без категории
Просмотров
0
Размер файла
386 Кб
Теги
1139, 017, s12190
1/--страниц
Пожаловаться на содержимое документа