# The Spectral Radius for a Class of Double-Star-Like Tree Systems with Maximal Degree 4

Authors: Yufeng Mao; Meijin Xu; Xiaodong Chen; Yan-Jun Liu; Kai Li
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

We mainly study the properties of the 4-double-star-like tree, which is the generalization of star-like trees. Firstly we use graft transformation method to obtain the maximal and minimum extremal graphs of 4-double-star-like trees. Secondly, by the relations between the degree and second degree of vertices in maximal extremal graphs of 4-double-star-like trees we get the upper bounds of spectral radius of 4-double-star-like trees.


---

## Body

## 1. Introduction

In recent years, there are a lot of the results of the upper and lower bounds on the spectral radius of graphs. For example, Ellingham and Zha [1] proposed upper bound on the spectral radius of graphs embeddable on a given compact surface; Wang et al. [2] proved that k trees have the second and the third largest spectral radius; Gong [3] discussed some sharp lower bounds for spectral radius of connected graphs and gave a new lower bound for spectral radius; Yuan and Shu [4] gave upper bound for the spectral radius of Halin graphs; Zhou and Xu [5] showed the upper bounds for the Laplacian spectral radius of a graph by using the Cauchy-Schwarz inequality; Song and Wang [6, 7] got the upper bound of the Laplacian spectral radius of some trees by grafting transformation.Star-like tree and its generalizationm-star-like tree are special trees and widely used in computer science. There are a lot of results on the bounds of spectral radius of star-like trees and m-star-like trees. For example, Patuzzi et al. [8] gave upper bounds of the spectral radius in star-like trees and double brooms; Aalipour et al. [9] obtained upper bound of double-star-like trees by Laplacian spectral; Wu and Hu [10] gave new upper bound of the spectral radii of m-star-like trees.Though many researchers obtained the bounds of spectral radius of star-like trees andm-star-like trees, few used the extremal graphs of the two kinds of trees to get the bounds. In this paper, we mainly use graft transformation method to obtain the maximal and minimum extremal graphs of 4-double-star-like trees. Then by the relations between the degree and second degree of vertices in maximal extremal graphs of 4-double-star-like trees we get the upper bounds of spectral radius of 4-double-star-like trees. Ours result provide a new method to research the bound of spectral radius of m-star-like trees. By this new method, we may get the second largest index, the third largest index, or the kth largest index of m-star-like trees, which provide a valuable tool for further research on m-star-like trees.


## 2. Preliminaries

In this paper, all graphs considered here are simple and undirected. We refer to [11] for notation not defined here. Let A(G) be the adjacent matrix of graph G. Since A(G) is a real symmetric matrix, its eigenvalues must be real, and let λ1,λ2,…,λn denote the eigenvalues with λ1≥λ2≥⋯≥λn. The sequence of n eigenvalues of A(G) is named the spectrum of G, and the spectral radius of G often calls the largest eigenvalue λ1(G) and is denoted by ρ(G). The characteristic polynomial of A(G) is called the characteristic polynomial of the graph G and is denoted by Φ(G). When G is connected, A(G) is an irreducible matrix. And by Perron-Frobenius theorem [12], ρ(G) is simple and the correspondent eigenvector can be positive. We refer to such eigenvector as Perron vector of G.An internal path in a graph, denoted byv0,v1,…,vk(k≥1), is a path joining vertices v0 and vk which are both of degree greater than 3, while all other vertices are of degree equal to 2.If graphG with n vertices has exactly two vertices of degree greater than two, then G is double-star-like [13]. A double-star-like tree graph of order n that has exactly two vertices with maximum degree 4 is called 4-double-star-like tree, and it is denoted by T42(n). The degree sum of vertices adjacent to v is called the second degree of v, remarked as T(vi) [4].In this paper, we denote byCn and T3(n) the cycle with order n and the third small spectral radius of tree. Γ42(n) denotes the family of the 4-double-star-like tree. Let d(v) denote the degree of v. The sum of entries in the ith row of A is called Si(A).Zhou and Xu [5] proved the following.LetG=(V,E) be a simple graph with n vertices and m edges, and then(1)ρG≤Δ′+δ-1+Δ′+δ-1+4Δ2-Δ·Δ′+4m-2n-1δ1/2×2-1with equality if and only if G is a regular bipartite graph.Wu and Hu [10] gave a new upper bound of the spectral radii of m-star-like trees. They show the following result:(2)ρGS0,S1,S2,…,SΔ0<2Δ-12Δ-22Δ-2.In this paper, we consider the extremal graphs and the upper bounds of the spectral radius of 4-double-star-like trees. The rest of the paper is organized as follows. Section3 contains some useful lemmas which play a fundamental role. Section 4 contains three theorems on the 4-double-star-like trees.


## 3. Some Useful Lemmas

In this section, we use the following lemmas about the connected graph to prove our main results.Lemma 1 (see [14]).
Letuv be an edge of a connected graph G with order n, and Gu,v denote the graph obtained from G by subdividing the edge uv by a new vertex w. Then the following two properties hold:(1)
Ifuv is not on any internal path of G≇Cn, then ρ(Gu,v)>ρ(G).(2)
Ifuv is on an internal path of G≇T3(n), then ρ(Gu,v)<ρ(G).Lemma 2 (see [15]).
Letv be a vertex of a connected graph G with d(v)>0 and, for positive integers i and j, let Gi,j denote the graph got from G by adding two pendent paths of length i and j at v. If i≥j≥1, then ρ(Gi,j)>ρ(Gi+1,j-1).Lemma 3 (see [15]).
LetG be a connected graph with a,b∈E(G) and deg⁡a>1 and deg⁡b>1, and let Gi,j(1) be the graph obtained from G by adding two pendent paths of Pi and Pj at a,b. If i≥j≥1 and x≥ρGi+1,j-11, then ΦGi,j1,x<Φ(Gi+1,j-1(1),x) and ρGi,j1>ρGi+1,j-11.From the above lemma we immediately get the following.Corollary 4.
LetT42n be a 4-double-star-like tree. As shown in Figure 1, when two centers are adjacent, T42n is denoted by T42(i1,i2,i3,1,i4,i5,i6) with i1+i2+i3+i4+i5+i6+2=n and i1>i4, where i1,i2,i3,i4,i5,i6 denote the length of the 6 branches of the 4-double-star-like tree in clockwise direction, respectively. Then, by the graft transformation, we get a graph, as shown in Figure 2 denoted by T42(i1+1,i2,i3,1,i4-1,i5,i6). Then (3)ρT42i1,i2,i3,1,i4,i5,i6>ρT42i1+1,i2,i3,1,i4-1,i5,i6.Figure 1
T
4
2
(
i
1
,
i
2
,
i
3
,
1
,
i
4
,
i
5
,
i
6
).Figure 2
T
4
2
(
i
1
+
1
,
i
2
,
i
3
,
1
,
i
4
-
1
,
i
5
,
i
6
).Lemma 5 (see [1]).
LetG be a connected graph with order n and spectral radius ρ and A denote its adjacency matrix. Let f be any polynomial. Then(4)minv∈VG⁡SvfA≤fρ≤minv∈VG⁡SvfA.
Furthermore, if the sum of all entries in each row off(A) are not all the same, then the inequalities are strict.The following result provides a very effective method which can affect the value of spectral radius.Lemma 6 (see [2]).
Supposeu,v are two vertices of a graph G, u1,u2,…,us∈N(u)∖N(v)(1≤s≤d(u)), and x=(x1,x2,…,xn) is the Perron vector of A(G), where xi corresponds to the vertex ui(1≤i≤n). Let G∗ be the graph obtained from G by deleting the edges u,ui and adding the edges v,ui1≤i≤s. If xv≥xu, then ρG<ρG∗.The processes depicted in Lemma6 are called graft transformation.


## 4. Main Results

In this section, we consider 4-double-star-like tree withn vertices. The main result of the paper is the following theorem.Theorem 7.
The minimal extremal graph of 4-double-star-like tree isT42(1,n-6,1)1 (as shown in Figure 3); namely, (5)ρT42n≥ρT421,n-6,11.Figure 3
T
4
2
(
1
,
n
-
6,1
)
1.Proof.
LetT42(n)∈Γ42(n), as shown in Figure 4. By Lemma 2, we are using the graft transformation to obtain the graph, as shown in Figure 5, denoted by T42(n)1, and, then, (6)ρT42n≥ρT42n1.
Supposep′, q′, and r′ and p, q, and r are positive integers. For the convenience of proof, we use T42(p′,q′,r′) and T42(p,q,r)1 to denote T42(n) and T42(n)1, respectively. p′, q′, and r′ denote the number of the vertices of three parts as shown in Figure 4. Similarly, p, q, and r play the same role in Figure 5.
Obviously,T42p,q,r1 is a subdivision of external of T42p-1,q,r1, and then, by using Lemma 1, we have(7)ρT42p,q,r1≥ρT42p-1,q,r1.
As shown in Figure6, T42p-1,q+1,r1 is a subdivision of internal T42p-1,q,r1, and, by Lemma 1, we have(8)ρT42p-1,q,r1≥ρT42p-1,q+1,r1.By (7) and (8),(9)ρT42p,q,r1≥ρT42p-1,q+1,r1.Proceeding in this way, we have(10)ρT42p-1,q+1,r1≥ρT42p-2,q+2,r1,ρT42p-2,q+2,r1≥ρT42p-3,q+3,r1,⋮ρT421,p+q-1,r1≥ρT421,p+q+r-2,11.Thus(11)ρT42p,q,r1≥ρT421,p+q-1,r1≥ρT421,p+q+r-2,11.
As shown in Figure7, T421,p+q+r-2,11 is the minimum extremal graphs of 4-double-star-like tree, and p+q+r-2=n-6, shortened to T421,n-6,11.Figure 4
T
4
2
n.Figure 5
T
4
2
n
1.Figure 6
T
4
2
p
-
1
,
q
+
1
,
r
1.Figure 7
T
4
2
1
,
p
+
q
+
r
-
2,1
1.Theorem 8.
The maximum extremal graph of 4-double-star-like tree isT42a1,a2,a3,1,a4,a5,a6 (as shown in Figure 8), where a1,a2,…,a6 are almost equal in length; namely, the length of each branch differs at most 1: (12)ρT42n≤ρT42a1,a2,a3,1,a4,a5,a6.Figure 8
T
4
2
a
1
,
a
2
,
a
3
,
1
,
a
4
,
a
5
,
a
6.Proof.
LetT42n∈Γ42n, as shown in Figure 9.
Obviously,T42p,q,r is a subdivision of internal T42p,q-1,r, and, by Lemma 1, we can get(13)ρT42p,q-1,r≥ρT42p,q,r.
Then, as shown in Figure10, T42p+1,q-1,r is a subdivision of external T42p,q-1,r, and, by Lemma 1, we can get (14)ρT42p+1,q-1,r≥ρT42p,q-1,r.
By (13) and (14), we can get(15)ρT42p+1,q-1,r≥ρT42p,q,r.
Proceeding in this way untilq=2, we get T42p+q-2,2,r, which can be denoted in the form of T42i1,i2,i3,1,i4,i5,i6 as in Corollary 4. The value of spectral radius is largest when i1,i2,i3,i4,i5,i6 equal a1,a2,a3,a4,a5,a6 and a1,a2,…,a6 are almost equal in length, and then we get T42a1,a2,a3,1,a4,a5,a6, as shown in Figure 11.
Whenn=11, there are 6 different 4-double-star-like trees (as shown in Figure 12). By calculating the spectral radius of the 6 graphs, we can see that Theorem 8 holds for the 6 graphs:(16)ρT1,5,1=2.1753,ρT1,4,2=2.2262,ρT1,3,3=2.2738,ρT1,2,4=2.3459,ρT2,2,3=2.3700,ρT2,3,2=2.2882,and then(17)ρT2,2,3>ρT1,2,4>ρT2,3,2>ρT1,3,3>ρT1,4,2>ρT1,5,1.Figure 9
T
4
2
n.Figure 10
T
4
2
p
+
1
,
q
-
1
,
r.Figure 11
T
4
2
p
+
q
-
2,2
,
r.Figure 12
T
4
2
11.Theorem 9.
The upper bound of spectral radius of the 4-double-star-like trees is1+5; namely,(18)ρTj,k,l,m≤1+5.Proof.
By the definition of 4-double-star-like tree we can get(19)Tvi-2dvi=2,Tvj-2dvj=0,Tvk-2dvk=-1,Tvm-2dvm=-3,Tvn-2dvn=4.
LetA be the adjacent matrix of T42(n). Since the sum of entries in the ith row of A is dvi, SiA=dvi. Since the sum of entries in the ith row of A2 is Tvi, SiA2=Tvi.
By (19) we obtain(20)SiA2-2×SiA≤4.Suppose fx=x2-2x. By Lemma 5, we have(21)ρ2-2ρ≤4.Thus(22)ρ≤1+5.Now, we complete the proof of Theorem 9.


## 5. Conclusion

In this paper we have shown some results of the 4-double-star-like trees. We obtain the minimal and the maximum extremal graphs of 4-double-star-like tree beingT421,n-6,11 and T42a1,a2,a3,1,a4,a5,a6, and then we get the upper bound of spectral radius of the 4-double-star-like trees, which is 1+5.



---

*Source: 529024-2015-11-12.xml*