# On the Maximal-Adjacency-Spectrum Unicyclic Graphs with Given Maximum Degree

Authors: Haizhou Song; Lulu Tian
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

In this paper, we study the properties and structure of the maximal-adjacency-spectrum unicyclic graphs with given maximum degree. We obtain some necessary conditions on the maximal-adjacency-spectrum unicyclic graphs in the set of unicyclic graphs withn vertices and maximum degree Δ and describe the structure of the maximal-adjacency-spectrum unicyclic graphs in the set. Besides, we also give a new upper bound on the adjacency spectral radius of unicyclic graphs, and this new upper bound is the best upper bound expressed by vertices n and maximum degree Δ from now on.


---

## Body

## 1. Introduction

The spectral theory of graphs was established in the 1940s and 1950s. It is a branch of mathematics that is widely applied, and itis a powerful tool for solving problems in discrete mathematics. Many of the early results were related to the relationship between the spectrum and the structural properties of a graphs [1–4]. The spectral theory of graphs has been widely used in quantum theory, chemistry, physics, computer science, the theory of communication networks, and information science. Along with the continuous research of the spectral theory of graphs, applications of the spectral theory of graphs have also been found in the fields of electrical networks and vibration theory [5, 6].Not only has the spectral theory of graphs pushed forward and enriched research into combinatorics and graph theory but also it has been widely used in quantum theory, chemistry, physics, computer science, the theory of communication networks, and information science. The wide range of application of the spectral theory of graphs has led to the spectral theory of graphs becoming a very active field of research over the last thirty to forty years, and large numbers of results are continuously emerging.There are many results on the adjacency spectral radius for different classes of graphs. Guo et al. [7] have studied the largest and the second largest spectral radius of trees with n vertices and diameter d. Guo and Shao [8] have studied the first ⌊d/2⌋+1 spectral radii of graphs with n vertices and diameter d. Petrovic et al. [9, 10] have studied the spectral radius of unicyclic and bicyclic graphs with n vertices and k pendant vertices. Guo et al. [11, 12] have studied the spectral radius of unicyclic and bicyclic graphs with n vertices and diameter d.LetT=V,E be a connected graph with edge set E and vertex set V. In this paper, we denote by u,v a edge of E, where u∈V,v∈V. Denote the maximum degree of vertex of T by ΔT. For convenience, we shall sometimes denote ΔT simply by Δ. Denote the degree of vertex v by dv. Denote by NTv the set which consists of the vertices adjacent to vertex v in T. Denote by du,v the shortest distance between vertex u and vertex v. Denote by ρT the adjacency spectral radius of T. If T=V,E is a connected graph with n vertices, where V is the vertex set of T, E is the edge set of T, and E=n, then T is called a unicyclic graph. We denote the set which consists of the unicyclic graphs with n vertices and maximum degree Δ by TnΔ.In this paper, we study further the properties and structure of the maximal-adjacency-spectrum unicyclic graphs in the set of unicyclic graphs withn vertices and the maximum degree Δ, where Δ≥3. Besides, we study the new upper bound on the adjacency spectral radius of unicyclic with n vertices and the maximum degree Δ.Suppose thatT∗∈TnΔ, then we obtain some necessary conditions about that T∗ is maximal-adjacency-spectrum unicyclic graph in TnΔ using the following theorems.Theorem 1.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, if x=x1,x2,…,xnT is the Perron vector of T∗, then the degree of the vertices that corresponds to all largest components in the component of x is Δ.Theorem 2.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ and the only circle in T∗ is C, x=x1,x2,…,xnT is the Perron vector of T∗; if the component xu∗ which corresponds to the vertex u∗ in x satisfies that xu∗=max1≤i≤nxi, then u∗∈VC.Theorem 3.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, if the only circle in T∗ is C, and there exists a nonfull internal vertex in the set of VT∗\VC, then the number of all the nonfull internal vertices of T∗ is one.Theorem 4.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, let C be the only circle in T∗ and VC=3, if there is no nonfull internal vertex in the set of VT∗\VC, then both the following propositions are established:(1)
The number of the nonfull internal vertex inVC is at most 2.(2)
When the number of nonfull internal vertex inVC is 2, then there is at least one vertex with degree 2 in the two nonfull internal vertices in VC.Theorem 5.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. If the only circle in T∗ is C, there is no nonfull internal vertex in the set of VT∗\VC, and the number of the nonfull internal vertex in the set of VC is equal to or greater than 2, then the length of the circle is 3, that is, VC=3.Theorem 6.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, if C is the only circle in T∗, then VC=3.Theorem 7.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, and let r be the vertex that corresponds to a maximum component in the component of the Perron vector of T∗. T∗ is the rooted unicyclic graph with root node r, let C be the only circle in T∗, and VC=r,g1,g2. Let du,v be the shortest distance between vertex u and vertex v in T∗, denote that W1 = {ii is the leaf node of T∗, and the shortest path from i to r neither pass g1 nor pass g2}, W2 = {ii is the leaf node of T∗, and the shortest path from i to r either pass g1 or pass g2}, then the following propositions are established:(1)
IfW2=∅, then maxi∈W1di,r=1.(2)
Ifdg1=2, then for the arbitrary leaf node i in T∗, we all have 1−di,r≤1.Ifdg2=2, then for the arbitrary leaf node i in T∗, we all have 1−di,r≤1.(3)
IfW2≠∅, then for the arbitrary leaves i,j in T∗, we all have di,r−dj,r≤1.(4)
IfW2≠∅, then mini∈W2di,r≥maxj∈W1dj,r.(5)
IfW2≠∅ and there exists a vertex with degree 2 in VC, then T∗ is the rooted unicyclic graph with 3 levels, and for ∀j∈W1, we all have dj,r=1.Theorem 8.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, x=x1,x2,…,xnT is the Perron vector of T∗, r is the vertex that corresponds to a maximum component in the component of the Perron vector of T∗. Let T∗ be the rooted unicyclic graph with root node r, then T∗ is an almost full-degree unicyclic graph with root node r.Theorem 9.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, x=x1,x2,…,xnT is the Perron vector of T∗, r is the vertex that corresponds to a maximum component in the component of the Perron vector of T∗, and T∗ is the rooted unicyclic graph with root node r, T∗ has only one nonfull internal vertex u. Suppose that C is the only one circle in T∗, and VC=r,g1,g2, denote that W1 = {ii is the leaf node of T∗, and the shortest path from i to r neither pass g1 nor pass g2}, W2 = {ii is the leaf node of T∗, and the shortest path from i to r either pass g1 or pass g2}. Assume that T∗≇Tn,2Δ, that is, W2≠∅, then the following propositions are established:(1)
If the distances from all leaves ofT∗ to r are all equal, then there exists a leaf node i∈W1 which makes i,u is a pendant edge.(2)
If there are two leavesi,j in T∗ which make di,r≠dj,r and maxi∈W1di,r=mini∈W1di,r, then either there exists a leaf node j1∈W2, which makes u,j1 is a pendant edge or u∈VC and du=2.(3)
Ifmaxi∈W1di,r≠mini∈W1di,r, then there exists a leaf node j1∈W1, which makes u,j1 is a pendant edge.Finally, we obtain the main result of this paper in the following theorem.Theorem 10.
Suppose thatT∗∈TnΔ, and T∗ is a rooted unicyclic graph with root vertex which is the vertex that corresponds to a maximum component in the component of the Perron vector of T∗, then T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ if and only if T∗≅HnΔ.That is, we describe the structure of the maximal-adjacency-spectrum unicyclic graphs inTnΔ. In addition, we give a new upper bound on the adjacency spectral radius of unicyclic graphs on the basis of Theorem 10.In the following discussion of this paper, we assume thatΔ the maximum degree of unicyclic graphs satisfies Δ≥3.


## 2. Preliminaries

### 2.1. Some Basic Concepts

A rooted unicyclic graph is a simple nonlinear structure. Figure1 shows a rooted unicyclic graph with root node R.Figure 1
A rooted unicyclic graph.We can divide a rooted unicyclic graph into levels according to the following principles.The root nodes are in the first level. For instance, in the rooted unicyclic graph with root nodeR shown in Figure 1, R is in the first level. In a rooted unicyclic graph, the level which arbitrary vertex is defined as the shortest distance from the vertex to the root node adds 1; for instance, in the rooted unicyclic graph with root node R shown in Figure 1, the vertices A,C,D,E are in the second level, the vertices B,F,G,J,K,L,M,N,O,P,Q are in the third level, and the vertices H,I,V,S are in the fourth level. The levels of a rooted unicyclic graph are defined as the maximum of the levels of all the vertices in the rooted unicyclic graph. For instance, the level of the rooted unicyclic graph shown in Figure 1 is 4.Assume thatT is a rooted unicyclic graph, R is the root node of T and u is an arbitrary vertex which is not equal to R in T. Suppose that the shortest path from u to R is u1u2⋯uk, where u1=u,k≥2,uk=R, then we call u2 is a father vertex of u. For instance, in the rooted unicyclic graph with root node R shown in Figure 1, the shortest path from vertex F to vertex R is FAR, A is a father vertex of F. The shortest paths from vertex B to vertex R are BARandBCR, respectively; therefore, A and C are both father vertices of B.LetT be a rooted unicyclic graph, if u and v are two different vertices of T, and u,v have the same father vertex, then u is called a brother of v. If w1 and w2 are two different vertices in the same level in T, and the father vertex of w1 is not equal to the father vertex of w2, then w1 is called a cousin of w2. For instance, in the rooted unicyclic graph with root node R shown in Figure 1, vertex L≠M, L, and M have the same father vertex D; therefore, L is a brother of M. Besides, vertices L,Q are two vertices in the same level in T, and the father vertex of L is not equal to the father vertex of Q; therefore, L is a cousin of Q.The vertices (exceptu) on the shortest path that connects the root node to vertex u are called the direct ancestor of the vertex u. For instance, in the rooted unicyclic graph with root node R shown in Figure 1, the shortest path from the root node R to the vertex M is RDM; therefore, R and D are both the direct ancestors of M.Assume thatuandv are two different vertices in the rooted unicyclic graph T, the level of the vertex u in T is k1 and the level of the vertex v in T is k2, where k2<k1 and v is not the direct ancestor of u, then we call v is a collateral ancestor of u. For instance, in the rooted unicyclic graph with root node R shown in Figure 1, the level of vertex L in T is 3, the level of vertex E in T is 2, and E is not the direct ancestor of L; therefore, vertex E is the collateral ancestor of vertex L.Suppose thatT is a rooted unicyclic graph, if vertex v and vertex w are both direct ancestors of vertex u, and the level of vertex v in T is larger than the level of vertex w in T, then the generation of vertex v to u is closer than the generation of vertex w to vertex u. For instance, in the rooted unicyclic graph with root node R shown in Figure 1, the shortest path from vertex R to vertex Q is REQ, vertices RandE are both direct ancestors of Q, the root node R is in the first level, and vertex E is in the second level; therefore, the generation of vertex E to Q is closer than the generation of vertex R to vertex Q.Ifm≥2, and for any number i which satisfies 1≤i≤m, we all have that p is a direct ancestor of ui, then p is called a common direct ancestor of u1,u2,…,um. For instance, in the rooted unicyclic graph with root node R shown in Figure 1, E is both the direct ancestor of O and the direct ancestor of S; therefore, E is a common direct ancestor of OandS.Ifm≥2, p is a common direct ancestor of u1,u2,…,um, and q which is the arbitrary direct ancestor of u1,u2,…,um satisfies that q is either equal to p or the direct ancestor of p, then p is called the common direct ancestor of u1,u2,…,um of the nearest generation. For instance, in the rooted unicyclic graph with root node R shown in Figure 1, A is the common direct ancestor of F,I of the nearest generation.Letv,w be two cousins of u, if the common direct ancestor of u and w of the nearest generation is the common direct ancestor of u and v of the nearest generation, then v is the cousin of u with generation closer than w. For instance, in the rooted unicyclic graph with root node R shown in Figure 1, HandS are two cousins of V, and the common direct ancestor of V and H of the nearest generation is A, the common direct ancestor of V and S of the nearest generation is R, and R is the ancestor of A; therefore, H is the cousin of V generation closer than S.In order to give the main results of this paper, we introduce some basic definitions and lemmas.


### 2.2. Some Definitions

Definition 1.
Suppose thatT∗∈TnΔ, if for any T∈TnΔ all have that ρT≤ρT∗ establish, then T∗ is called a maximal-adjacency-spectrum unicyclic graph in TnΔ.Definition 2.
Suppose thatk≥2 and v0,v1,…,vk are vertices different from each other in graph T, if dv0≥3,dvk≥3, and for any natural number i which satisfies 1≤i≤k−1 all have dvi=2, then v0v1…vkk≥2 a path of graph T is called an internal path of graph T.Definition 3.
Suppose thatT=V,E is a unicyclic graph, and the degree of T is ΔΔ≥3, v∈V is called a nonfull vertex of T, which means v satisfies 2≤dv<Δ.Definition 4.
Suppose thatT=V,E is a simple connected graph with n vertices, the vertices in T with degree 1 are called the pendant point of T, or call that vertex in the leaf node of T; for convenience, the leaf node of T is sometimes simply called leaf node of T. The edge associated with the pendant point is called pendant edge.Definition 5.
Suppose thatT=V,E is a unicyclic graph, and the maximum degree of T is ΔΔ≥3, if T satisfies or T≅Tn,2Δ, where Tn,2Δ is shown in Figure 2, and r is the root node of Tn,2Δ. Or T is a rooted unicyclic graph with levels more than two, and T satisfies the following properties:(1)
The vertex in the first level isr, and r is the root node of T; the vertices in the second level from left to right are v1,v2,…,vΔ.(2)
Suppose that the only circle inT is C, and VC=r,v1,v2.(3)
The internal vertices ofT are all full-degree vertices.(4)
The distance from all the leaf node nodes ofT to r is equal.
Then,T is called a completely full Δ degree unicyclic graph.Figure 2
A completely full Δ degree unicyclic graph with levels 2.Definition 6.
SupposeT=V,E is a unicyclic graph, and the maximum degree of T is ΔΔ≥3, if T satisfies or that T≅Tn,2Δ, where Tn,2Δ is shown in Figure 2, and r is the root node of Tn,2Δ. Or T is a completely full Δ degree unicyclic graph with levels more than two. Or T is a rooted unicyclic graph obtained from another completely full Δ degree unicyclic graph with levels more than two by deleting some right leaf nodes. Then, T is called an almost completely full Δ degree unicyclic graph. We denote the almost completely full Δ degree unicyclic graph with n vertices and maximum degree Δ by HnΔ.Definition 7.
Suppose thatT=V,E is a unicyclic graph, and the maximum of T is ΔΔ≥3, if T satisfies or T≅Tn,2Δ, where Tn,2Δ is shown in Figure 2, and r is the root node of Tn,2Δ. Or T∗≅Tn,3Δ, where Tn,3Δ=VTn,3Δ,ETn,3Δ,VTn,3Δ=r,v1,v2,…,vΔ,w1,w2,…,ws (where s is the number which satisfies that s+2≤Δ), ETn,3Δ=r,v1,r,v2,v1,v2,r,v3,…,r,vΔ,v1,w1,…,v1,ws, and r is the root node of Tn,3Δ. or T is a rooted unicyclic graph with k levels, and T satisfies the following properties:(1)
k≥3.(2)
The vertex in the first level isr, and r is the root node of T; the vertices in the second level from left to right are v1,v2,…,vΔ.(3)
Suppose that the only circle inT is C, and VC=r,v1,v2.(4)
There is at most one nonfull internal vertex inT.(5)
When there is only one nonfull internal vertex inT, this nonfull internal vertex is in the k−1 level of T.
Then,T is an almost full Δ degree unicyclic graph with root node r.
From the definitions above, we know that completely fullΔ degree unicyclic graph is the special situation of almost completely full Δ degree unicyclic graph. completely full Δ degree unicyclic graph and almost completely full Δ degree unicyclic graph are both special situations of almost full Δ degree unicyclic graph. For convenience, in this paper, we denote completely full Δ degree unicyclic graph, almost completely full Δ degree unicyclic graph, almost full Δ degree unicyclic graph by completely full-degree unicyclic graph, almost completely full-degree unicyclic graph, and almost full-degree unicyclic graph, respectively.
For instance, suppose that the unicyclic graph shown in Figure3(a) is a rooted unicyclic graph with root node r, then the rooted unicyclic graph shown in Figure 3(a) is a completely full 3 degree unicyclic graph with levels 3, maximum degree 3, and root node r. Suppose that the root node of the unicyclic graph shown in Figure 3(b) is r, then the rooted unicyclic graph shown in Figure 3(b) is an almost completely full 4 degree unicyclic graph with levels 4, maximum degree 4, and root node r. Suppose that the root node of the unicyclic graph shown in Figure 3(c) is r, then the rooted unicyclic graph shown in Figure 3(c) is an almost full 4 degree unicyclic graph with levels 4, maximum degree 4, and root node r.
In order to give the main results of this paper, we give some lemmas.Figure 3
Some unicyclic graphs with roots.
(a)(b)(c)


### 2.3. Some Lemmas

Now, we give some lemmas which we use to proof the main results.Lemma 1 (see [13]).
Suppose thatT is a simple connected graph with n vertices and maximum Δ, x=x1,x2,…,xnT is the Perron vector of T, xuandxv correspond to vertices uandv, respectively, and xu≥xv. If w∈NTv\u, let T1=T−v,w+u,w, if T1 is still a simple connected graph, then ρT1>ρT.Lemma 2 (see [13]).
Suppose thatT is a simple connected graph with n vertices and maximum Δ, x=x1,x2,…,xnT is the Perron vector of T, xuandxv correspond to vertices uandv, respectively, and xu≥xv. Suppose that w1∈NTv\u,w2∈NTV\u,…,wk∈NTv\u. Let T1=T−v,w1−v,w2−⋯−v,wk+u,w1+u,w2+⋯+u,wk, T1 and T are shown in Figure 4. If T1 is still a simple connected graph, then ρT1>ρT.Figure 4
Transition deformation of graphs.Lemma 3 (see [13]).
Suppose thatT=V,E is a simple connected graph with n vertices and maximum Δ, x=x1,x2,…,xnT is the Perron vector of T, and suppose that xu1,xu2,xv1,andxv2 correspond to the four different vertices u1,u2,v1,andv2, respectively, where u1,u2∈E,v1,v2∈E and xu1≥xv1,xu2<xv2. Let T1=T−u1,u2−v1,v2+u1,v2+v1,u2, T1 and T are shown in Figure 5; if T1 is still a simple connected graph, then ρT1>ρT.Figure 5
Cross deformation of graphs.Lemma 4 (see [14]).
Suppose thatT=V,E is a simple connected graph, and v0v1⋯vkk≥2 is an internal path of T. If T1=T−vi−1vi−vivi+1+vi−1vi+1, where 1≤i≤k−1, then ρT1≥ρT.Lemma 5 (see [13]).
Suppose thatT=VT,ET is a connected graph, if u∈VTandv∉VT, let T1=T+u,v, then ρT1>ρT.Lemma 6.
Assume thatT∈TnΔ, the edge set of T is ET, and C is the only circle in T. Suppose that VC=u1,u2,…,ul, where l≥4, and for any natural number i which satisfies 1≤i≤k−1, we all have ui,ui+1∈ET,ul,u1∈ET, denote ul+1=u1,ul+2=u2,…,u2l=ul. Suppose that x=x1,x2,…,xnT is the Perron vector of T, r1,r2,…,rk (where 1≤k≤l) is the set which consists of all the vertices whose components of Perron vector are equal to max1≤i≤lxui in C, if for any arbitrary natural number j which satisfies 1≤j≤l+1, we all have uj,uj+1,…,uj+k−1≠r1,r2,…,rk, then there exists T1∈TnΔ which makes that ρT1>ρT holds.Proof.
Since for any arbitrary natural numberj which satisfies 1≤j≤l+1, we all have uj,uj+1,…,uj+k−1≠r1,r2,…,rk, we can get k≥2. Without loss of generality, we assume that r1,r2,…,rk have clockwise arrangement in C, as shown in Figure 6, and denote rk+1=r1.
Since for any natural numberj which satisfies 1≤j≤l+1, we all have uj,uj+1,…,uj+k−1≠r1,r2,…,rk. We know that there exist two vertices v1andv2 in C and exist two numbers i and s that satisfy both 1≤i≤k−1,1≤s≤k, and i<s, which make v1 is in clockwise arrangement between ri and ri+1, v1 is adjacent to ri, and v2 is in clockwise arrangement between rs and rs+1, v2 is adjacent to rs, and xv1≠max1≤i≤lxuiandxv2≠max1≤i≤lxui. From the definition of r1,r2,…,rk, we know xri=xrs>maxxv1,xv2. Let T1=T−ri,v1−rs,v2+ri,rs+v1,v2, then it is easy to know T1∈TnΔ. From xri>xv2 and xrs>xv1, by Lemma 3, we have ρT1>ρT; therefore, Lemma 6 holds.Figure 6
The only circle C inT.Lemma 7.
Assume thatT∈TnΔ,T=VT,ET,v1,v2,v3,andv4 are four different vertices of T, and v1andv3∈ET,v2,v4∈ET. If x=x1,x2,…,xnT is the Perron vector of T, xv1,xv2,xv3,andxv4 correspond to vertices v1,v2,v3,andv4, respectively, and xv1>xv2>xv3>xv4. Let T1=T−v1,v3−v2,v4+v1,v2+v3,v4, if T1 is still a simple connected graph, then ρT1>ρT.Proof.
Sincex=x1,x2,…,xnT is the Perron vector of T, we can imply that ρT=xTATx, where AT is the adjacency matrix of T. For xTAT1x−xTATx=2xv1xv2+xv3xv4−xv1xv3+xv2xv4=2xv1−xv4xv2−xv3>0, and T1 is a simple connected graph; hence, we get ρT1=maxy=1yTAT1y≥xTAT1x>xTATx=ρT.
Therefore, Lemma7 holds.


## 2.1. Some Basic Concepts

A rooted unicyclic graph is a simple nonlinear structure. Figure1 shows a rooted unicyclic graph with root node R.Figure 1
A rooted unicyclic graph.We can divide a rooted unicyclic graph into levels according to the following principles.The root nodes are in the first level. For instance, in the rooted unicyclic graph with root nodeR shown in Figure 1, R is in the first level. In a rooted unicyclic graph, the level which arbitrary vertex is defined as the shortest distance from the vertex to the root node adds 1; for instance, in the rooted unicyclic graph with root node R shown in Figure 1, the vertices A,C,D,E are in the second level, the vertices B,F,G,J,K,L,M,N,O,P,Q are in the third level, and the vertices H,I,V,S are in the fourth level. The levels of a rooted unicyclic graph are defined as the maximum of the levels of all the vertices in the rooted unicyclic graph. For instance, the level of the rooted unicyclic graph shown in Figure 1 is 4.Assume thatT is a rooted unicyclic graph, R is the root node of T and u is an arbitrary vertex which is not equal to R in T. Suppose that the shortest path from u to R is u1u2⋯uk, where u1=u,k≥2,uk=R, then we call u2 is a father vertex of u. For instance, in the rooted unicyclic graph with root node R shown in Figure 1, the shortest path from vertex F to vertex R is FAR, A is a father vertex of F. The shortest paths from vertex B to vertex R are BARandBCR, respectively; therefore, A and C are both father vertices of B.LetT be a rooted unicyclic graph, if u and v are two different vertices of T, and u,v have the same father vertex, then u is called a brother of v. If w1 and w2 are two different vertices in the same level in T, and the father vertex of w1 is not equal to the father vertex of w2, then w1 is called a cousin of w2. For instance, in the rooted unicyclic graph with root node R shown in Figure 1, vertex L≠M, L, and M have the same father vertex D; therefore, L is a brother of M. Besides, vertices L,Q are two vertices in the same level in T, and the father vertex of L is not equal to the father vertex of Q; therefore, L is a cousin of Q.The vertices (exceptu) on the shortest path that connects the root node to vertex u are called the direct ancestor of the vertex u. For instance, in the rooted unicyclic graph with root node R shown in Figure 1, the shortest path from the root node R to the vertex M is RDM; therefore, R and D are both the direct ancestors of M.Assume thatuandv are two different vertices in the rooted unicyclic graph T, the level of the vertex u in T is k1 and the level of the vertex v in T is k2, where k2<k1 and v is not the direct ancestor of u, then we call v is a collateral ancestor of u. For instance, in the rooted unicyclic graph with root node R shown in Figure 1, the level of vertex L in T is 3, the level of vertex E in T is 2, and E is not the direct ancestor of L; therefore, vertex E is the collateral ancestor of vertex L.Suppose thatT is a rooted unicyclic graph, if vertex v and vertex w are both direct ancestors of vertex u, and the level of vertex v in T is larger than the level of vertex w in T, then the generation of vertex v to u is closer than the generation of vertex w to vertex u. For instance, in the rooted unicyclic graph with root node R shown in Figure 1, the shortest path from vertex R to vertex Q is REQ, vertices RandE are both direct ancestors of Q, the root node R is in the first level, and vertex E is in the second level; therefore, the generation of vertex E to Q is closer than the generation of vertex R to vertex Q.Ifm≥2, and for any number i which satisfies 1≤i≤m, we all have that p is a direct ancestor of ui, then p is called a common direct ancestor of u1,u2,…,um. For instance, in the rooted unicyclic graph with root node R shown in Figure 1, E is both the direct ancestor of O and the direct ancestor of S; therefore, E is a common direct ancestor of OandS.Ifm≥2, p is a common direct ancestor of u1,u2,…,um, and q which is the arbitrary direct ancestor of u1,u2,…,um satisfies that q is either equal to p or the direct ancestor of p, then p is called the common direct ancestor of u1,u2,…,um of the nearest generation. For instance, in the rooted unicyclic graph with root node R shown in Figure 1, A is the common direct ancestor of F,I of the nearest generation.Letv,w be two cousins of u, if the common direct ancestor of u and w of the nearest generation is the common direct ancestor of u and v of the nearest generation, then v is the cousin of u with generation closer than w. For instance, in the rooted unicyclic graph with root node R shown in Figure 1, HandS are two cousins of V, and the common direct ancestor of V and H of the nearest generation is A, the common direct ancestor of V and S of the nearest generation is R, and R is the ancestor of A; therefore, H is the cousin of V generation closer than S.In order to give the main results of this paper, we introduce some basic definitions and lemmas.


## 2.2. Some Definitions

Definition 1.
Suppose thatT∗∈TnΔ, if for any T∈TnΔ all have that ρT≤ρT∗ establish, then T∗ is called a maximal-adjacency-spectrum unicyclic graph in TnΔ.Definition 2.
Suppose thatk≥2 and v0,v1,…,vk are vertices different from each other in graph T, if dv0≥3,dvk≥3, and for any natural number i which satisfies 1≤i≤k−1 all have dvi=2, then v0v1…vkk≥2 a path of graph T is called an internal path of graph T.Definition 3.
Suppose thatT=V,E is a unicyclic graph, and the degree of T is ΔΔ≥3, v∈V is called a nonfull vertex of T, which means v satisfies 2≤dv<Δ.Definition 4.
Suppose thatT=V,E is a simple connected graph with n vertices, the vertices in T with degree 1 are called the pendant point of T, or call that vertex in the leaf node of T; for convenience, the leaf node of T is sometimes simply called leaf node of T. The edge associated with the pendant point is called pendant edge.Definition 5.
Suppose thatT=V,E is a unicyclic graph, and the maximum degree of T is ΔΔ≥3, if T satisfies or T≅Tn,2Δ, where Tn,2Δ is shown in Figure 2, and r is the root node of Tn,2Δ. Or T is a rooted unicyclic graph with levels more than two, and T satisfies the following properties:(1)
The vertex in the first level isr, and r is the root node of T; the vertices in the second level from left to right are v1,v2,…,vΔ.(2)
Suppose that the only circle inT is C, and VC=r,v1,v2.(3)
The internal vertices ofT are all full-degree vertices.(4)
The distance from all the leaf node nodes ofT to r is equal.
Then,T is called a completely full Δ degree unicyclic graph.Figure 2
A completely full Δ degree unicyclic graph with levels 2.Definition 6.
SupposeT=V,E is a unicyclic graph, and the maximum degree of T is ΔΔ≥3, if T satisfies or that T≅Tn,2Δ, where Tn,2Δ is shown in Figure 2, and r is the root node of Tn,2Δ. Or T is a completely full Δ degree unicyclic graph with levels more than two. Or T is a rooted unicyclic graph obtained from another completely full Δ degree unicyclic graph with levels more than two by deleting some right leaf nodes. Then, T is called an almost completely full Δ degree unicyclic graph. We denote the almost completely full Δ degree unicyclic graph with n vertices and maximum degree Δ by HnΔ.Definition 7.
Suppose thatT=V,E is a unicyclic graph, and the maximum of T is ΔΔ≥3, if T satisfies or T≅Tn,2Δ, where Tn,2Δ is shown in Figure 2, and r is the root node of Tn,2Δ. Or T∗≅Tn,3Δ, where Tn,3Δ=VTn,3Δ,ETn,3Δ,VTn,3Δ=r,v1,v2,…,vΔ,w1,w2,…,ws (where s is the number which satisfies that s+2≤Δ), ETn,3Δ=r,v1,r,v2,v1,v2,r,v3,…,r,vΔ,v1,w1,…,v1,ws, and r is the root node of Tn,3Δ. or T is a rooted unicyclic graph with k levels, and T satisfies the following properties:(1)
k≥3.(2)
The vertex in the first level isr, and r is the root node of T; the vertices in the second level from left to right are v1,v2,…,vΔ.(3)
Suppose that the only circle inT is C, and VC=r,v1,v2.(4)
There is at most one nonfull internal vertex inT.(5)
When there is only one nonfull internal vertex inT, this nonfull internal vertex is in the k−1 level of T.
Then,T is an almost full Δ degree unicyclic graph with root node r.
From the definitions above, we know that completely fullΔ degree unicyclic graph is the special situation of almost completely full Δ degree unicyclic graph. completely full Δ degree unicyclic graph and almost completely full Δ degree unicyclic graph are both special situations of almost full Δ degree unicyclic graph. For convenience, in this paper, we denote completely full Δ degree unicyclic graph, almost completely full Δ degree unicyclic graph, almost full Δ degree unicyclic graph by completely full-degree unicyclic graph, almost completely full-degree unicyclic graph, and almost full-degree unicyclic graph, respectively.
For instance, suppose that the unicyclic graph shown in Figure3(a) is a rooted unicyclic graph with root node r, then the rooted unicyclic graph shown in Figure 3(a) is a completely full 3 degree unicyclic graph with levels 3, maximum degree 3, and root node r. Suppose that the root node of the unicyclic graph shown in Figure 3(b) is r, then the rooted unicyclic graph shown in Figure 3(b) is an almost completely full 4 degree unicyclic graph with levels 4, maximum degree 4, and root node r. Suppose that the root node of the unicyclic graph shown in Figure 3(c) is r, then the rooted unicyclic graph shown in Figure 3(c) is an almost full 4 degree unicyclic graph with levels 4, maximum degree 4, and root node r.
In order to give the main results of this paper, we give some lemmas.Figure 3
Some unicyclic graphs with roots.
(a)(b)(c)


## 2.3. Some Lemmas

Now, we give some lemmas which we use to proof the main results.Lemma 1 (see [13]).
Suppose thatT is a simple connected graph with n vertices and maximum Δ, x=x1,x2,…,xnT is the Perron vector of T, xuandxv correspond to vertices uandv, respectively, and xu≥xv. If w∈NTv\u, let T1=T−v,w+u,w, if T1 is still a simple connected graph, then ρT1>ρT.Lemma 2 (see [13]).
Suppose thatT is a simple connected graph with n vertices and maximum Δ, x=x1,x2,…,xnT is the Perron vector of T, xuandxv correspond to vertices uandv, respectively, and xu≥xv. Suppose that w1∈NTv\u,w2∈NTV\u,…,wk∈NTv\u. Let T1=T−v,w1−v,w2−⋯−v,wk+u,w1+u,w2+⋯+u,wk, T1 and T are shown in Figure 4. If T1 is still a simple connected graph, then ρT1>ρT.Figure 4
Transition deformation of graphs.Lemma 3 (see [13]).
Suppose thatT=V,E is a simple connected graph with n vertices and maximum Δ, x=x1,x2,…,xnT is the Perron vector of T, and suppose that xu1,xu2,xv1,andxv2 correspond to the four different vertices u1,u2,v1,andv2, respectively, where u1,u2∈E,v1,v2∈E and xu1≥xv1,xu2<xv2. Let T1=T−u1,u2−v1,v2+u1,v2+v1,u2, T1 and T are shown in Figure 5; if T1 is still a simple connected graph, then ρT1>ρT.Figure 5
Cross deformation of graphs.Lemma 4 (see [14]).
Suppose thatT=V,E is a simple connected graph, and v0v1⋯vkk≥2 is an internal path of T. If T1=T−vi−1vi−vivi+1+vi−1vi+1, where 1≤i≤k−1, then ρT1≥ρT.Lemma 5 (see [13]).
Suppose thatT=VT,ET is a connected graph, if u∈VTandv∉VT, let T1=T+u,v, then ρT1>ρT.Lemma 6.
Assume thatT∈TnΔ, the edge set of T is ET, and C is the only circle in T. Suppose that VC=u1,u2,…,ul, where l≥4, and for any natural number i which satisfies 1≤i≤k−1, we all have ui,ui+1∈ET,ul,u1∈ET, denote ul+1=u1,ul+2=u2,…,u2l=ul. Suppose that x=x1,x2,…,xnT is the Perron vector of T, r1,r2,…,rk (where 1≤k≤l) is the set which consists of all the vertices whose components of Perron vector are equal to max1≤i≤lxui in C, if for any arbitrary natural number j which satisfies 1≤j≤l+1, we all have uj,uj+1,…,uj+k−1≠r1,r2,…,rk, then there exists T1∈TnΔ which makes that ρT1>ρT holds.Proof.
Since for any arbitrary natural numberj which satisfies 1≤j≤l+1, we all have uj,uj+1,…,uj+k−1≠r1,r2,…,rk, we can get k≥2. Without loss of generality, we assume that r1,r2,…,rk have clockwise arrangement in C, as shown in Figure 6, and denote rk+1=r1.
Since for any natural numberj which satisfies 1≤j≤l+1, we all have uj,uj+1,…,uj+k−1≠r1,r2,…,rk. We know that there exist two vertices v1andv2 in C and exist two numbers i and s that satisfy both 1≤i≤k−1,1≤s≤k, and i<s, which make v1 is in clockwise arrangement between ri and ri+1, v1 is adjacent to ri, and v2 is in clockwise arrangement between rs and rs+1, v2 is adjacent to rs, and xv1≠max1≤i≤lxuiandxv2≠max1≤i≤lxui. From the definition of r1,r2,…,rk, we know xri=xrs>maxxv1,xv2. Let T1=T−ri,v1−rs,v2+ri,rs+v1,v2, then it is easy to know T1∈TnΔ. From xri>xv2 and xrs>xv1, by Lemma 3, we have ρT1>ρT; therefore, Lemma 6 holds.Figure 6
The only circle C inT.Lemma 7.
Assume thatT∈TnΔ,T=VT,ET,v1,v2,v3,andv4 are four different vertices of T, and v1andv3∈ET,v2,v4∈ET. If x=x1,x2,…,xnT is the Perron vector of T, xv1,xv2,xv3,andxv4 correspond to vertices v1,v2,v3,andv4, respectively, and xv1>xv2>xv3>xv4. Let T1=T−v1,v3−v2,v4+v1,v2+v3,v4, if T1 is still a simple connected graph, then ρT1>ρT.Proof.
Sincex=x1,x2,…,xnT is the Perron vector of T, we can imply that ρT=xTATx, where AT is the adjacency matrix of T. For xTAT1x−xTATx=2xv1xv2+xv3xv4−xv1xv3+xv2xv4=2xv1−xv4xv2−xv3>0, and T1 is a simple connected graph; hence, we get ρT1=maxy=1yTAT1y≥xTAT1x>xTATx=ρT.
Therefore, Lemma7 holds.


## 3. The Properties and Structure of the Maximal-Adjacency-Spectrum Unicyclic Graphs inTnΔ

### 3.1. The Properties of the Maximal-Adjacency-Spectrum Unicyclic Graphs inTnΔ

First, we give the properties of the Perron vector of the maximal-adjacency-spectrum unicyclic graphs inTnΔ, as in the following theorems:Theorem 11.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, if x=x1,x2,…,xnT is the Perron vector of T∗, then the degree of the vertices that corresponds to all largest components in the component of x is Δ.Proof.
Assume that the proposition is not established, we suppose that there exists a vertexv∗ in T∗ such that xv∗=max1≤i≤nxi and dv∗<Δ. Denote p=dv∗, it is obvious that p≥2; hence, 2≤p<Δ. We choose a vertex u with degree Δ in VT∗, suppose that NT∗u=v1,v2,…,vΔ. For T∗ is a unicyclic graph, it is easy to know that there are Δ−p vertices vj1,vj2,…,vjΔ−p in the set of NT∗u\NT∗v∗ such that T∗−u,vj1−u,vj2−⋯−u,vjΔ−p+v∗,vj1+v∗,vj2+⋯+v∗,vjΔ−p is still a simple connected graph. Denote T1=T∗−u,vj1−u,vj2−⋯−u,vjΔ−p+v∗,vj1+v∗,vj2+⋯+v∗,vjΔ−p, then it is easy to know T1∈TnΔ. Again by xv∗≥xu, by Lemma 2, we get ρT1>ρT∗, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ; hence, the hypothesis is not established; therefore, Theorem 11 holds.Theorem 12.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, and the only circle in T∗ is C, x=x1,x2,…,xnT is the Perron vector of T∗, if the component xu∗ which corresponds to the vertex u∗ in x satisfies that xu∗=max1≤i≤nxi, then u∗∈VC.Proof.
Assume that the proposition is not established, we suppose that there exists a vertexu∗ in T∗ such that xu∗=max1≤i≤nxi and u∗∈VT∗\VC. From xu∗=max1≤i≤nxi and Theorem 11, we get du∗=Δ. For du∗=Δ,u∗∈VT∗\VC and T∗ is a unicyclic graph, we know that there exists a path u∗u1⋯ukk≥1 whose length is k in T∗, which makes u∗∉VC,u1∉VC,…,uk∉VC, u1,u2,…,uk are difference with each other, and uk is the leaf node.
First, for∀v∈VC, we have xv>xuk. Otherwise, suppose there exists a vertex v1 in VC such that xv1≤xuk. Now according to the value of dv1, we discuss the following two cases:Case 1.dv1<Δ.Sincev1∈VC, we have NT∗v1≥2; thus in the set of VT∗, there exists a vertex v2 which satisfies v2∈NT∗v1 such that T∗−v2,v1+v2,uk is still a simple connected graph. Denote T1=T∗−v2,v1+v2,uk, then it is easy to know T1∈TnΔ. By Lemma 1, we get ρT1>ρT∗, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Case 2.dv1=Δ.In this case, it is easy to know that in the set ofNT∗v1, there exist Δ−1 vertices v2,v3,…,vΔ such that T∗−v1,v2−v1,v3−⋯−v1,vΔ+uk,v2+uk,v3+⋯+uk,vΔ is still a simple connected graph. Denote T1=T∗−v1,v2−v1,v3−⋯−v1,vΔ+uk,v2+uk,v3+⋯+uk,vΔ, then it is easy to know T1∈TnΔ. From xv1≤xuk, by Lemma 2, we can get ρT1>ρT∗, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.
From the above discussion of the two cases, we know that the hypothesis is not established. Hence, for∀v∈VC, we all have that xv>xuk holds.
Second, denoteu∗ by u0, suppose that v is the vertex which is nearest to u∗ in C. Choose two vertices v1andv2 different from v in C, then xu0≥xv1,xu0≥xv2,xv1>xuk, and xv2>xuk. Thus, we have that there exists a natural number l which satisfies 1≤l≤k such that at least one of the following two inequality groups: ① xv1≤xul−1,xv2>xul and ② xv2≤xul−1,xv1>xul holds. Without loss of generality, we assume that there exists a natural number l which satisfies 1≤l≤k such that xv1≤xul−1 and xv2>xul. Then, let T2=T∗−ul−1,ul−v1,v2+v2,ul−1+v1,ul, then it is easy to know T2∈TnΔ. By Lemma 3, we have that ρT2>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Therefore, Theorem 12 holds.Lemma 8.
Assume thatT∈TnΔ, x=x1,x2,…,xnT is the Perron vector of T, and C is the only circle in T, VC=u1,u2,…,ul, suppose that xu1,xu2,…,xul corresponds to the vertices u1,u2,…,ul, respectively. If l≥4, and xu1=xu2=⋯=xul, then there must exist T1∈TnΔ such that ρT1>ρT.Proof.
Assume that the proposition is not established, thenT is a maximal-adjacency-spectrum unicyclic graph in TnΔ. From Theorem 12, we can get xu1=xu2=⋯=xul=max1≤i≤nxi; again by Theorem 11, we get du1=du2=⋯=dul=Δ≥3; hence, for any natural number i which satisfies 1≤i≤l, and we all have NTui\VC≠∅. Besides, from Theorem 12, we get that for ∀v∈VT\VC, we all have xv<max1≤i≤nxi.
Without loss of generality, we assume thatu1,u2,…,ul have clockwise arrangement in C. Since NTu1\VC≠∅, choose v∈NTu1\VC, then we have xv<xu1. For l≥4, we can know u1,v,ul−1,andul are different from each other. From xu1=xu2=⋯=xul and xu1>xv, we know that xul−1=xu1>xv; again from xu1=xul, we can get xu1≥xul. Let T1=T−u1,v−ul,ul−1+u1,ul−1+ul,v, then it is easy to know T1∈TnΔ. From xul−1>xv and xu1≥xul, by Lemma 3, we have that ρT1>ρT holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Therefore, Lemma 8 holds.Lemma 9.
Assume thatT∈TnΔ, where T=VT,ET, C is the circle of T, VC=u1,u2,…,ul,l≥4, and for any natural number i which satisfies 1≤i≤l−1, we all have ui,ui+1∈ET,ul,u1∈ET. If there exists a natural number i0 which satisfies 1≤i0≤l such that dui0=2, then there exists T1∈TnΔ such that ρT1>ρT.Proof.
Assume that the proposition is not established, thenT is a maximal-adjacency-spectrum unicyclic graph in TnΔ.
Form Theorems11 and 12, we know that there exists a natural number j which satisfies 1≤j≤l such that xuj=max1≤i≤nxi and duj=Δ≥3. Now, we discuss the following two cases: Case 1. There are at least two vertices with the degree not less than 3 in VC.Denoteul+1=u1, for any natural number i which satisfies 1≤i≤l−1, we all have ui,ui+1∈ETandul,u1∈ET; hence, for any natural number i which satisfies 1≤i≤l, we all have ui,ui+1∈ET. And for there exists a natural number i0 which satisfies 1≤i0≤l such that dui0=2 and there are at least two vertices with the degree not less than 3 in VC, then we know that there exist two natural numbers t and m which satisfy m≥2 and 1≤t≤l−m+1 such that utut+1⋯ut+m is an internal path. Let T1=VT1,ET1, where VT1=VT\ut+1andET1=ET−ut,ut+1−ut+1,ut+2+ut,ut+2. It is easy to know T1∈Tn−1Δ, and by Lemma 4, we have that ρT1≥ρT holds.Suppose thatv1 is an arbitrary leaf node of T1. Let T2=T1+v1,ut+1, then it is easy to know T2∈TnΔ, and by Lemma 5, we have that ρT2>ρT1 holds, and thus, ρT2>ρT. Therefore, this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Case 2. There is only one vertex with degree not less than 3 inVC.In this case, it is easy to know that the only one vertex with degree not less than 3 must beuj. Suppose that VC=v1,v2,…,vl−1,uj, and v1,v2,…,vl−1,uj have clockwise arrangement in C, as shown in Figure 7. From Theorems 11 and 12, we get xuj>maxxv1,xv2,…,xvl−1. From l≥4, we know that vl−2,vl−1,andv1 are different. And for xuj>xvl−1, it is easy to prove that xv1>xvl−2 holds. Otherwise, xv1≤xvl−2, let T1=T−vl−1,vl−2−uj,v1+uj,vl−2+v1,vl−1, then it is easy to know T1∈TnΔ. From xuj>xvl−1 and xvl−2≥xv1, by Lemma 3, we have that ρT1>ρT holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ; hence, xv1>xvl−2. Let T2=T−vl−1,vl−2+vl−1,v1, then it is easy to know T2∈TnΔ, and by Lemma 1, we have that ρT2>ρT holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.
By consideration of the above two cases, we know that the hypothesis is not established. Therefore, Lemma9 holds.Figure 7
Vertex permutation graph of cycle C.Figure 8
Vertex permutation graph of cycle C with four vertices.Figure 9
Cycle C with four vertices.Lemma 10.
Assume thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, and x=x1,x2,…,xnT∗ is the Perron vector of T∗. Then, for any leaf node i and any vertex j which is not the leaf node in T∗, we all have that xi<xj holds, where xiandxj correspond to the vertices iandj, respectively.Proof.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, and x=x1,x2,…,xnT∗ is the Perron vector of T∗. Let j0 be any one of the vertices whose component is equal to max1≤l≤nxl in x, then from Theorem 11, we know dj0=Δ. Then, for any nonleaf node u which is not j0 in T∗, and for the arbitrary leaf node i in T∗, we all have that xu≥xi holds. Otherwise, there exists a vertex w which is not the vertex j0 and is not a leaf node i1 in T∗, which makes xw<xi1. For w is not the leaf node, hence dw≥2, thus there exists a vertex v in the set of NT∗w such that T∗−v,w+v,i1 still belong to TnΔ. Let T1=T∗−v,w+v,i1, then by Lemma 1, we have that ρT1>ρT holds, this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Again since xj0=max1≤l≤nxl, then xj0≥xu; thus, for any vertex j which is not the leaf node in T∗, and for any leaf node i in T∗, we all have that xj>xi holds.
For the properties of the nonfull internal vertices of the maximal-adjacency-spectrum unicyclic graph inTnΔ, we have the following theorems.Theorem 13.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, if the only circle in T∗ is C, and there exists a nonfull internal vertex in the set of VT∗\VC, then the number of all the nonfull internal vertices of T∗ is one.Proof.
Assume that the proposition is not established, then suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, the only circle in T∗ is C, there exists a nonfull internal vertex in the set of VT∗\VC, and the number of the nonfull internal vertex in T∗ is more than 1. Without loss of generality, assume that u1andu2 are two nonfull internal vertices in T∗, where u1∈VT∗\VC.
Letx=x1,x2,…,xnT be the Perron vector of T∗, xu1andxu2 correspond to the vertices u1andu2, respectively. Now according to whether u1 and u2 adjacent or not , we discuss the following two cases:Case 1.u1 and u2 adjacent.For case 1, we discuss the following two subcases again according to the value ofxu1 and xu2.Subcase 1.xu1≥xu2.Sinceu2 is the nonfull internal vertex in T∗, then NT∗u2\u1≠∅, choose w∈NT∗u2\u1. Let T1=T∗−w,u2+w,u1, then it is easy to know T1∈TnΔ. By Lemma 1, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Subcase 2.xu1<xu2.Sinceu1 is the nonfull internal vertex in T∗, then NT∗u1\u2≠∅, choose w∈NT∗u1\u2. Let T1=T∗−w,u1+w,u2, then it is easy to know T1∈TnΔ. By Lemma 1, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Case 2.u1 and u2 are not adjacent.Sinceu1andu2 are the nonfull internal vertices in T∗, we have that NT∗u1\NT∗u2≥1 and NT∗u2\NT∗u1≥1 hold at the same time. For case 2, we discuss the following two subcases again according to the value of xu1 and xu2.Subcase 1.xu1≤xu2.SinceNT∗u1\NT∗u2≥1 and T∗ is a unicyclic graph, we know that there exists w∈NT∗u1\NT∗u2 such that T∗−w,u1+w,u2 is still a simple connected graph. Denote T1=T∗−w,u1+w,u2, then it is easy to know T1∈TnΔ; by Lemma 1, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Subcase 2.xu1>xu2.ForNT∗u2\NT∗u1≥1 and T∗ is a unicyclic graph, we know that there exists w∈NT∗u2\NT∗u1 such that T∗−w,u2+w,u1 is still a simple connected graph. Denote T1=T∗−w,u2+w,u1, then it is easy to know T1∈TnΔ; by Lemma 1, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.
Hence, from the discussions of case 1 and case 2, we can know that the hypothesis is not established; therefore, Theorem13 holds.Theorem 14.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, let C be the only circle in T∗, and VC=3, if there is no nonfull internal vertex in the set of VT∗\VC, then both the following propositions are established:(1)
The number of the nonfull internal vertex inVC is at most 2.(2)
When the number of nonfull internal vertex inVC is 2, then there is at least one vertex with degree 2 in the two nonfull internal vertices in VC.Proof.
Letx=x1,x2,…,xn be the Perron vector of T∗.(1)
Suppose that a vertexv in T∗ satisfies xv=max1≤i≤nxi, then from Theorem 12, we get v∈VC, and from Theorem 11, we know dv=Δ. Hence, the number of the nonfull internal vertices in VC is at most 2, and then, (1) of Theorem 14 holds.(2)
When the number of nonfull internal vertices inVC is 2, without loss of generality, we assume that u1andu2 are the nonfull internal vertices in VC. Suppose that xu1andxu2 correspond to the vertices u1andu2, respectively. Assume that du1≠2 and du2≠2, then we must have that du1≥3 and du2≥3 hold. Hence, NT∗u1\VC≠∅ and NT∗u2\VC≠∅. Choose s1∈NT∗u1\VC,s2∈NT∗u2\VC. Without loss of generality, we assume that xu1≥xu2, and let T1=T∗−u2,s2+s2,u1, then it is easy to know T1∈TnΔ. By Lemma 1, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Hence, the hypothesis is not established. Therefore, either du1=2 or du2=2, then (2) of Theorem 14 holds.
By consideration, Theorem14 holds.


### 3.2. The Structure of the Maximal-Adjacency-Spectrum Unicyclic Graphs inTnΔ

For the length of the circle of the maximal-adjacency-spectrum unicyclic graphs inTnΔ, we have the following theorems.Theorem 15.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. If the only circle in T∗ is C, there is no nonfull internal vertex in the set of VT∗\VC, and the number of the nonfull internal vertex in the set of VC is equal to or greater than 2, then the length of the circle is 3, that is, VC=3.Proof.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, the only circle in T∗ is C, there is no nonfull internal vertex in the set of VT∗\VC, and the number of the nonfull internal vertices in the set of VC is not less than 2. Denote VC=m, and assume that Theorem 15 is not established, then m≥4. Suppose that u1∈VC,u2∈VC, and u1andu2 are two different nonfull internal vertices in T∗. Let x be the Perron vector of T∗, and suppose that xu1andxu2 correspond to the vertices u1andu2. Now according to the value of m, we discuss the following two cases:Case 1.m≥5.In case 1, there exists a pathu1v1v2⋯vku2 which satisfies k≥2 in C. Without loss of generality, we assume that xu1≥xu2. Let T1=T∗−vk,u2+vk,u1, then it is easy to know T1∈TnΔ. By Lemma 1, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Case 2.m=4.Now according to whether the verticesu1 and u2 adjacent or not, we discuss the following two subcases again:Subcase 1. Ifm=4 and u1andu2 are adjacent.At this time, it is easy to know that there is a pathu1v1v2u2 in C. Without loss of generality, we assume that xu1≥xu2. Let T1=T∗−v2,u2+v2,u1, then it is easy to know T1∈TnΔ; By Lemma 1, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Subcase 2. Ifm=4 and u1andu2 are not adjacent.Suppose thatVC=u1,u2,v1,w1. First, we must have that dv1=dw1=Δ holds; otherwise, there must exist two adjacent nonfull internal vertices in C. From the discussion of the subcase 1 in case 2, we know that it will imply a contradiction. Without loss of generality, we assume that the position relationship of the vertices v1,w1,u1,andu2 in C is shown in Figure 8.Second, we must havedu1≥3 and du2≥3. Otherwise, there are at least one of the two inequalities, du1<3 and du2<3, holds. Without loss of generality, assume that du1<3. For u1∈VC, du1=2. And since dv1=dw1=Δ≥3, we have that v1u1w1 is an internal path, let T1=VT1,ET1, where VT1=VT∗\u1,ET1=ET∗−v1,u1−u1,w1+v1,w1, then it is easy to know T1∈Tn−1Δ. By Lemma 4, we have that ρT1≥ρT∗ holds. Let w1 be an arbitrary leaf node in T1, and let T2=T1+u1,w1, then it is easy to know T2∈TnΔ. By Lemma 5, we have that ρT2>ρT1 holds; hence, ρT2>ρT∗, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Fromdu1≥3 and du2≥3, we know that NT∗u1\VC≠∅ and NT∗u2\VC≠∅ hold. Choose s1∈NT∗u1\VCands2∈NT∗u2\VC. Without loss of generality, assume that xu1≥xu2. Let T3=T∗−s2,u2+s2,u1, then it is easy to know T3∈TnΔ. By Lemma 1, we have that ρT3>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.
Hence, from the discussion of case 1 and case 2, we know thatm≥4 does not hold. Therefore, Theorem 15 holds.Theorem 16.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, if C is the only circle in T∗, then VC=3.Proof.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ and C is the only circle in T∗. Denote VC=l; assume that Theorem 16 does not hold, then we have l≥4. From Theorems 13 and 15, we can get that there is at most one nonfull internal vertex in T∗. Suppose that VC=u1,u2,…,ul, and x=x1,x2,…,xnT is the Perron vector of T∗. By Theorem 12, we can get max1≤i≤lxui=max1≤i≤nxi. Then, from l≥4, T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, and from Lemma 8, we can know max1≤i≤lxui>min1≤i≤lxui. Now, according to the value of l, we discuss the following two cases:Case 1.l=4.Suppose thatVC=u1,u2,u3,u4, from Theorem 12, we have that max1≤i≤4xui=max1≤j≤nxj holds. Without loss of generality, assume that xu1=max1≤i≤4xui, then we have xu1=max1≤j≤nxj; again from Theorem 11, we can get du1=ΔΔ≥3. Without loss of generality, we assume that u1,u2,u3,andu4 have anticlockwise arrangement in C, and the position of the relationship of these vertices is shown in Figure 9.In the situation of case 1, we could prove that the following six propositions hold.Proposition 1.
For any vertexui which satisfies 1≤i≤4 in VC, we all have that NT∗ui\VC≠∅ holds.
For there is at most one nonfull internal vertex inT∗, there is at most one of du2,du3,anddu4 unequal to ΔΔ≥3. Besides, mindu2,du3,du4≥3; otherwise, mindu2,du3,du4=2. Since there is at most one nonfull internal vertex in T∗, hence there must exist an internal path q1q2q3 in C. Let T1=VT1,ET1, where VT1=VT∗\q2,ET1=ET∗−q1,q2−q2,q3+q1,q3. Then, it is easy to know T1∈Tn−1Δ, and by Lemma 4, we have that ρT1≥ρT∗ holds. Let w1 be an arbitrary leaf node in T1, and let T2=T1+q2,w1, then it is easy to know T2∈TnΔ. By Lemma 5, we have that ρT2>ρT1 holds. Hence, ρT2>ρT∗, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Then, we have mindu2,du3,du4≥3, and min1≤i≤4dui≥3. Therefore, for any vertex ui which satisfies 1≤i≤4 in the set of VC, we all have that NT∗ui\VC≠∅ holds.Proposition 2.
xu3=minxu2,xu3,xu4.
Assume thatxu3=minxu2,xu3,xu4 is not established, and we have xu3>minxu2,xu3,xu4. Without loss of generality, assume that minxu2,xu3,xu4=xu2, then we have xu3>xu2. Let T1=T∗−u1,u2−u3,u4+u1,u3+u2,u4, then it is easy to know T1∈TnΔ. From xu1≥xu4 and xu3>xu2, by Lemma 3, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ; hence, the hypothesis is not established. Therefore, xu3=minxu2,xu3,xu4.Proposition 3.
For∀v∈NT∗u2\VC, we all have that xu4=xv holds.
And for∀w∈NT∗v4\VC, we all have that xw=xu2 holds. From Proposition 1, we know NT∗u2\VC≠∅. Assume that, for ∀v∈NT∗u2\VC, we all have that the proposition xu4=xv is not established, then there must exists a vertex v2∈NT∗u2\VC such that xu4≠xv2.Proposition 4.
du2=Δ and du4=Δ.
Ifdu2=Δ is not established, then du2<Δ. From Proposition 1, we know NT∗u3\VC≠∅. Choose v3∈NT∗u3\VC, and let T1=T∗−v3,u3+v3,u2, then it is easy to know T1∈TnΔ. From Proposition 2, we know xu3≤xu2, and by Lemma 1, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Hence, the hypothesis is not established, that is, du2=Δ. The same reason, we can prove that du4=Δ holds.Proposition 5.
xu4=xu2.
From Proposition1, we know NT∗u2\VC≠∅ and NT∗u4\VC≠∅. For Ax=ρT∗x, where A is the adjacency matrix of T∗, denote ρ=ρT∗, then ρxu4=xu1+xu3+∑p∈NT∗u4\VCxp,ρxu2=xu1+xu3+∑q∈NT∗u2\VCxq. From Propositions 3 and 4, we can know ∑p∈NT∗u4\VCxp=Δ−2xu2 and ∑q∈NT∗u2\VCxq=Δ−2xu4; thus, we have ρxu4=xu1+xu3+Δ−2xu2 and ρxu2=xu1+xu3+Δ−2xu4. Hence, ρ+Δ−2xu4−xu2=0. Therefore, xu4=xu2.Proposition 6.
xu1=xu2 and xu1=xu4.
Assume thatxu1≠xu2, then from xu1=max1≤i≤4xui, we know xu1>xu2. From Proposition 1, we can get NT∗u2\VC≠∅. Choose v2∈NT∗u2\VC, let T1=T∗−u1,u4−u2,v2+v2,u1+u2,u4, and then it is easy to know T1∈TnΔ. From Proposition 3, we know xv2=xu4; hence, xu4≤xv2. And for xu1>xu2, then by Lemma 3, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ; hence, we have that xu1=xu2 holds. And from Proposition 5, we get xu4=xu2; therefore, xu1=xu4.
From Proposition2, we know xu3=minxu2,xu3,xu4; from Proposition 6, we have xu1=xu2=xu4, and by Lemma 8, we know max1≤i≤4xui>min1≤i≤4xui; hence, xu3<xu4. Let T2=T∗−u1,u4−u2,u3+u3,u1+u2,u4, then it is easy to know T2∈TnΔ. From xu3<xu4 and xu1≤xu2, by Lemma 3, we have that ρT2>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.
Therefore, in conclusion, case 1 implies a contradiction.
Case 2.l≥5.
In this case, from Lemma8, we have that min1≤i≤lxui<max1≤i≤lxui. Let s be a vertex in C such that xs=min1≤i≤lxui. From Theorem 12, we can get that there exists a natural number i0 which satisfies 1≤i0≤l such that xui0=max1≤i≤nxi. Assume that k is the number of the vertices whose components are equal to max1≤i≤nxi in C. From min1≤i≤lxui<max1≤i≤lxui, we have l−k≥1. Suppose that r1,r2,…,rk are all the vertices whose components are equal to max1≤i≤nxi in C, and r1,r2,…,rk are clockwise arrangement in C. Then, by Lemma 6, we can suppose that the vertices which follow the clockwise direction in C are s,…,r1,r2,…,rk,…,s in sequence.
First, we can prove thatk≥2 holds.
Assume thatk≥2 is not established, then k=1. Then now, we can suppose that the vertices which follow the clockwise direction in C are w2,…,v2,v1,r1,w1,w2 in sequence, where v2,v1,r1,w1,andw2 are five different vertices in C, and let the circle C be shown as Figure 10. From the definitions of r1,r2,…,rk and from k=1, we can know that, for any natural number i which satisfies 1≤i≤2, we all have that xvi<xr1 and xwi<xr1 hold.
From Lemma9, we can get NT∗w1\VC≠∅. Then for ∀t∈NT∗w1\VC, we all have that xt<xv1 holds. Otherwise, there exists t1∈NT∗w1\VC such that xt1≥xv1. Let T1=T∗−w1,t1−r1,v1+r1,t1+w1,v1, then it is easy to know T1∈TnΔ. From xt1≥xv1 and xw1<xr1, by Lemma 3, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.
Besides, we also can provexv2<xw1. Otherwise, xv2≥xw1; let T2=T∗−v1,v2−r1,w1+r1,v2+w1,v1, then it is easy to know T2∈TnΔ. From xv2≥xw1 and xv1<xr1, by Lemma 3, we have that ρT2>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.
Chooset2∈NT∗w1\VC; let T3=T∗−v1,v2−t2,w1+t2,v2+w1,v1, then it is easy to know T3∈TnΔ. From the above conclusion, we have xt2<xv1. For xv2<xw1, by Lemma 3, we have that ρT3>ρT∗ holds. This implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Hence, the hypothesis is not established; therefore, k≥2 holds.
Second, we can prove thatl−k≥2 holds.
Assume thatl−k≥2 is not established, then l−k=1; hence, we can suppose that the vertices which follow the clockwise direction in C are s,r1,r2,…,rk in sequence. From l≥5, we know that k≥4 holds; thus s,r1,rk−1,andrk are four different vertices. Let T4=T∗−r1,s−rk−1,rk+r1,rk+s,rk−1, it is easy to know T4∈TnΔ. From the definitions of r1,r2,…,rk and s, we know xs<xrk. Since xr1≥xrk−1, by Lemma 3, we have that ρT4>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Therefore, l−k=1 is not established, then we have l−k≥2.
Denotem=l−k, from l−k≥2, and we have that m≥2 holds. Then, we can suppose that the vertices which follow the clockwise direction in C are vm,…,v1,r1,…,rk in sequence. From m≥2 and k≥2, we know that vm,v1,r1,andrk are four different vertices in C, and the relationship of the vertices of C is shown in Figure 11.
For the relationship betweenxv1 and xvm, we must have that xv1=xvm holds. Otherwise, there must exist one of the two equations, xv1<xvm and xv1>xvm, holds. Let T5=T∗−r1,v1−rk,vm+r1,vm+v1,rk, then it is easy to know T5∈TnΔ. If xv1<xvm, for xr1≥xrk, by Lemma 3, we have that ρT5>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. If xv1>xvm, for xr1≤xrk, by Lemma 3, we have that ρT5>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Hence, xv1=xvm. Then, we have that xvm≥xv1 holds.
By Lemma9, we know dvm≥3; hence, NT∗vm\VC≠∅. Choose u∈NT∗vm\VC; then from Theorem 11, we get xu<xr1. Let T6=T∗−r1,v1−u,vm+r1,vm+v1,u, it is easy to know T6∈TnΔ. From xvm≥xv1 and xu<xr1, by Lemma 3, we know that ρT6>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.
Hence, in conclusion, case 2 implies a contradiction.By consideration of the discussion of case 1 and case 2, we know that whenl=4 or l≥5, a contradiction is implied. Hence, l≥4 is not established; therefore, l=3 and VC=3. Then, we have that Theorem 16 holds.Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, then the leaf nodes of T∗ have the properties stated in the following theorem.Figure 10
Vertex permutation graphs of cycle C with no less than 5 vertices.Figure 11
The relationship of the vertices of C.Theorem 17.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, and let r be the vertex that corresponds to a maximum component in the component of the Perron vector of T∗. T∗ is the rooted unicyclic graph with root node r, let C be the only circle in T∗, and VC=r,g1,g2. Let du,v be the shortest distance between vertex u and vertex v in T∗, denote that W1 = {ii is the leaf node of T∗, and the shortest path from i to r neither pass g1 nor pass g2}, W2 = {ii is the leaf node of T∗, and the shortest path from i to r either pass g1 or pass g2}, then the following propositions are established:(1)
IfW2=∅, then maxi∈W1di,r=1.(2)
Ifdg1=2, then for the arbitrary leaf node i in T∗, we all have 1−di,r≤1.Ifdg2=2, then for the arbitrary leaf node i in T∗, we all have 1−di,r≤1.(3)
IfW2≠∅, then for the arbitrary leaves i,j in T∗, we all have di,r−dj,r≤1.(4)
IfW2≠∅, then mini∈W2di,r≥maxj∈W1dj,r.(5)
IfW2≠∅, and there exists a vertex with degree 2 in VC, then T∗ is the rooted unicyclic graph with 3 levels, and for ∀j∈W1, we all have dj,r=1.Proof.
Assume thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, and suppose that r is the vertex that corresponds to a maximum component in the component of the Perron vector of T∗, and T∗ is a rooted unicyclic graph with root node r. Suppose that C is the only circle in T∗, and VC=r,g1,g2, let x=x1,x2,…,xnT be the Perron vector of T∗.(1)
Assume thatmaxi∈W1di,r=1 is not established, then there exists a vertex i∈W1 such that di,r≥2. Suppose that the shortest path from i to r is u1u2⋯ukr, where u1=i,k≥2. By Lemma 1, it is easy to prove that xg1<xu2 holds. And from Lemma 10, we get xg2>xu1. Let T1=T∗−g1,g2−u1,u2+u2,g2+g1,u1, it is easy to know T1∈TnΔ. From xg1<xu2 and xg2>xu1, by Lemma 3, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Hence, maxi∈W1di,r=1.Therefore, (1) of Theorem17 holds.(2)
Assume thatdg1=2, and there exists a leaf node i in T∗ such that 1−di,r>1. Without loss of generality, we assume that the shortest path from r to i is rv1v2⋯vk, where vk=i. From 1−di,r>1, we know di,r≥3, then we have k≥3. Let T1=T∗−vk−1,vk+g1,vk, then it is easy to know T1∈TnΔ. If xg1≥xvk−1, then by Lemma 1, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ; hence, xg1<xvk−1. Let T2=T∗−vk−1,vk−r,g1+vk−1,r+g1,vk, it is easy to know T2∈TnΔ. Since xg1<xvk−1, and from Lemma 10, we know that xvk<xr holds. By Lemma 3, we have that ρT2>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Hence, when dg1=2, for any leaf node i in T∗, we all have that 1−di,r≤1 holds. Similarly, when dg2=2, for any leaf node i in T∗, we all have that 1−di,r≤1 holds.Therefore, (2) of theorem holds.(3)
Assume that there exist two leaf nodesi,j in T∗ such that di,r−dj,r>1. Suppose that di,r=k,dj,r=l, then we have k−l>1. Without loss of generality, we assume that k−l>1, then we have that k≥l+2 and l≥1 hold. Let P1 be the shortest path from i to r and P2 be the shortest path from j to r. According to whether there is a public edge between P1 and P2 or not, we discuss the following two cases:Case 1. There is no public edge betweenP1 and P2.We denote the pathP1 by rvkvk−1⋯v2v1 and the path P2 by rul⋯u2u1, where v1=iandu1=j; P1andP2 are shown in Figure 12. Besides, we denote ul+1=r; by the definition of r, we know xul+1≥xvk.Foru1 is the leaf node in T∗ and v2 is the nonleaf node in T∗, then by Lemma 10, we have xu1<xv2.Fromxu1<xv2,xul+1≥xvk and k−1≥l+1, we know that there exists a natural number s that satisfies 1≤s≤l, which make xus<xvs+1 and xus+1≥xvs+2. Let T1=T∗−us,us+1−vs+1,vs+2+vs+1,us+1+us,vs+2, then it is easy to know T1∈TnΔ. From xus<xvs+1 and xus+1≥xvs+2, by Lemma 3, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Case 2. There is a public edge betweenP1 and P2.From thatW2≠∅,Δ≥3, and there exists public edge between P1 and P2, we know that there must exist a leaf node w neither equal to i nor equal to j, which makes the shortest path from w to r have no public edge with P1,P2. Denote the shortest path from the leaf node w to r by P3, and then the length of P3 is l+1. Otherwise, the difference in length between P3 and at least one of P1andP2 is greater than 1. From the discussion of case 1, we know that this will lead to a contradiction. Besides, there will be k=2+l. Otherwise, k>2+l, it will imply that the difference in lengthen between P3 and P1 is more than 1, and P3 has no public edge with P1. From the discussion of case 1, we know that this will lead to a contradiction.Suppose thatP1,P2,andP3 are shown in Figure 13, where P1 is u0u1u2⋯ut+1⋯r and P2 is v2v3⋯vt+1⋯r, where u0=i,v2=j, and there exists t≥2 such that, for ∀j≥t+1, we all have uj=vj. Let P3 be w1w2w3⋯wt+1⋯r, where w1 is denoted by w, and denote uk=r.Now, we consider the pathsP1 and P3.Forw1 is the leaf node in T∗ and u1 is the nonleaf node in T∗, then by Lemma 10, we get xw1<xu1. If there exists a natural number s that satisfies 1≤s≤t, which make that both xws<xus and xws+1≥xus+1 hold. Let T1=T∗−ws,ws+1−us,us+1+ws+1,us+us+1,ws, then it is easy to know T1∈TnΔ. From xws<xus and xws+1≥xus+1, by Lemma 3, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Hence, for any natural number s which satisfies 1≤s≤t, xws<xus, and xws+1≥xus+1 cannot hold meanwhile. And for xw1<xu1, then we have that, for any natural number s which satisfies 1≤s≤t+1, we all have xws<xus.Now we consider the pathsP2 and P3.Forv2 is the leaf node in T∗ and w2 is the nonleaf node in T∗, by Lemma 10, we get xv2<xw2. Since xvt+1=xut+1>xwt+1, then there exists a natural number s that satisfies 2≤s≤t, which make that both xvs<xws and xvs+1≥xws+1 hold. Let T2=T∗−vs,vs+1−ws,ws+1+ws+1,vs+vs+1,ws, then it is easy to know T2∈TnΔ. From xvs<xws and xvs+1≥xws+1, by Lemma 3, we know that ρT2>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.From the discussion of case 1 and case 2, we know that the hypothesis is not established. Therefore, (3) of Theorem17 holds.(4)
Assume that the proposition is not established, then there exist verticesi∈W2 and j∈W1 such that di,r<dj,r. From i∈W2, we know di,r≥2. Without loss of generality, we assume that the shortest path from r to i is rv1v2⋯vs and the shortest path from r to j is rw1w2⋯wk, where i=vsandj=wk. Then, we have that k>s and s≥2 hold. From i∈W2, we know that the shortest path from i to r must pass one of g1 and g2. Without loss of generality, we assume that the shortest path from i to r pass g1, then v1=g1. By (3) of Theorem 17, we know k=s+1.Sincevs is the leaf node in T∗ and wk−1 is the nonleaf node in T∗, then by Lemma 10, we get xwk−1>xvs. Let T1=T∗−vs−1,vs−wk−1,wk−2+wk−1,vs−1+vs,wk−2, it is easy to know T1∈TnΔ. From xwk−1>xvs, if xwk−2≤xvs−1, then by Lemma 3, we have that ρT1>ρT∗ holds. This implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ; hence, xwk−2>xvs−1. By mathematical induction, we get xwk−s>xvs−s−1, then we have that xw1>xv1 holds.We also can prove thatxw2>xg2 holds. Otherwise, xw2≤xg2. For xw1>xv1, let T2=T∗−w1,w2−v1,g2+w1,g2+v1,w2, it is easy to know T2∈TnΔ. From xw2≤xg2 and xw1>xv1, by Lemma 3, we have that ρT2>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Let T3=T∗−w1,w2+w1,g2+r,w2, it is easy to know T3∈TnΔ. From xr≥xw1 and xw2>xg2, by Lemma 3, we have that ρT3>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Hence, the hypothesis is not established; therefore, (4) of Theorem17 holds.(5)
Assume thatT∗ is not a rooted unicyclic graph with levels 3, and since W2≠∅, then T∗ is a rooted unicyclic graph with levels not less than 4. For there exists a vertex with degree 2 in VC, without loss of generality, we assume that dg2=2. From W2≠∅, the level of T∗ is not less than 4 and (4) of Theorem 17, and we know that there exists a vertex i∈W2 such that di,r≥3. Suppose that the shortest path from i to r is v1v2⋯vkr, where v1=i. Then, from di,r≥3, we know that k≥3 holds, and from dg2=2, we know that vk=g1 holds. Let T1=T∗−v1,v2−r,g2+r,v2+g2,v1, from vk=g1 and k≥3, we know T1∈TnΔ. And by Lemma 1, it is easy to prove xv2>xg2. For xv1≤xr, then by Lemma 3, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ; hence, the hypothesis is not established. Therefore, T∗ is a rooted unicyclic graph with levels 3.Next, we prove that, for∀j∈W1, we all have dj,r=1. Otherwise, assume that there exists a vertex j0∈W1 such that dj0,r≥2. And for T∗ is a rooted unicyclic graph with levels 3, then we have that dj0,r=2 holds. Suppose that the shortest path from j0 to r is w1w2r, where w1=j0, w2 is neither equal to g1 nor equal to g2. From that there exists a vertex with degree 2 in VC, without loss of generality, assume that dg2=2. Then, from Lemma 1, it is easy to prove that xg2≤xw2 holds. By Lemma 10, we can get xg1>xw1. Let T2=T∗−g1,g2−w1,w2+g1,w2+g2,w1, then it is easy to know T2∈TnΔ. From xg2≤xw2 and xg1>xw1, by Lemma 3, we have that ρT2>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Hence, the hypothesis is not established. Therefore, for ∀j∈W1, we all have that dj,r=1 holds.In conclusion, (5) of Theorem17 holds.
For the relationship between the maximal-adjacency-spectrum unicyclic graphs inTnΔ and the almost full-degree unicyclic graphs, we have the following theorem.Figure 12
A graph with no common edge between two paths.Figure 13
A graph with common edge(s) between two paths.Theorem 18.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, x=x1,x2,…,xnT is the Perron vector of T∗, and r is the vertex that corresponds to a maximum component in the component of the Perron vector of T∗. Let T∗ be the rooted unicyclic graph with root node r, then T∗ is an almost full-degree unicyclic graph with root node r.Proof.
Suppose that the only circle inT∗ is C. From Theorem 16, we get VC=3. By Theorem 12, we know r∈VC, then let VC=r,g1,g2. Denote W1 = {ii is the leaf node of T∗, and the shortest path from i to r neither pass g1 nor pass g2}, W2 = {ii is the leaf node of T∗, and the shortest path from i to r either pass g1 or pass g2}.
Now according toT∗, we discuss the following three cases:Case 1. There exist nonfull internal vertices inT∗ and exist nonfull internal vertices in C.For case 1, according to whether there exist the vertices with degree 2 inC or not, we discuss the following two subcases:Subcase 1. There exist nonfull internal vertices inC and exist the vertices with degree 2 in C.For subcase 1, according to the number of the vertices with degree 2 inC, we continue to discuss the following two subcases:Subcase 1.1. There are at least two vertices with degree 2 inC.In this case, it is easy to knowW2=∅; by (1) of Theorem 17, we know maxi∈W1di,r=1; thus, T∗≅Tn,2Δ, where Tn,2Δ is shown in Figure 2. Hence, T∗ is an almost full-degree unicyclic graph with root node r.Subcase 1.2. There is only one vertex with degree 2 inC.In this case, it is easy to knowW2≠∅. For there is only one vertex with degree 2 in C, then by (5) of Theorem 17, we know that T∗ is a rooted unicyclic graph with levels 3. And for ∀j∈W1, we all have that dj,r=1 holds; hence, it is easy to know that T∗ is an almost full-degree unicyclic graph with root node r.Subcase 2. There exist nonfull internal vertices inC, and the degree of all the vertices in C is not equal to 2.In this case, it is easy to know that the degree of all the vertices inC are more than 2. From that, there exist nonfull internal vertices in C, and from Theorem 14, we know that there is only one nonfull internal vertex in C. Without loss of generality, assume that g2 is the nonfull internal vertex in C, then we have that dg1=Δ and 3≤dg2<Δ holds. And by Theorem 13, we know that there is only one nonfull internal vertex in T∗. Then, it is easy to know that W1≠∅,W2≠∅ and mini∈W2di,andr≥2 hold.Supposemaxi∈W1di,r=m, then m=1. Assume that m=1 is not established, then we have m≥2. Now choose a vertex u1 which satisfies du1,r=m and u1∈W1 in T∗. Choose u2∈NT∗u1, then xg2≤xu2. Otherwise, xg2>xu2, let T1=T∗−u1,u2+g2,u1, from m≥2 and g2 is the nonfull internal vertex in T∗, we know T1∈TnΔ. And by Lemma 1, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Let T2=T∗−g1,g2−u1,u2+g2,u1+u2,g1, it is easy to know T2∈TnΔ. From xg2≤xu2, and by Lemma 10, we get xg1>xu1; then by Lemma 3, we have that ρT2>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Hence, the hypothesis is not established, and then we have m=1. From mini∈W2di,r≥2, we get maxi∈W2di,r≥2. And for maxi∈W1di,r=1, by (3) of Theorem 17, we have that maxi∈W2di,r=2 holds. Thus, maxi∈W2di,r=mini∈W2di,r=2, from maxi∈W1di,r=1, and from that there is only one nonfull internal vertex in T∗, we know that T∗ is an almost full-degree unicyclic graph with root node r.By consideration of the discussion of subcase 1 and subcase 2 in case 1, we know that if there exist nonfull internal vertices inT∗, and there exist nonfull internal vertices in C, then T∗ is an almost full-degree unicyclic graph with root node r.Case 2. There exist nonfull internal vertices inT∗, and there is no nonfull internal vertex in C.Since there exist nonfull internal vertices inT∗, and there is no nonfull internal vertex in T∗, then there exist nonfull internal vertices out of the circle of T∗. By Theorem 13, we know that there only one nonfull internal vertex in T∗.We denoter by u0, let w be the only nonfull internal vertex in T∗. Denote that dr,w=l; obviously, l≥1. Choose a path P1 in which u0 is the starting point and a leaf node of T∗ is the terminal point, and P1 passes w. Suppose that P1 is u0u1⋯ul⋯uk, where k>l. From the definition of P1, we know ul=w, then we have that ul is the only nonfull internal vertex in T∗.Assume thatT∗ is not an almost full-degree unicyclic graph with root node r. If k=l+1, then from that there is only one nonfull internal vertex in T∗, and from Theorem 17, we have that, in T∗, there exists a path P2 in which u0 is the starting point and a leaf node of T∗ is the terminal point. Besides, P2 has no public edge with P1, and the length of P2 is l+2. Suppose that P2 is u0v1⋯vl+1vl+2, where vl+2 is the leaf node, then the relationship between P1 and P2 is shown in Figure 14. If k=l+2, then from that, there is only one nonfull internal vertex in T∗ and from Theorem 17, we know that, in T∗, there exists a path P3 in which u0 is the starting point and a leaf node of T∗ is the terminal point. Besides, P3 has no public edge with P1, and from Theorem 17, we know that the length of P3 is not less than l+1. Hence, suppose that P3 is u0v1⋯vl+1⋯, and the relationship between P1 and P3 is shown in Figure 15. If k≥l+3, from that there is only one nonfull internal vertex in T∗, and from Theorem 17, we know that, in T∗, there exists a path P4 in which u0 is the starting point and a leaf node of T∗ is the terminal point. Besides, P4 has no public edge with P1, and from Theorem 17, we know that the length of P4 is not less than l+2. Hence, suppose that P4 is u0v1⋯vl+2⋯, and the relationship between P1 and P4 is shown in Figure 16.Now according to the relationship betweenk and l, we discuss the following two subcases: let k=l+1 or k≥l+3 be the subcase 1, and let k=l+2 be the subcase 2.Subcase 1. Ifxul≥xvl+1, let T1=T∗−vl+2,vl+1+vl+2,ul, then it is easy to know T1∈TnΔ. By Lemma 1, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Ifxul<xvl+1, and for xu0=xr≥xv1, we know that there exists a natural number k that satisfies 2≤k≤l+1, which make that xuk−1<xvk and xuk−2≥xvk−1 hold. Let T2=T∗−vk−1,vk−uk−2,uk−1+vk,uk−2+uk−1,vk−1, it is easy to know T2∈TnΔ. From xuk−1<xvk and xuk−2≥xvk−1, and by Lemma 3, we have that ρT2>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Hence, subcase 1 of case 2 implies a contradiction.Subcase 2. In subcase 2, according to whethervl+1 is the leaf node or not, we discuss the following two subcases:Subcase 2.1.vl+1 is the leaf node.In this case, by Lemma10, we have xvl+1<xul+1.Ifxvl≥xul, and for xvl+1<xul+1, let T1=T∗−vl+1,vl−ul+1,ul+vl,ul+1+vl+1,ul, it is easy to know T1∈TnΔ. By Lemma 3, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ; hence, xvl<xul. Let T2=T∗−vl,vl+1+vl+1,ul, it is easy to know T2∈TnΔ, and by Lemma 1, we have that ρT2>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Subcase 2.2.vl+1 is not the leaf node.In this case, if there exists a natural numberi which satisfies 1≤i≤l+1 such that xvi≤xul, then let T3=T∗−vi,vi+1+vi+1,ul, it is easy to know T3∈TnΔ. By Lemma 1, we have that ρT3>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Hence, for arbitrary vertex vi which satisfies 1≤i≤l+1, we all have xvi>xul. Specially, we have xvl+1>xul.Fromxu0≥xv1 and xvl+1>xul, we know that there exists a natural number k that satisfies 2≤k≤l+1, which makes both xvk>xuk−1 and xvk−1≤xuk−2 hold. Let T4=T∗−vk,vk−1−uk−1,uk−2+vk,uk−2+uk−1,vk−1, it is easy to know T4∈TnΔ. From xvk>xuk−1 and xvk−1≤xuk−2, by Lemma 3, we have that ρT4>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Hence, in subcase 2, no matter whethervl+1 is leaf node or not, it will imply a contradiction.By consideration of the subcase 1 and subcase 2 in case 2, we know that the hypothesis is not established. Then, we know that when there exists nonfull internal vertices inT∗, and there exists no nonfull internal vertices in C, T∗ is an almost full-degree unicyclic graph with root node r.Case 3. There is no nonfull internal vertex inT∗, then there are only full-degree vertices and leaf nodes in T∗. From Theorem 17, we know that T∗ is an almost full-degree unicyclic graph with root node r.In conclusion, for each of the cases,T∗ is still an almost full-degree unicyclic graph with root node r, then we have that Theorem 18 holds.
Assume thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, T∗≇Tn,2Δ and there is only one nonfull internal vertex in T∗, then from the position of the nonfull internal vertex in T∗, we have the following conclusion, as in the following theorem.Figure 14
Vertex graphs of two paths underk = l + 1.Figure 15
Vertex graphs of two paths underk = l + 2.Figure 16
Vertex graphs of two paths underk > l + 2.Theorem 19.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, x=x1,x2,…,xnT is the Perron vector of T∗, r is the vertex that corresponds to a maximum component in the component of the Perron vector of T∗, and T∗ is the rooted unicyclic graph with root node r, T∗ has only one nonfull internal vertex u. Suppose that C is the only one circle in T∗, and VC=r,g1,g2, denote that W1 = {ii is the leaf node of T∗, and the shortest path from i to r neither pass g1 nor pass g2}, W2 = {ii is the leaf node of T∗, and the shortest path from i to r either pass g1 or pass g2}. Assume that T∗≇Tn,2Δ, that is W2≠∅, then the following propositions are established:(1)
If the distances from all leaves ofT∗ to r are all equal, then there exists a leaf node i∈W1 which makes i,u is a pendant edge.(2)
If there are two leavesi,j in T∗ which make di,r≠dj,r and maxi∈W1di,r=mini∈W1di,r, then either there exists a leaf node j1∈W2 which makes u,j1 is a pendant edge or u∈VC and du=2.(3)
Ifmaxi∈W1di,r≠mini∈W1di,r, then there exists a leaf node j1∈W1 which makes u,j1 is a pendant edge.Proof.
From Theorem18, we know that T∗ is an almost full-degree unicyclic graph with root node r; suppose that T∗ is a rooted unicyclic graph with levels k, then u is in the k−1 level.(1)
FromW2≠∅, we know maxi∈W2di,r≥2; thus, T∗ is a rooted unicyclic graph with the levels not less than 3. First, we have that dg1≥3 and dg2≥3 holds. Otherwise, there is at least one of the two equations, dg1=2 and dg2=2, holds. From W2≠∅, we know that there is at most one of the two equations which are dg1=2 and dg2=2 holds. Hence, there is only one of the two equations which are dg1=2 and dg2=2 holds. By (5) of Theorem 17, we get that, for ∀j∈W1, we all have that dj,r=1 holds; hence, maxi∈W1di,r=1. Then, we can get maxi∈W2di,r>maxi∈W1di,r, and this implies a contradiction with the distances from all leaves of T∗ to r are all equal; hence, dg1≥3 and dg2≥3.Assume that (1) of Theorem19 is not established, then there exists u1∈W2 such that u1,u is a pendant edge of T∗. Let u1u2⋯umr be the shortest path from u1 to r, where u2=u, um=g1, or um=g2. Without loss of generality, we assume that um=g1, from u1∈W2, we know m≥2.For the range of the value ofm, we must have that m≥3 holds. Otherwise, m=2, since the distances from all the leaf nodes in T∗ to r are equal, then for ∀j1∈W1, we all have dj1,r=2. Choose j∈W1; let v1v2r be the shortest path from j to r, where v1=j,v2≠g1 and v2≠g2. By Lemma 10, we have that xg2>xv1 holds. From um=g1 and m=2, we get g1=u2, and by u2=u, we have um=u=g1. In addition, for the relationship of xg1 and xv2, we must have xg1≤xv2. Otherwise, xg1>xv2, let T1=T∗−v1,v2+v1,g1, and it is easy to know T1∈TnΔ. By Lemma 1, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Let T2=T∗−g1,g2−v1,v2+g2,v2+g1,v1, then it is easy to know T2∈TnΔ. From xg2>xv1 and xg1≤xv2, by Lemma 3, we have that ρT2>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Thus, the hypothesis does not hold; that is, m≥3 holds.Since for any two leaf nodesi,j in T∗, we all have di,r=dj,r. And since du1,r=m, where u1∈W2, then for ∀j1∈W1, we all have that dj1,r=m holds. Choose j1∈W1, then we have that dj1,r=m holds. Without loss of generality, we assume that the shortest path from j1 to r is v1v2⋯vmr, where v1=j1,vm≠g1 and vm≠g2.Sinceu2=u is the nonfull internal vertex, then we have xu2<xv2. Otherwise, xu2≥xv2, let T3=T∗−v1,v2+v1,u2, and it is easy to know T3∈TnΔ. By Lemma 1, we have that ρT3>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Hence, xu2<xv2.Form≥3, hence u3 and v3 have the meaning. For the relationship between xu3 and xv3, we have that xu3<xv3 holds. Otherwise, xu3≥xv3, let T4=T∗−u3,u2−v3,v2+v3,u2+v2,u3, and it is easy to know T4∈TnΔ. Since xu3≥xv3 and xu2<xv2, by Lemma 3, we have that ρT4>ρT∗ holds, this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. By mathematics induction, we can prove that, for any natural number i which satisfies 2≤i≤m, we all have that xui<xvi holds.From Lemma10, we can get xu2>xv1. For the relationship between xu3 and xv2, we have xu3>xv2. Otherwise, xu3≤xv2, let T5=T∗−u3,u2−v1,v2+v1,u3+v2,u2, and it is easy to know T5∈TnΔ. From xu2>xv1 and xu3≤xv2, by Lemma 3, we have that ρT5>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. By mathematics induction, we can prove that, for any natural number i which satisfies 2≤i≤m, we all have that xui>xvi−1 holds.Hence, we havexvm>xum>xvm−1.For the relationship betweenxg2 and xvm, we have xg2>xvm. Otherwise, xg2≤xvm. Let T6=T∗−um,g2−vm−1,vm+g2,vm−1+vm,um, and it is easy to know T6∈TnΔ. From xg2≤xvm and xum>xvm−1, by Lemma 3, we have that ρT6>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Thus, we have thatxg2>xvm>xum>xvm−1 holds, let T7=T∗−um,g2−vm−1,vm+g2,vm+vm−1,um, and it is easy to know T7∈TnΔ. By Lemma 7, we have that ρT7>ρT∗ holds, this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.In conclusion, the hypothesis does not hold; hence, (1) of Theorem19 holds.(2)
Assume that (2) of Theorem19 does not hold, then the nonfull internal vertex u in T∗ should satisfy that there exists v1∈W1 such that v1,u is a pedant edge. For there exist two leaf nodes i,j in T∗ such that di,r≠dj,r and maxi∈W1di,r=mini∈W1di,r. Hence by Theorem 17, we know maxj2∈W2dj2,r=maxj1∈W1dj1,r+1; thus, u is in the third last level of T∗, and this implies a contradiction with T∗ is an almost full-degree unicyclic graph with root node r. Hence, the hypothesis does not hold, and then, (2) of Theorem 19 holds.(3)
SinceW2≠∅ and maxi∈W1di,r≠mini∈W1di,r, by Theorem 17, we get maxi∈W2di,r=mini∈W2di,r=maxi∈W1di,r=mini∈W1di,r+1. And it is easy to know mini∈W1di,r≥1; hence, maxi∈W1di,r≥2. From (5) of Theorem 17, we get that dg1≥3 and dg2≥3 hold.Assume that (3) of Theorem19 does not hold, since dg1≥3 and dg2≥3, the nonfull internal vertex u in T∗ should satisfy that there exists j1∈W2 such that j1,u is a pedant edge of T∗. From W2≠∅,dg1≥3, and dg2≥3, we have that dj1,r≥2 holds.Now we will provedj1,r≥3. Assume that dj1,r≥3 does not hold, then we have dj1,r=2, by maxi∈W2di,r=mini∈W2di,r=maxi∈W1di,r=mini∈W1di,r+1, we know that there exists i∈W1 such that di,r=2. Let the shortest path from i to r be v1v2r, where v1=i,v2≠g1, and v2≠g2, and let the shortest path from j1 to r be u1u2r, where j1=u1,u2=u, and u2 is either g1 or g2. Without loss of generality, we assume that u2=g1, and it is easy to know xv2>xu2; otherwise, xv2≤xu2. Let T1=T∗−v1,v2+u2,v1, then it is easy to know T1∈TnΔ, and by Lemma 1, we have that ρT1>ρT∗ holds. This implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ; hence, xv2>xu2. For u2=g1, thus, we get xv2>xg1. And for v1 is the leaf node of T∗, g2 is the nonleaf node of T∗, and then by Lemma 10, we have xg2>xv1. Thus, we get that xv2>xg1 and xg2>xv1 hold. Let T2=T∗−v1,v2−g1,g2+v2,g2+g1,v1, then it is easy to know T2∈TnΔ. By Lemma 3, we have that ρT2>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Thus, the hypothesis does not hold; hence, dj1,r≥3.Suppose that the shortest path fromj1 to r is u1u2⋯um+1r, where u1=j1, u2=u, and um+1 = g1 or um+1 = g2. Without loss of generality, we assume that um+1=g1. From dj1,r≥3, we can get m≥2. Since maxi∈W2di,r=mini∈W2di,r=maxi∈W1di,r=mini∈W1di,r+1, there exists i∈W1 such that di,r=dj1,r.Suppose that the shortest path fromi to r is v1v2⋯vm+1r, where v1=i,vm+1≠g1, and vm+1≠g2. For the relationship between xv2 and xu2, we have xv2>xu2. Otherwise, xv2≤xu2. Let T3=T∗−v1,v2+u2,v1, then it is easy to know T3∈TnΔ. And by Lemma 1, we have that ρT3>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. In addition, we also can prove xv3>xu3; otherwise, xv3≤xu3. Let T4=T∗−u2,u3−v2,v3+u2,v3+v2,u3, then it is easy to know T4∈TnΔ. From xv2>xu2 and xv3≤xu3, by Lemma 3, we have that ρT4>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ; hence, xv3>xu3. By mathematics induction, we can prove that, for any natural number i which satisfies 2≤i≤m+1, we all have that xvi>xui holds.By Lemma10, we can get xu2>xv1. For the relationship between xu3 and xv2, we have xu3>xv2. Otherwise, xu3≤xv2. Let T5=T∗−u3,u2−v1,v2+v1,u3+v2,u2, then it is easy to know T5∈TnΔ. From xu2>xv1 and xu3≤xv2, by Lemma 3, we have that ρT5>ρT∗ holds. This implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. By mathematics induction, we can prove that, for any natural number i which satisfies 2≤i≤m+1, we all have that xui>xvi−1 holds.Hence, we havexvm+1>xum+1>xvm.Besides, for the relationship betweenxg2 and xvm+1, we have xg2>xvm+1. Otherwise, xg2≤xvm+1. Let T6=T∗−g1,g2−vm,vm+1+g1,vm+1+g2,vm, then it is easy to know T6∈TnΔ. By g1=um+1 and xum+1>xvm, we can get xg1>xvm. And for xg2≤xvm+1, by Lemma 3, we have that ρT6>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Let T7=T∗−g2,um+1−vm,vm+1+g2,vm+1+um+1,vm, then it is easy to know T7∈TnΔ. From xg2>xvm+1 and xvm+1>xum+1>xvm, we can get xg2>xvm+1>xum+1>xvm. By Lemma 7, we have ρT7>ρT∗, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.In conclusion, the hypothesis does not hold, and hence, (3) of Theorem19 holds.
Finally, we give the structure of the maximal-adjacency-spectrum unicyclic graphs in the set of unicyclic graphs given the number of vertices and the maximum degree; in the following Theorem, we describe the structure of the maximal-adjacency-spectrum unicyclic graphs inTnΔ.Theorem 20.
Suppose thatT∗∈TnΔ, and T∗ is a rooted unicyclic graph with root vertex which is the vertex that corresponds to a maximum component in the component of the Perron vector of T∗, then T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ if and only if T∗≅HnΔ.Proof.
Necessity, suppose thatT∗∈TnΔ, T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, let x=x1,x2,…,xn be the Perron vector of T∗, and r be the vertex that corresponds to a maximum component of x. Suppose that T∗ is a rooted unicyclic graph with root node r; from Theorem 18, we have that T∗ is an almost full-degree unicyclic graph with root node r.
Denote the only circle inT∗ by C; from Theorem 16, we have VC=3. Again by Theorem 12, we could suppose that VC=r,g1,g2. Denote W1 = {ii is the root node of T∗, and the shortest path from i to r neither pass g1 nor pass g2}, W2 = {ii is the root node of T∗, and the shortest path from i to r either pass g1 or pass g2}.
When the level ofT∗ is 2, obviously, T∗≅HnΔ.
When the level ofT∗ is 3, if there is no nonfull internal vertex in C, then it is easy to know that T∗≅HnΔ holds. If there exists nonfull internal vertex in C, then according to the degree of the nonfull internal vertex in C, we discuss the following two cases:Case 1. There is one nonfull internal vertex inC with degree 2.In this case, we can provemaxdg1,dg2>2. Otherwise, maxdg1,dg2=2; that is, we have that dg1=dg2=2 holds, and thus, W2=∅. From (1) of Theorem 17, we know T∗≅Tn,2Δ, then T∗ is a rooted unicyclic graph with levels 2, and this implies a contradiction with the level of T∗ is 3. Without loss of generality, we assume that maxdg1,dg2=dg1; hence, dg1>2. And for there is one nonfull internal vertex with degree 2 in C, hence dg2=2, by (5) of Theorem 17, we get that, for ∀i∈W1, we all have that di,r=1 holds. Therefore, T∗≅HnΔ.Case 2. The degree of all the nonfull internal vertices inC is not less than 3.In this case, from Theorem14, we can get that there is only one nonfull internal vertex in C. Without loss of generality, we assume that g2 is the nonfull internal vertex. For the degree of all the nonfull internal vertices in C are not less than 3, the level of T∗ is 3, and VC=r,g1,g2; we have maxj∈W2dj,r=minj∈W2dj,r=2. Then, by (4) of Theorem 17, we get maxj∈W1dj,r≤2.We can provemaxj∈W1dj,r=1. Otherwise, there exists i∈W1 such that di,r=2. Suppose that the shortest path from i to r is ru2u1, where u1=i, and u2 is neither g1 nor g2. According to the relationship between xg2 and xu2, we have xg2<xu2. Otherwise, xg2≥xu2, let T1=T∗−u1,u2+u1,g2, and it is easy to know T1∈TnΔ. By Lemma 1, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Let T2=T∗−u1,u2−g1,g2+g1,u2+u1,g2, then it is easy to know T2∈TnΔ. Again by Lemma 10, we get xg1>xu1. And we have proved xg2<xu2; hence, by Lemma 3, we have that ρT2>ρT∗ holds. This implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ; hence, maxj∈W1dj,r=1. From that maxj∈W2dj,r=minj∈W2dj,r=2,maxj∈W1dj,r=1 and there is only one nonfull internal vertex in C, we know that T∗≅HnΔ holds.In conclusion, when the level ofT∗ is 3, we have that T∗≅HnΔ holds.
Now we discuss the case in which the level ofT∗ is not less than 4.
Suppose thatmaxi∈W1∪W2di,r=k, from the level of T∗ is not less than 4, we know k≥3.
DenoteQ1 = {i∈VT∗di,r=k−1, and the shortest path from i to r pass neither g1 nor g2}, Q2 = {i∈VT∗di,r=k−1, and the shortest path from i to r pass either g1 or g2}.
From Theorem18, we get that T∗ is an almost full-degree unicyclic graph, then if there exists nonfull internal vertex in T∗, we have that the nonfull internal vertex in the second last level of T∗. And since the level of T∗ is not less than 4, if there exists nonfull internal vertex in T∗, then the nonfull internal vertex must belong to the set of VT∗\VC. Again from Theorem 13, we get that there is only one nonfull internal vertex in T∗. Thus, when the level of T∗ is not less than 4, there is at most one nonfull internal vertex in T∗.
When the level ofT∗ is not less than 4, we discuss the following three cases according to the structure of T∗.Case 1. There is no nonfull internal vertex inT∗. At this time, we can discuss the following three subcases:Subcase 1. When for arbitrary leaf nodesi,j in T∗, we all have di,r=dj,r.At this time, it is easy to know thatT∗≅HnΔ holds.Subcase 2. When there exist two leaf nodesi,j in T∗ such that di,r≠dj,r and maxi∈W1di,r=mini∈W1di,r.At this time, from Theorem17, we get maxi∈W1di,r=mini∈W1di,r=maxi∈W2di,r−1=k−1. And for ∀q1∈Q1, we all have that dq1=1 holds.Subcase 3. Whenmaxi∈W1di,r≠mini∈W1di,r.At this time, from Theorems17 and 19, we know that the following two conclusions hold. ① maxi∈W2di,r=mini∈W2di,r=maxi∈W1di,r=mini∈W1di,r+1. ② ∀q2∈Q2 all have that dq2=Δ holds.Case 2. There is only one nonfull internal vertexu in T∗, and one of the brothers of u is leaf node.Now, it is easy to know that there exist two leaf node nodesi,j in T∗ such that di,r≠dj,r, then according to case (2), we discuss the following two subcases:Subcase 1. When there exist two leaf nodesi,j in T∗, which make di,r≠dj,r and maxi∈W1di,r=mini∈W1di,r.At this time, from Theorems17 and 19, we know that the following three conclusions hold: ① maxi∈W1di,r=mini∈W1di,r=maxi∈W2di,r−1=k−1; ② ∀q1∈Q1 all have that dq1=1 holds; ③ the nonfull internal vertex u∈Q2.Subcase 2. Whenmaxi∈W1di,r≠mini∈W1di,r.From Theorems17 and 19, we know that the following three conclusions hold: ① maxi∈W2di,r=mini∈W2di,r=maxi∈W1di,r=mini∈W1di,r+1. ② ∀q2∈Q2 all have that dq2=Δ holds. ③ The nonfull internal vertex u∈Q1.Case 3. There is only one nonfull internal vertexu in T∗, and all the brothers of u are full-degree vertices.According to case (3), we could discuss the following three subcases:Subcase 1. When arbitrary leaf nodesi,j in T∗ all have di,r=dj,r.At this time, from Theorem19, we get that the nonfull internal vertex u∈Q1, and ∀q2∈Q2 all have that dq2=Δ holds. And for there is only one nonfull internal vertex in T∗, then we have that, for ∀j1∈Q1\u, we all have dj1=Δ; hence, T∗≅HnΔ holds.Subcase 2. When there two exist leaf nodesi,j in T∗, which make di,r≠dj,r and maxi∈W1di,r=mini∈W1di,r.At this time, from Theorem19, we get that the nonfull internal vertex u∈Q2. Since there exist two leaf node nodes i,j such that di,r≠dj,r and maxi∈W1di,r=mini∈W1di,r in T∗, by Theorem 17, we get maxi∈W1di,r=mini∈W1di,r=k−1.Subcase 3. Whenmaxi∈W1di,r≠mini∈W1di,r.At this time, from Theorem19, we get u∈Q1. Since maxi∈W1di,r≠mini∈W1di,r, by (3) and (4) of Theorem 17, we can get maxi∈W2di,r=mini∈W2di,r=maxi∈W1di,r=mini∈W1di,r+1. And for there is only one nonfull internal vertex u in T∗, and u∈Q1; hence, for ∀q2∈Q2, we all have dq2=Δ.In the following, we call the subcases (3.2) and (3.3)” case 3″ and the subcases (1.2), (1.3), (2.1), and (2.2) “case 4”.
Sincemaxi∈W1∪W2di,r=kk≥3, we have that T∗ is a rooted unicyclic graph with levels k+1.
Now according to the notation of the vertices inT∗, we make the following instructions: ① except r,g1,g2, if wi∈VT∗, then let wi express one of the vertices in the bottom layer of the first i of T∗. ② If wi∈VT∗, we denote wjj>i the ancestor of wi, which is in the bottom layer of the first j of T∗, (note: wi can equal to any one of the vertex r,g1,g2, and g1 does not express that g1 is in the first last level of T∗ and g2 does not express that g2 is in the second last level of T∗. The above notations in ① and ② are still established when w is changed for any other vertex, which is not g).
Assume thatT∗≇HnΔ, then the structure of T∗ must be as the following case 3 or case 4 shown.Case 3. From the discussion of subcases 3.2 and 3.3, we know that there must exist a leaf nodes2 and an nonfull internal vertex u in T∗ (it is easy to know that u is in the second last level of T∗, denote r2=u), which make u,s2 satisfy the following properties: ① s2 at least has one full-degree brother. ② The common direct ancestor of s2 and u of the nearest generation is in the bottom layer of the first l of T∗, and l≥4. We choose v2 a full-degree brother of s2, denote the common direct ancestor of s2 and u of the nearest generation is rll≥4, then the relationship of the vertices in case 1 is shown in Figure 17, where in Figure 17, u2 is a brother of u and du2=Δ.Ifxr2≥xv2, then let T1=T∗−v1,v2+v1,r2, it is easy to know T1∈TnΔ. And by Lemma 1, we can get ρT1>ρT∗, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ; hence, xr2<xv2. And from Theorem 20, we know xr2>xs2.LetT2=T∗−s2,s3−r2,r3+r2,s3+s2,r3, and it is easy to know that T2∈TnΔ. If xr3≤xs3, from xr2>xs2, and by Lemma 3, we have that ρT2>ρT∗ holds. This implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ; hence, xr3>xs3. Let T3=T∗−v2,s3−r2,r3+r2,s3+v2,r3, then it is easy to know that T3∈TnΔ. From xr2<xv2 and xr3>xs3, by Lemma 3, we have that ρT3>ρT∗ holds. This implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Hence, the hypothesis is not established; therefore, T∗≅HnΔ.Case 4. ForT∗ is an almost full-degree unicyclic graph with root node r, T∗≇HnΔ, and from the discussion of subcase 1.2, subcase 1,3, subcase 2.1, and subcase 2.2, we know that there must exist two leaf nodes r2,s2 in the second level of T∗, which satisfy the following properties.There is a cousin or brotheru2 of the nonleaf vertex which is of the nearest generation of r2, there also exists a cousin or brother v2 of the nonleaf vertex which is of nearest generation of s2. This makes that rt (where t≥3) is the common direct ancestor of r2 and u2 of the nearest generation, sm (where m≥3) is the common direct ancestor of s2 and v2 of the nearest generation, w is the common direct ancestor of r2,u2,s2,andv2 of the nearest generation, and u2 and v2 satisfy that u2≠v2,rt≠w, sm≠w and rt≠sm.Without loss of generality, we assume thatt≥m. Then, the relationship of the vertices in case 2 is shown as Figure 18. From the method of marking the index of the vertices in T∗, we know rt=ut,sm=vm, and st=vt.First, by Lemma10, it is easy to know maxxr2,xs2<minxu2,xv2.Ifxut≥xst, then xrt≥xvt. Since xr2<xv2, there is a natural number k that satisfies 2≤k≤t−1, which make xrk<xvk and xrk+1≥xvk+1. Let T1=T∗−rk+1,rk−vk+1,vk+rk+1,vk+vk+1,rk, then it is easy to know T1∈TnΔ. From xrk<xvk and xrk+1≥xvk+1, by Lemma 3, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Ifxut<xst, since xu2>xs2, there exists a natural number k that satisfies 2≤k≤t−1, which makes xuk>xsk and xuk+1≤xsk+1. Let T2=T∗−uk+1,uk−sk+1,sk+uk+1,sk+sk+1,uk, then it is easy to know T2∈TnΔ. From xuk>xsk and xuk+1≤xsk+1, by Lemma 3, we have that ρT2>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Hence, the hypothesis is not established; therefore,T∗≅HnΔ.In conclusion, ifT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, and the level of T∗ is not less than 4, we have that T∗≅HnΔ holds.
By considering the discussion of all the cases according to the level ofT∗, we know that if T∗∈TnΔ, T∗ is a unicyclic graph in which the vertex corresponding to a maximum component in the component of the Perron vector of T∗ is the root node, and T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, then T∗≅HnΔ.
Sufficiency, suppose thatT∗∈TnΔ, T∗ is a rooted unicyclic graph in which the vertex corresponding to a maximum component in the component of the Perron vector of T∗ is the root node, and T∗≅HnΔ. It is easy to know TnΔ<+∞, then there must exist maximal-adjacency-spectrum unicyclic graph in TnΔ. Suppose that T∗∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, and let T∗∗ be a rooted unicyclic graph in which the vertex corresponding to a maximum component in the component of the Perron vector of T∗ is the root node. Then by the necessity of Theorem 20, we know T∗∗≅HnΔ. And for T∗≅HnΔ, then T∗∗≅T∗; thus, T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.
From Theorem20, we know that if we regard two isomorphic graphs as one graph, then there is only one maximal-adjacency-spectrum unicyclic graph in TnΔ, and the maximal-adjacency-spectrum unicyclic graphs in TnΔ is HnΔ.Figure 17
Vertex graph in case 1.Figure 18
Vertex graph in case 2.


## 3.1. The Properties of the Maximal-Adjacency-Spectrum Unicyclic Graphs inTnΔ

First, we give the properties of the Perron vector of the maximal-adjacency-spectrum unicyclic graphs inTnΔ, as in the following theorems:Theorem 11.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, if x=x1,x2,…,xnT is the Perron vector of T∗, then the degree of the vertices that corresponds to all largest components in the component of x is Δ.Proof.
Assume that the proposition is not established, we suppose that there exists a vertexv∗ in T∗ such that xv∗=max1≤i≤nxi and dv∗<Δ. Denote p=dv∗, it is obvious that p≥2; hence, 2≤p<Δ. We choose a vertex u with degree Δ in VT∗, suppose that NT∗u=v1,v2,…,vΔ. For T∗ is a unicyclic graph, it is easy to know that there are Δ−p vertices vj1,vj2,…,vjΔ−p in the set of NT∗u\NT∗v∗ such that T∗−u,vj1−u,vj2−⋯−u,vjΔ−p+v∗,vj1+v∗,vj2+⋯+v∗,vjΔ−p is still a simple connected graph. Denote T1=T∗−u,vj1−u,vj2−⋯−u,vjΔ−p+v∗,vj1+v∗,vj2+⋯+v∗,vjΔ−p, then it is easy to know T1∈TnΔ. Again by xv∗≥xu, by Lemma 2, we get ρT1>ρT∗, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ; hence, the hypothesis is not established; therefore, Theorem 11 holds.Theorem 12.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, and the only circle in T∗ is C, x=x1,x2,…,xnT is the Perron vector of T∗, if the component xu∗ which corresponds to the vertex u∗ in x satisfies that xu∗=max1≤i≤nxi, then u∗∈VC.Proof.
Assume that the proposition is not established, we suppose that there exists a vertexu∗ in T∗ such that xu∗=max1≤i≤nxi and u∗∈VT∗\VC. From xu∗=max1≤i≤nxi and Theorem 11, we get du∗=Δ. For du∗=Δ,u∗∈VT∗\VC and T∗ is a unicyclic graph, we know that there exists a path u∗u1⋯ukk≥1 whose length is k in T∗, which makes u∗∉VC,u1∉VC,…,uk∉VC, u1,u2,…,uk are difference with each other, and uk is the leaf node.
First, for∀v∈VC, we have xv>xuk. Otherwise, suppose there exists a vertex v1 in VC such that xv1≤xuk. Now according to the value of dv1, we discuss the following two cases:Case 1.dv1<Δ.Sincev1∈VC, we have NT∗v1≥2; thus in the set of VT∗, there exists a vertex v2 which satisfies v2∈NT∗v1 such that T∗−v2,v1+v2,uk is still a simple connected graph. Denote T1=T∗−v2,v1+v2,uk, then it is easy to know T1∈TnΔ. By Lemma 1, we get ρT1>ρT∗, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Case 2.dv1=Δ.In this case, it is easy to know that in the set ofNT∗v1, there exist Δ−1 vertices v2,v3,…,vΔ such that T∗−v1,v2−v1,v3−⋯−v1,vΔ+uk,v2+uk,v3+⋯+uk,vΔ is still a simple connected graph. Denote T1=T∗−v1,v2−v1,v3−⋯−v1,vΔ+uk,v2+uk,v3+⋯+uk,vΔ, then it is easy to know T1∈TnΔ. From xv1≤xuk, by Lemma 2, we can get ρT1>ρT∗, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.
From the above discussion of the two cases, we know that the hypothesis is not established. Hence, for∀v∈VC, we all have that xv>xuk holds.
Second, denoteu∗ by u0, suppose that v is the vertex which is nearest to u∗ in C. Choose two vertices v1andv2 different from v in C, then xu0≥xv1,xu0≥xv2,xv1>xuk, and xv2>xuk. Thus, we have that there exists a natural number l which satisfies 1≤l≤k such that at least one of the following two inequality groups: ① xv1≤xul−1,xv2>xul and ② xv2≤xul−1,xv1>xul holds. Without loss of generality, we assume that there exists a natural number l which satisfies 1≤l≤k such that xv1≤xul−1 and xv2>xul. Then, let T2=T∗−ul−1,ul−v1,v2+v2,ul−1+v1,ul, then it is easy to know T2∈TnΔ. By Lemma 3, we have that ρT2>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Therefore, Theorem 12 holds.Lemma 8.
Assume thatT∈TnΔ, x=x1,x2,…,xnT is the Perron vector of T, and C is the only circle in T, VC=u1,u2,…,ul, suppose that xu1,xu2,…,xul corresponds to the vertices u1,u2,…,ul, respectively. If l≥4, and xu1=xu2=⋯=xul, then there must exist T1∈TnΔ such that ρT1>ρT.Proof.
Assume that the proposition is not established, thenT is a maximal-adjacency-spectrum unicyclic graph in TnΔ. From Theorem 12, we can get xu1=xu2=⋯=xul=max1≤i≤nxi; again by Theorem 11, we get du1=du2=⋯=dul=Δ≥3; hence, for any natural number i which satisfies 1≤i≤l, and we all have NTui\VC≠∅. Besides, from Theorem 12, we get that for ∀v∈VT\VC, we all have xv<max1≤i≤nxi.
Without loss of generality, we assume thatu1,u2,…,ul have clockwise arrangement in C. Since NTu1\VC≠∅, choose v∈NTu1\VC, then we have xv<xu1. For l≥4, we can know u1,v,ul−1,andul are different from each other. From xu1=xu2=⋯=xul and xu1>xv, we know that xul−1=xu1>xv; again from xu1=xul, we can get xu1≥xul. Let T1=T−u1,v−ul,ul−1+u1,ul−1+ul,v, then it is easy to know T1∈TnΔ. From xul−1>xv and xu1≥xul, by Lemma 3, we have that ρT1>ρT holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Therefore, Lemma 8 holds.Lemma 9.
Assume thatT∈TnΔ, where T=VT,ET, C is the circle of T, VC=u1,u2,…,ul,l≥4, and for any natural number i which satisfies 1≤i≤l−1, we all have ui,ui+1∈ET,ul,u1∈ET. If there exists a natural number i0 which satisfies 1≤i0≤l such that dui0=2, then there exists T1∈TnΔ such that ρT1>ρT.Proof.
Assume that the proposition is not established, thenT is a maximal-adjacency-spectrum unicyclic graph in TnΔ.
Form Theorems11 and 12, we know that there exists a natural number j which satisfies 1≤j≤l such that xuj=max1≤i≤nxi and duj=Δ≥3. Now, we discuss the following two cases: Case 1. There are at least two vertices with the degree not less than 3 in VC.Denoteul+1=u1, for any natural number i which satisfies 1≤i≤l−1, we all have ui,ui+1∈ETandul,u1∈ET; hence, for any natural number i which satisfies 1≤i≤l, we all have ui,ui+1∈ET. And for there exists a natural number i0 which satisfies 1≤i0≤l such that dui0=2 and there are at least two vertices with the degree not less than 3 in VC, then we know that there exist two natural numbers t and m which satisfy m≥2 and 1≤t≤l−m+1 such that utut+1⋯ut+m is an internal path. Let T1=VT1,ET1, where VT1=VT\ut+1andET1=ET−ut,ut+1−ut+1,ut+2+ut,ut+2. It is easy to know T1∈Tn−1Δ, and by Lemma 4, we have that ρT1≥ρT holds.Suppose thatv1 is an arbitrary leaf node of T1. Let T2=T1+v1,ut+1, then it is easy to know T2∈TnΔ, and by Lemma 5, we have that ρT2>ρT1 holds, and thus, ρT2>ρT. Therefore, this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Case 2. There is only one vertex with degree not less than 3 inVC.In this case, it is easy to know that the only one vertex with degree not less than 3 must beuj. Suppose that VC=v1,v2,…,vl−1,uj, and v1,v2,…,vl−1,uj have clockwise arrangement in C, as shown in Figure 7. From Theorems 11 and 12, we get xuj>maxxv1,xv2,…,xvl−1. From l≥4, we know that vl−2,vl−1,andv1 are different. And for xuj>xvl−1, it is easy to prove that xv1>xvl−2 holds. Otherwise, xv1≤xvl−2, let T1=T−vl−1,vl−2−uj,v1+uj,vl−2+v1,vl−1, then it is easy to know T1∈TnΔ. From xuj>xvl−1 and xvl−2≥xv1, by Lemma 3, we have that ρT1>ρT holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ; hence, xv1>xvl−2. Let T2=T−vl−1,vl−2+vl−1,v1, then it is easy to know T2∈TnΔ, and by Lemma 1, we have that ρT2>ρT holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.
By consideration of the above two cases, we know that the hypothesis is not established. Therefore, Lemma9 holds.Figure 7
Vertex permutation graph of cycle C.Figure 8
Vertex permutation graph of cycle C with four vertices.Figure 9
Cycle C with four vertices.Lemma 10.
Assume thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, and x=x1,x2,…,xnT∗ is the Perron vector of T∗. Then, for any leaf node i and any vertex j which is not the leaf node in T∗, we all have that xi<xj holds, where xiandxj correspond to the vertices iandj, respectively.Proof.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, and x=x1,x2,…,xnT∗ is the Perron vector of T∗. Let j0 be any one of the vertices whose component is equal to max1≤l≤nxl in x, then from Theorem 11, we know dj0=Δ. Then, for any nonleaf node u which is not j0 in T∗, and for the arbitrary leaf node i in T∗, we all have that xu≥xi holds. Otherwise, there exists a vertex w which is not the vertex j0 and is not a leaf node i1 in T∗, which makes xw<xi1. For w is not the leaf node, hence dw≥2, thus there exists a vertex v in the set of NT∗w such that T∗−v,w+v,i1 still belong to TnΔ. Let T1=T∗−v,w+v,i1, then by Lemma 1, we have that ρT1>ρT holds, this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Again since xj0=max1≤l≤nxl, then xj0≥xu; thus, for any vertex j which is not the leaf node in T∗, and for any leaf node i in T∗, we all have that xj>xi holds.
For the properties of the nonfull internal vertices of the maximal-adjacency-spectrum unicyclic graph inTnΔ, we have the following theorems.Theorem 13.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, if the only circle in T∗ is C, and there exists a nonfull internal vertex in the set of VT∗\VC, then the number of all the nonfull internal vertices of T∗ is one.Proof.
Assume that the proposition is not established, then suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, the only circle in T∗ is C, there exists a nonfull internal vertex in the set of VT∗\VC, and the number of the nonfull internal vertex in T∗ is more than 1. Without loss of generality, assume that u1andu2 are two nonfull internal vertices in T∗, where u1∈VT∗\VC.
Letx=x1,x2,…,xnT be the Perron vector of T∗, xu1andxu2 correspond to the vertices u1andu2, respectively. Now according to whether u1 and u2 adjacent or not , we discuss the following two cases:Case 1.u1 and u2 adjacent.For case 1, we discuss the following two subcases again according to the value ofxu1 and xu2.Subcase 1.xu1≥xu2.Sinceu2 is the nonfull internal vertex in T∗, then NT∗u2\u1≠∅, choose w∈NT∗u2\u1. Let T1=T∗−w,u2+w,u1, then it is easy to know T1∈TnΔ. By Lemma 1, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Subcase 2.xu1<xu2.Sinceu1 is the nonfull internal vertex in T∗, then NT∗u1\u2≠∅, choose w∈NT∗u1\u2. Let T1=T∗−w,u1+w,u2, then it is easy to know T1∈TnΔ. By Lemma 1, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Case 2.u1 and u2 are not adjacent.Sinceu1andu2 are the nonfull internal vertices in T∗, we have that NT∗u1\NT∗u2≥1 and NT∗u2\NT∗u1≥1 hold at the same time. For case 2, we discuss the following two subcases again according to the value of xu1 and xu2.Subcase 1.xu1≤xu2.SinceNT∗u1\NT∗u2≥1 and T∗ is a unicyclic graph, we know that there exists w∈NT∗u1\NT∗u2 such that T∗−w,u1+w,u2 is still a simple connected graph. Denote T1=T∗−w,u1+w,u2, then it is easy to know T1∈TnΔ; by Lemma 1, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Subcase 2.xu1>xu2.ForNT∗u2\NT∗u1≥1 and T∗ is a unicyclic graph, we know that there exists w∈NT∗u2\NT∗u1 such that T∗−w,u2+w,u1 is still a simple connected graph. Denote T1=T∗−w,u2+w,u1, then it is easy to know T1∈TnΔ; by Lemma 1, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.
Hence, from the discussions of case 1 and case 2, we can know that the hypothesis is not established; therefore, Theorem13 holds.Theorem 14.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, let C be the only circle in T∗, and VC=3, if there is no nonfull internal vertex in the set of VT∗\VC, then both the following propositions are established:(1)
The number of the nonfull internal vertex inVC is at most 2.(2)
When the number of nonfull internal vertex inVC is 2, then there is at least one vertex with degree 2 in the two nonfull internal vertices in VC.Proof.
Letx=x1,x2,…,xn be the Perron vector of T∗.(1)
Suppose that a vertexv in T∗ satisfies xv=max1≤i≤nxi, then from Theorem 12, we get v∈VC, and from Theorem 11, we know dv=Δ. Hence, the number of the nonfull internal vertices in VC is at most 2, and then, (1) of Theorem 14 holds.(2)
When the number of nonfull internal vertices inVC is 2, without loss of generality, we assume that u1andu2 are the nonfull internal vertices in VC. Suppose that xu1andxu2 correspond to the vertices u1andu2, respectively. Assume that du1≠2 and du2≠2, then we must have that du1≥3 and du2≥3 hold. Hence, NT∗u1\VC≠∅ and NT∗u2\VC≠∅. Choose s1∈NT∗u1\VC,s2∈NT∗u2\VC. Without loss of generality, we assume that xu1≥xu2, and let T1=T∗−u2,s2+s2,u1, then it is easy to know T1∈TnΔ. By Lemma 1, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Hence, the hypothesis is not established. Therefore, either du1=2 or du2=2, then (2) of Theorem 14 holds.
By consideration, Theorem14 holds.


## 3.2. The Structure of the Maximal-Adjacency-Spectrum Unicyclic Graphs inTnΔ

For the length of the circle of the maximal-adjacency-spectrum unicyclic graphs inTnΔ, we have the following theorems.Theorem 15.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. If the only circle in T∗ is C, there is no nonfull internal vertex in the set of VT∗\VC, and the number of the nonfull internal vertex in the set of VC is equal to or greater than 2, then the length of the circle is 3, that is, VC=3.Proof.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, the only circle in T∗ is C, there is no nonfull internal vertex in the set of VT∗\VC, and the number of the nonfull internal vertices in the set of VC is not less than 2. Denote VC=m, and assume that Theorem 15 is not established, then m≥4. Suppose that u1∈VC,u2∈VC, and u1andu2 are two different nonfull internal vertices in T∗. Let x be the Perron vector of T∗, and suppose that xu1andxu2 correspond to the vertices u1andu2. Now according to the value of m, we discuss the following two cases:Case 1.m≥5.In case 1, there exists a pathu1v1v2⋯vku2 which satisfies k≥2 in C. Without loss of generality, we assume that xu1≥xu2. Let T1=T∗−vk,u2+vk,u1, then it is easy to know T1∈TnΔ. By Lemma 1, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Case 2.m=4.Now according to whether the verticesu1 and u2 adjacent or not, we discuss the following two subcases again:Subcase 1. Ifm=4 and u1andu2 are adjacent.At this time, it is easy to know that there is a pathu1v1v2u2 in C. Without loss of generality, we assume that xu1≥xu2. Let T1=T∗−v2,u2+v2,u1, then it is easy to know T1∈TnΔ; By Lemma 1, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Subcase 2. Ifm=4 and u1andu2 are not adjacent.Suppose thatVC=u1,u2,v1,w1. First, we must have that dv1=dw1=Δ holds; otherwise, there must exist two adjacent nonfull internal vertices in C. From the discussion of the subcase 1 in case 2, we know that it will imply a contradiction. Without loss of generality, we assume that the position relationship of the vertices v1,w1,u1,andu2 in C is shown in Figure 8.Second, we must havedu1≥3 and du2≥3. Otherwise, there are at least one of the two inequalities, du1<3 and du2<3, holds. Without loss of generality, assume that du1<3. For u1∈VC, du1=2. And since dv1=dw1=Δ≥3, we have that v1u1w1 is an internal path, let T1=VT1,ET1, where VT1=VT∗\u1,ET1=ET∗−v1,u1−u1,w1+v1,w1, then it is easy to know T1∈Tn−1Δ. By Lemma 4, we have that ρT1≥ρT∗ holds. Let w1 be an arbitrary leaf node in T1, and let T2=T1+u1,w1, then it is easy to know T2∈TnΔ. By Lemma 5, we have that ρT2>ρT1 holds; hence, ρT2>ρT∗, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Fromdu1≥3 and du2≥3, we know that NT∗u1\VC≠∅ and NT∗u2\VC≠∅ hold. Choose s1∈NT∗u1\VCands2∈NT∗u2\VC. Without loss of generality, assume that xu1≥xu2. Let T3=T∗−s2,u2+s2,u1, then it is easy to know T3∈TnΔ. By Lemma 1, we have that ρT3>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.
Hence, from the discussion of case 1 and case 2, we know thatm≥4 does not hold. Therefore, Theorem 15 holds.Theorem 16.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, if C is the only circle in T∗, then VC=3.Proof.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ and C is the only circle in T∗. Denote VC=l; assume that Theorem 16 does not hold, then we have l≥4. From Theorems 13 and 15, we can get that there is at most one nonfull internal vertex in T∗. Suppose that VC=u1,u2,…,ul, and x=x1,x2,…,xnT is the Perron vector of T∗. By Theorem 12, we can get max1≤i≤lxui=max1≤i≤nxi. Then, from l≥4, T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, and from Lemma 8, we can know max1≤i≤lxui>min1≤i≤lxui. Now, according to the value of l, we discuss the following two cases:Case 1.l=4.Suppose thatVC=u1,u2,u3,u4, from Theorem 12, we have that max1≤i≤4xui=max1≤j≤nxj holds. Without loss of generality, assume that xu1=max1≤i≤4xui, then we have xu1=max1≤j≤nxj; again from Theorem 11, we can get du1=ΔΔ≥3. Without loss of generality, we assume that u1,u2,u3,andu4 have anticlockwise arrangement in C, and the position of the relationship of these vertices is shown in Figure 9.In the situation of case 1, we could prove that the following six propositions hold.Proposition 1.
For any vertexui which satisfies 1≤i≤4 in VC, we all have that NT∗ui\VC≠∅ holds.
For there is at most one nonfull internal vertex inT∗, there is at most one of du2,du3,anddu4 unequal to ΔΔ≥3. Besides, mindu2,du3,du4≥3; otherwise, mindu2,du3,du4=2. Since there is at most one nonfull internal vertex in T∗, hence there must exist an internal path q1q2q3 in C. Let T1=VT1,ET1, where VT1=VT∗\q2,ET1=ET∗−q1,q2−q2,q3+q1,q3. Then, it is easy to know T1∈Tn−1Δ, and by Lemma 4, we have that ρT1≥ρT∗ holds. Let w1 be an arbitrary leaf node in T1, and let T2=T1+q2,w1, then it is easy to know T2∈TnΔ. By Lemma 5, we have that ρT2>ρT1 holds. Hence, ρT2>ρT∗, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Then, we have mindu2,du3,du4≥3, and min1≤i≤4dui≥3. Therefore, for any vertex ui which satisfies 1≤i≤4 in the set of VC, we all have that NT∗ui\VC≠∅ holds.Proposition 2.
xu3=minxu2,xu3,xu4.
Assume thatxu3=minxu2,xu3,xu4 is not established, and we have xu3>minxu2,xu3,xu4. Without loss of generality, assume that minxu2,xu3,xu4=xu2, then we have xu3>xu2. Let T1=T∗−u1,u2−u3,u4+u1,u3+u2,u4, then it is easy to know T1∈TnΔ. From xu1≥xu4 and xu3>xu2, by Lemma 3, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ; hence, the hypothesis is not established. Therefore, xu3=minxu2,xu3,xu4.Proposition 3.
For∀v∈NT∗u2\VC, we all have that xu4=xv holds.
And for∀w∈NT∗v4\VC, we all have that xw=xu2 holds. From Proposition 1, we know NT∗u2\VC≠∅. Assume that, for ∀v∈NT∗u2\VC, we all have that the proposition xu4=xv is not established, then there must exists a vertex v2∈NT∗u2\VC such that xu4≠xv2.Proposition 4.
du2=Δ and du4=Δ.
Ifdu2=Δ is not established, then du2<Δ. From Proposition 1, we know NT∗u3\VC≠∅. Choose v3∈NT∗u3\VC, and let T1=T∗−v3,u3+v3,u2, then it is easy to know T1∈TnΔ. From Proposition 2, we know xu3≤xu2, and by Lemma 1, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Hence, the hypothesis is not established, that is, du2=Δ. The same reason, we can prove that du4=Δ holds.Proposition 5.
xu4=xu2.
From Proposition1, we know NT∗u2\VC≠∅ and NT∗u4\VC≠∅. For Ax=ρT∗x, where A is the adjacency matrix of T∗, denote ρ=ρT∗, then ρxu4=xu1+xu3+∑p∈NT∗u4\VCxp,ρxu2=xu1+xu3+∑q∈NT∗u2\VCxq. From Propositions 3 and 4, we can know ∑p∈NT∗u4\VCxp=Δ−2xu2 and ∑q∈NT∗u2\VCxq=Δ−2xu4; thus, we have ρxu4=xu1+xu3+Δ−2xu2 and ρxu2=xu1+xu3+Δ−2xu4. Hence, ρ+Δ−2xu4−xu2=0. Therefore, xu4=xu2.Proposition 6.
xu1=xu2 and xu1=xu4.
Assume thatxu1≠xu2, then from xu1=max1≤i≤4xui, we know xu1>xu2. From Proposition 1, we can get NT∗u2\VC≠∅. Choose v2∈NT∗u2\VC, let T1=T∗−u1,u4−u2,v2+v2,u1+u2,u4, and then it is easy to know T1∈TnΔ. From Proposition 3, we know xv2=xu4; hence, xu4≤xv2. And for xu1>xu2, then by Lemma 3, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ; hence, we have that xu1=xu2 holds. And from Proposition 5, we get xu4=xu2; therefore, xu1=xu4.
From Proposition2, we know xu3=minxu2,xu3,xu4; from Proposition 6, we have xu1=xu2=xu4, and by Lemma 8, we know max1≤i≤4xui>min1≤i≤4xui; hence, xu3<xu4. Let T2=T∗−u1,u4−u2,u3+u3,u1+u2,u4, then it is easy to know T2∈TnΔ. From xu3<xu4 and xu1≤xu2, by Lemma 3, we have that ρT2>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.
Therefore, in conclusion, case 1 implies a contradiction.
Case 2.l≥5.
In this case, from Lemma8, we have that min1≤i≤lxui<max1≤i≤lxui. Let s be a vertex in C such that xs=min1≤i≤lxui. From Theorem 12, we can get that there exists a natural number i0 which satisfies 1≤i0≤l such that xui0=max1≤i≤nxi. Assume that k is the number of the vertices whose components are equal to max1≤i≤nxi in C. From min1≤i≤lxui<max1≤i≤lxui, we have l−k≥1. Suppose that r1,r2,…,rk are all the vertices whose components are equal to max1≤i≤nxi in C, and r1,r2,…,rk are clockwise arrangement in C. Then, by Lemma 6, we can suppose that the vertices which follow the clockwise direction in C are s,…,r1,r2,…,rk,…,s in sequence.
First, we can prove thatk≥2 holds.
Assume thatk≥2 is not established, then k=1. Then now, we can suppose that the vertices which follow the clockwise direction in C are w2,…,v2,v1,r1,w1,w2 in sequence, where v2,v1,r1,w1,andw2 are five different vertices in C, and let the circle C be shown as Figure 10. From the definitions of r1,r2,…,rk and from k=1, we can know that, for any natural number i which satisfies 1≤i≤2, we all have that xvi<xr1 and xwi<xr1 hold.
From Lemma9, we can get NT∗w1\VC≠∅. Then for ∀t∈NT∗w1\VC, we all have that xt<xv1 holds. Otherwise, there exists t1∈NT∗w1\VC such that xt1≥xv1. Let T1=T∗−w1,t1−r1,v1+r1,t1+w1,v1, then it is easy to know T1∈TnΔ. From xt1≥xv1 and xw1<xr1, by Lemma 3, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.
Besides, we also can provexv2<xw1. Otherwise, xv2≥xw1; let T2=T∗−v1,v2−r1,w1+r1,v2+w1,v1, then it is easy to know T2∈TnΔ. From xv2≥xw1 and xv1<xr1, by Lemma 3, we have that ρT2>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.
Chooset2∈NT∗w1\VC; let T3=T∗−v1,v2−t2,w1+t2,v2+w1,v1, then it is easy to know T3∈TnΔ. From the above conclusion, we have xt2<xv1. For xv2<xw1, by Lemma 3, we have that ρT3>ρT∗ holds. This implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Hence, the hypothesis is not established; therefore, k≥2 holds.
Second, we can prove thatl−k≥2 holds.
Assume thatl−k≥2 is not established, then l−k=1; hence, we can suppose that the vertices which follow the clockwise direction in C are s,r1,r2,…,rk in sequence. From l≥5, we know that k≥4 holds; thus s,r1,rk−1,andrk are four different vertices. Let T4=T∗−r1,s−rk−1,rk+r1,rk+s,rk−1, it is easy to know T4∈TnΔ. From the definitions of r1,r2,…,rk and s, we know xs<xrk. Since xr1≥xrk−1, by Lemma 3, we have that ρT4>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Therefore, l−k=1 is not established, then we have l−k≥2.
Denotem=l−k, from l−k≥2, and we have that m≥2 holds. Then, we can suppose that the vertices which follow the clockwise direction in C are vm,…,v1,r1,…,rk in sequence. From m≥2 and k≥2, we know that vm,v1,r1,andrk are four different vertices in C, and the relationship of the vertices of C is shown in Figure 11.
For the relationship betweenxv1 and xvm, we must have that xv1=xvm holds. Otherwise, there must exist one of the two equations, xv1<xvm and xv1>xvm, holds. Let T5=T∗−r1,v1−rk,vm+r1,vm+v1,rk, then it is easy to know T5∈TnΔ. If xv1<xvm, for xr1≥xrk, by Lemma 3, we have that ρT5>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. If xv1>xvm, for xr1≤xrk, by Lemma 3, we have that ρT5>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Hence, xv1=xvm. Then, we have that xvm≥xv1 holds.
By Lemma9, we know dvm≥3; hence, NT∗vm\VC≠∅. Choose u∈NT∗vm\VC; then from Theorem 11, we get xu<xr1. Let T6=T∗−r1,v1−u,vm+r1,vm+v1,u, it is easy to know T6∈TnΔ. From xvm≥xv1 and xu<xr1, by Lemma 3, we know that ρT6>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.
Hence, in conclusion, case 2 implies a contradiction.By consideration of the discussion of case 1 and case 2, we know that whenl=4 or l≥5, a contradiction is implied. Hence, l≥4 is not established; therefore, l=3 and VC=3. Then, we have that Theorem 16 holds.Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, then the leaf nodes of T∗ have the properties stated in the following theorem.Figure 10
Vertex permutation graphs of cycle C with no less than 5 vertices.Figure 11
The relationship of the vertices of C.Theorem 17.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, and let r be the vertex that corresponds to a maximum component in the component of the Perron vector of T∗. T∗ is the rooted unicyclic graph with root node r, let C be the only circle in T∗, and VC=r,g1,g2. Let du,v be the shortest distance between vertex u and vertex v in T∗, denote that W1 = {ii is the leaf node of T∗, and the shortest path from i to r neither pass g1 nor pass g2}, W2 = {ii is the leaf node of T∗, and the shortest path from i to r either pass g1 or pass g2}, then the following propositions are established:(1)
IfW2=∅, then maxi∈W1di,r=1.(2)
Ifdg1=2, then for the arbitrary leaf node i in T∗, we all have 1−di,r≤1.Ifdg2=2, then for the arbitrary leaf node i in T∗, we all have 1−di,r≤1.(3)
IfW2≠∅, then for the arbitrary leaves i,j in T∗, we all have di,r−dj,r≤1.(4)
IfW2≠∅, then mini∈W2di,r≥maxj∈W1dj,r.(5)
IfW2≠∅, and there exists a vertex with degree 2 in VC, then T∗ is the rooted unicyclic graph with 3 levels, and for ∀j∈W1, we all have dj,r=1.Proof.
Assume thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, and suppose that r is the vertex that corresponds to a maximum component in the component of the Perron vector of T∗, and T∗ is a rooted unicyclic graph with root node r. Suppose that C is the only circle in T∗, and VC=r,g1,g2, let x=x1,x2,…,xnT be the Perron vector of T∗.(1)
Assume thatmaxi∈W1di,r=1 is not established, then there exists a vertex i∈W1 such that di,r≥2. Suppose that the shortest path from i to r is u1u2⋯ukr, where u1=i,k≥2. By Lemma 1, it is easy to prove that xg1<xu2 holds. And from Lemma 10, we get xg2>xu1. Let T1=T∗−g1,g2−u1,u2+u2,g2+g1,u1, it is easy to know T1∈TnΔ. From xg1<xu2 and xg2>xu1, by Lemma 3, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Hence, maxi∈W1di,r=1.Therefore, (1) of Theorem17 holds.(2)
Assume thatdg1=2, and there exists a leaf node i in T∗ such that 1−di,r>1. Without loss of generality, we assume that the shortest path from r to i is rv1v2⋯vk, where vk=i. From 1−di,r>1, we know di,r≥3, then we have k≥3. Let T1=T∗−vk−1,vk+g1,vk, then it is easy to know T1∈TnΔ. If xg1≥xvk−1, then by Lemma 1, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ; hence, xg1<xvk−1. Let T2=T∗−vk−1,vk−r,g1+vk−1,r+g1,vk, it is easy to know T2∈TnΔ. Since xg1<xvk−1, and from Lemma 10, we know that xvk<xr holds. By Lemma 3, we have that ρT2>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Hence, when dg1=2, for any leaf node i in T∗, we all have that 1−di,r≤1 holds. Similarly, when dg2=2, for any leaf node i in T∗, we all have that 1−di,r≤1 holds.Therefore, (2) of theorem holds.(3)
Assume that there exist two leaf nodesi,j in T∗ such that di,r−dj,r>1. Suppose that di,r=k,dj,r=l, then we have k−l>1. Without loss of generality, we assume that k−l>1, then we have that k≥l+2 and l≥1 hold. Let P1 be the shortest path from i to r and P2 be the shortest path from j to r. According to whether there is a public edge between P1 and P2 or not, we discuss the following two cases:Case 1. There is no public edge betweenP1 and P2.We denote the pathP1 by rvkvk−1⋯v2v1 and the path P2 by rul⋯u2u1, where v1=iandu1=j; P1andP2 are shown in Figure 12. Besides, we denote ul+1=r; by the definition of r, we know xul+1≥xvk.Foru1 is the leaf node in T∗ and v2 is the nonleaf node in T∗, then by Lemma 10, we have xu1<xv2.Fromxu1<xv2,xul+1≥xvk and k−1≥l+1, we know that there exists a natural number s that satisfies 1≤s≤l, which make xus<xvs+1 and xus+1≥xvs+2. Let T1=T∗−us,us+1−vs+1,vs+2+vs+1,us+1+us,vs+2, then it is easy to know T1∈TnΔ. From xus<xvs+1 and xus+1≥xvs+2, by Lemma 3, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Case 2. There is a public edge betweenP1 and P2.From thatW2≠∅,Δ≥3, and there exists public edge between P1 and P2, we know that there must exist a leaf node w neither equal to i nor equal to j, which makes the shortest path from w to r have no public edge with P1,P2. Denote the shortest path from the leaf node w to r by P3, and then the length of P3 is l+1. Otherwise, the difference in length between P3 and at least one of P1andP2 is greater than 1. From the discussion of case 1, we know that this will lead to a contradiction. Besides, there will be k=2+l. Otherwise, k>2+l, it will imply that the difference in lengthen between P3 and P1 is more than 1, and P3 has no public edge with P1. From the discussion of case 1, we know that this will lead to a contradiction.Suppose thatP1,P2,andP3 are shown in Figure 13, where P1 is u0u1u2⋯ut+1⋯r and P2 is v2v3⋯vt+1⋯r, where u0=i,v2=j, and there exists t≥2 such that, for ∀j≥t+1, we all have uj=vj. Let P3 be w1w2w3⋯wt+1⋯r, where w1 is denoted by w, and denote uk=r.Now, we consider the pathsP1 and P3.Forw1 is the leaf node in T∗ and u1 is the nonleaf node in T∗, then by Lemma 10, we get xw1<xu1. If there exists a natural number s that satisfies 1≤s≤t, which make that both xws<xus and xws+1≥xus+1 hold. Let T1=T∗−ws,ws+1−us,us+1+ws+1,us+us+1,ws, then it is easy to know T1∈TnΔ. From xws<xus and xws+1≥xus+1, by Lemma 3, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Hence, for any natural number s which satisfies 1≤s≤t, xws<xus, and xws+1≥xus+1 cannot hold meanwhile. And for xw1<xu1, then we have that, for any natural number s which satisfies 1≤s≤t+1, we all have xws<xus.Now we consider the pathsP2 and P3.Forv2 is the leaf node in T∗ and w2 is the nonleaf node in T∗, by Lemma 10, we get xv2<xw2. Since xvt+1=xut+1>xwt+1, then there exists a natural number s that satisfies 2≤s≤t, which make that both xvs<xws and xvs+1≥xws+1 hold. Let T2=T∗−vs,vs+1−ws,ws+1+ws+1,vs+vs+1,ws, then it is easy to know T2∈TnΔ. From xvs<xws and xvs+1≥xws+1, by Lemma 3, we know that ρT2>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.From the discussion of case 1 and case 2, we know that the hypothesis is not established. Therefore, (3) of Theorem17 holds.(4)
Assume that the proposition is not established, then there exist verticesi∈W2 and j∈W1 such that di,r<dj,r. From i∈W2, we know di,r≥2. Without loss of generality, we assume that the shortest path from r to i is rv1v2⋯vs and the shortest path from r to j is rw1w2⋯wk, where i=vsandj=wk. Then, we have that k>s and s≥2 hold. From i∈W2, we know that the shortest path from i to r must pass one of g1 and g2. Without loss of generality, we assume that the shortest path from i to r pass g1, then v1=g1. By (3) of Theorem 17, we know k=s+1.Sincevs is the leaf node in T∗ and wk−1 is the nonleaf node in T∗, then by Lemma 10, we get xwk−1>xvs. Let T1=T∗−vs−1,vs−wk−1,wk−2+wk−1,vs−1+vs,wk−2, it is easy to know T1∈TnΔ. From xwk−1>xvs, if xwk−2≤xvs−1, then by Lemma 3, we have that ρT1>ρT∗ holds. This implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ; hence, xwk−2>xvs−1. By mathematical induction, we get xwk−s>xvs−s−1, then we have that xw1>xv1 holds.We also can prove thatxw2>xg2 holds. Otherwise, xw2≤xg2. For xw1>xv1, let T2=T∗−w1,w2−v1,g2+w1,g2+v1,w2, it is easy to know T2∈TnΔ. From xw2≤xg2 and xw1>xv1, by Lemma 3, we have that ρT2>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Let T3=T∗−w1,w2+w1,g2+r,w2, it is easy to know T3∈TnΔ. From xr≥xw1 and xw2>xg2, by Lemma 3, we have that ρT3>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Hence, the hypothesis is not established; therefore, (4) of Theorem17 holds.(5)
Assume thatT∗ is not a rooted unicyclic graph with levels 3, and since W2≠∅, then T∗ is a rooted unicyclic graph with levels not less than 4. For there exists a vertex with degree 2 in VC, without loss of generality, we assume that dg2=2. From W2≠∅, the level of T∗ is not less than 4 and (4) of Theorem 17, and we know that there exists a vertex i∈W2 such that di,r≥3. Suppose that the shortest path from i to r is v1v2⋯vkr, where v1=i. Then, from di,r≥3, we know that k≥3 holds, and from dg2=2, we know that vk=g1 holds. Let T1=T∗−v1,v2−r,g2+r,v2+g2,v1, from vk=g1 and k≥3, we know T1∈TnΔ. And by Lemma 1, it is easy to prove xv2>xg2. For xv1≤xr, then by Lemma 3, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ; hence, the hypothesis is not established. Therefore, T∗ is a rooted unicyclic graph with levels 3.Next, we prove that, for∀j∈W1, we all have dj,r=1. Otherwise, assume that there exists a vertex j0∈W1 such that dj0,r≥2. And for T∗ is a rooted unicyclic graph with levels 3, then we have that dj0,r=2 holds. Suppose that the shortest path from j0 to r is w1w2r, where w1=j0, w2 is neither equal to g1 nor equal to g2. From that there exists a vertex with degree 2 in VC, without loss of generality, assume that dg2=2. Then, from Lemma 1, it is easy to prove that xg2≤xw2 holds. By Lemma 10, we can get xg1>xw1. Let T2=T∗−g1,g2−w1,w2+g1,w2+g2,w1, then it is easy to know T2∈TnΔ. From xg2≤xw2 and xg1>xw1, by Lemma 3, we have that ρT2>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Hence, the hypothesis is not established. Therefore, for ∀j∈W1, we all have that dj,r=1 holds.In conclusion, (5) of Theorem17 holds.
For the relationship between the maximal-adjacency-spectrum unicyclic graphs inTnΔ and the almost full-degree unicyclic graphs, we have the following theorem.Figure 12
A graph with no common edge between two paths.Figure 13
A graph with common edge(s) between two paths.Theorem 18.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, x=x1,x2,…,xnT is the Perron vector of T∗, and r is the vertex that corresponds to a maximum component in the component of the Perron vector of T∗. Let T∗ be the rooted unicyclic graph with root node r, then T∗ is an almost full-degree unicyclic graph with root node r.Proof.
Suppose that the only circle inT∗ is C. From Theorem 16, we get VC=3. By Theorem 12, we know r∈VC, then let VC=r,g1,g2. Denote W1 = {ii is the leaf node of T∗, and the shortest path from i to r neither pass g1 nor pass g2}, W2 = {ii is the leaf node of T∗, and the shortest path from i to r either pass g1 or pass g2}.
Now according toT∗, we discuss the following three cases:Case 1. There exist nonfull internal vertices inT∗ and exist nonfull internal vertices in C.For case 1, according to whether there exist the vertices with degree 2 inC or not, we discuss the following two subcases:Subcase 1. There exist nonfull internal vertices inC and exist the vertices with degree 2 in C.For subcase 1, according to the number of the vertices with degree 2 inC, we continue to discuss the following two subcases:Subcase 1.1. There are at least two vertices with degree 2 inC.In this case, it is easy to knowW2=∅; by (1) of Theorem 17, we know maxi∈W1di,r=1; thus, T∗≅Tn,2Δ, where Tn,2Δ is shown in Figure 2. Hence, T∗ is an almost full-degree unicyclic graph with root node r.Subcase 1.2. There is only one vertex with degree 2 inC.In this case, it is easy to knowW2≠∅. For there is only one vertex with degree 2 in C, then by (5) of Theorem 17, we know that T∗ is a rooted unicyclic graph with levels 3. And for ∀j∈W1, we all have that dj,r=1 holds; hence, it is easy to know that T∗ is an almost full-degree unicyclic graph with root node r.Subcase 2. There exist nonfull internal vertices inC, and the degree of all the vertices in C is not equal to 2.In this case, it is easy to know that the degree of all the vertices inC are more than 2. From that, there exist nonfull internal vertices in C, and from Theorem 14, we know that there is only one nonfull internal vertex in C. Without loss of generality, assume that g2 is the nonfull internal vertex in C, then we have that dg1=Δ and 3≤dg2<Δ holds. And by Theorem 13, we know that there is only one nonfull internal vertex in T∗. Then, it is easy to know that W1≠∅,W2≠∅ and mini∈W2di,andr≥2 hold.Supposemaxi∈W1di,r=m, then m=1. Assume that m=1 is not established, then we have m≥2. Now choose a vertex u1 which satisfies du1,r=m and u1∈W1 in T∗. Choose u2∈NT∗u1, then xg2≤xu2. Otherwise, xg2>xu2, let T1=T∗−u1,u2+g2,u1, from m≥2 and g2 is the nonfull internal vertex in T∗, we know T1∈TnΔ. And by Lemma 1, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Let T2=T∗−g1,g2−u1,u2+g2,u1+u2,g1, it is easy to know T2∈TnΔ. From xg2≤xu2, and by Lemma 10, we get xg1>xu1; then by Lemma 3, we have that ρT2>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Hence, the hypothesis is not established, and then we have m=1. From mini∈W2di,r≥2, we get maxi∈W2di,r≥2. And for maxi∈W1di,r=1, by (3) of Theorem 17, we have that maxi∈W2di,r=2 holds. Thus, maxi∈W2di,r=mini∈W2di,r=2, from maxi∈W1di,r=1, and from that there is only one nonfull internal vertex in T∗, we know that T∗ is an almost full-degree unicyclic graph with root node r.By consideration of the discussion of subcase 1 and subcase 2 in case 1, we know that if there exist nonfull internal vertices inT∗, and there exist nonfull internal vertices in C, then T∗ is an almost full-degree unicyclic graph with root node r.Case 2. There exist nonfull internal vertices inT∗, and there is no nonfull internal vertex in C.Since there exist nonfull internal vertices inT∗, and there is no nonfull internal vertex in T∗, then there exist nonfull internal vertices out of the circle of T∗. By Theorem 13, we know that there only one nonfull internal vertex in T∗.We denoter by u0, let w be the only nonfull internal vertex in T∗. Denote that dr,w=l; obviously, l≥1. Choose a path P1 in which u0 is the starting point and a leaf node of T∗ is the terminal point, and P1 passes w. Suppose that P1 is u0u1⋯ul⋯uk, where k>l. From the definition of P1, we know ul=w, then we have that ul is the only nonfull internal vertex in T∗.Assume thatT∗ is not an almost full-degree unicyclic graph with root node r. If k=l+1, then from that there is only one nonfull internal vertex in T∗, and from Theorem 17, we have that, in T∗, there exists a path P2 in which u0 is the starting point and a leaf node of T∗ is the terminal point. Besides, P2 has no public edge with P1, and the length of P2 is l+2. Suppose that P2 is u0v1⋯vl+1vl+2, where vl+2 is the leaf node, then the relationship between P1 and P2 is shown in Figure 14. If k=l+2, then from that, there is only one nonfull internal vertex in T∗ and from Theorem 17, we know that, in T∗, there exists a path P3 in which u0 is the starting point and a leaf node of T∗ is the terminal point. Besides, P3 has no public edge with P1, and from Theorem 17, we know that the length of P3 is not less than l+1. Hence, suppose that P3 is u0v1⋯vl+1⋯, and the relationship between P1 and P3 is shown in Figure 15. If k≥l+3, from that there is only one nonfull internal vertex in T∗, and from Theorem 17, we know that, in T∗, there exists a path P4 in which u0 is the starting point and a leaf node of T∗ is the terminal point. Besides, P4 has no public edge with P1, and from Theorem 17, we know that the length of P4 is not less than l+2. Hence, suppose that P4 is u0v1⋯vl+2⋯, and the relationship between P1 and P4 is shown in Figure 16.Now according to the relationship betweenk and l, we discuss the following two subcases: let k=l+1 or k≥l+3 be the subcase 1, and let k=l+2 be the subcase 2.Subcase 1. Ifxul≥xvl+1, let T1=T∗−vl+2,vl+1+vl+2,ul, then it is easy to know T1∈TnΔ. By Lemma 1, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Ifxul<xvl+1, and for xu0=xr≥xv1, we know that there exists a natural number k that satisfies 2≤k≤l+1, which make that xuk−1<xvk and xuk−2≥xvk−1 hold. Let T2=T∗−vk−1,vk−uk−2,uk−1+vk,uk−2+uk−1,vk−1, it is easy to know T2∈TnΔ. From xuk−1<xvk and xuk−2≥xvk−1, and by Lemma 3, we have that ρT2>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Hence, subcase 1 of case 2 implies a contradiction.Subcase 2. In subcase 2, according to whethervl+1 is the leaf node or not, we discuss the following two subcases:Subcase 2.1.vl+1 is the leaf node.In this case, by Lemma10, we have xvl+1<xul+1.Ifxvl≥xul, and for xvl+1<xul+1, let T1=T∗−vl+1,vl−ul+1,ul+vl,ul+1+vl+1,ul, it is easy to know T1∈TnΔ. By Lemma 3, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ; hence, xvl<xul. Let T2=T∗−vl,vl+1+vl+1,ul, it is easy to know T2∈TnΔ, and by Lemma 1, we have that ρT2>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Subcase 2.2.vl+1 is not the leaf node.In this case, if there exists a natural numberi which satisfies 1≤i≤l+1 such that xvi≤xul, then let T3=T∗−vi,vi+1+vi+1,ul, it is easy to know T3∈TnΔ. By Lemma 1, we have that ρT3>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Hence, for arbitrary vertex vi which satisfies 1≤i≤l+1, we all have xvi>xul. Specially, we have xvl+1>xul.Fromxu0≥xv1 and xvl+1>xul, we know that there exists a natural number k that satisfies 2≤k≤l+1, which makes both xvk>xuk−1 and xvk−1≤xuk−2 hold. Let T4=T∗−vk,vk−1−uk−1,uk−2+vk,uk−2+uk−1,vk−1, it is easy to know T4∈TnΔ. From xvk>xuk−1 and xvk−1≤xuk−2, by Lemma 3, we have that ρT4>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Hence, in subcase 2, no matter whethervl+1 is leaf node or not, it will imply a contradiction.By consideration of the subcase 1 and subcase 2 in case 2, we know that the hypothesis is not established. Then, we know that when there exists nonfull internal vertices inT∗, and there exists no nonfull internal vertices in C, T∗ is an almost full-degree unicyclic graph with root node r.Case 3. There is no nonfull internal vertex inT∗, then there are only full-degree vertices and leaf nodes in T∗. From Theorem 17, we know that T∗ is an almost full-degree unicyclic graph with root node r.In conclusion, for each of the cases,T∗ is still an almost full-degree unicyclic graph with root node r, then we have that Theorem 18 holds.
Assume thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, T∗≇Tn,2Δ and there is only one nonfull internal vertex in T∗, then from the position of the nonfull internal vertex in T∗, we have the following conclusion, as in the following theorem.Figure 14
Vertex graphs of two paths underk = l + 1.Figure 15
Vertex graphs of two paths underk = l + 2.Figure 16
Vertex graphs of two paths underk > l + 2.Theorem 19.
Suppose thatT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, x=x1,x2,…,xnT is the Perron vector of T∗, r is the vertex that corresponds to a maximum component in the component of the Perron vector of T∗, and T∗ is the rooted unicyclic graph with root node r, T∗ has only one nonfull internal vertex u. Suppose that C is the only one circle in T∗, and VC=r,g1,g2, denote that W1 = {ii is the leaf node of T∗, and the shortest path from i to r neither pass g1 nor pass g2}, W2 = {ii is the leaf node of T∗, and the shortest path from i to r either pass g1 or pass g2}. Assume that T∗≇Tn,2Δ, that is W2≠∅, then the following propositions are established:(1)
If the distances from all leaves ofT∗ to r are all equal, then there exists a leaf node i∈W1 which makes i,u is a pendant edge.(2)
If there are two leavesi,j in T∗ which make di,r≠dj,r and maxi∈W1di,r=mini∈W1di,r, then either there exists a leaf node j1∈W2 which makes u,j1 is a pendant edge or u∈VC and du=2.(3)
Ifmaxi∈W1di,r≠mini∈W1di,r, then there exists a leaf node j1∈W1 which makes u,j1 is a pendant edge.Proof.
From Theorem18, we know that T∗ is an almost full-degree unicyclic graph with root node r; suppose that T∗ is a rooted unicyclic graph with levels k, then u is in the k−1 level.(1)
FromW2≠∅, we know maxi∈W2di,r≥2; thus, T∗ is a rooted unicyclic graph with the levels not less than 3. First, we have that dg1≥3 and dg2≥3 holds. Otherwise, there is at least one of the two equations, dg1=2 and dg2=2, holds. From W2≠∅, we know that there is at most one of the two equations which are dg1=2 and dg2=2 holds. Hence, there is only one of the two equations which are dg1=2 and dg2=2 holds. By (5) of Theorem 17, we get that, for ∀j∈W1, we all have that dj,r=1 holds; hence, maxi∈W1di,r=1. Then, we can get maxi∈W2di,r>maxi∈W1di,r, and this implies a contradiction with the distances from all leaves of T∗ to r are all equal; hence, dg1≥3 and dg2≥3.Assume that (1) of Theorem19 is not established, then there exists u1∈W2 such that u1,u is a pendant edge of T∗. Let u1u2⋯umr be the shortest path from u1 to r, where u2=u, um=g1, or um=g2. Without loss of generality, we assume that um=g1, from u1∈W2, we know m≥2.For the range of the value ofm, we must have that m≥3 holds. Otherwise, m=2, since the distances from all the leaf nodes in T∗ to r are equal, then for ∀j1∈W1, we all have dj1,r=2. Choose j∈W1; let v1v2r be the shortest path from j to r, where v1=j,v2≠g1 and v2≠g2. By Lemma 10, we have that xg2>xv1 holds. From um=g1 and m=2, we get g1=u2, and by u2=u, we have um=u=g1. In addition, for the relationship of xg1 and xv2, we must have xg1≤xv2. Otherwise, xg1>xv2, let T1=T∗−v1,v2+v1,g1, and it is easy to know T1∈TnΔ. By Lemma 1, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Let T2=T∗−g1,g2−v1,v2+g2,v2+g1,v1, then it is easy to know T2∈TnΔ. From xg2>xv1 and xg1≤xv2, by Lemma 3, we have that ρT2>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Thus, the hypothesis does not hold; that is, m≥3 holds.Since for any two leaf nodesi,j in T∗, we all have di,r=dj,r. And since du1,r=m, where u1∈W2, then for ∀j1∈W1, we all have that dj1,r=m holds. Choose j1∈W1, then we have that dj1,r=m holds. Without loss of generality, we assume that the shortest path from j1 to r is v1v2⋯vmr, where v1=j1,vm≠g1 and vm≠g2.Sinceu2=u is the nonfull internal vertex, then we have xu2<xv2. Otherwise, xu2≥xv2, let T3=T∗−v1,v2+v1,u2, and it is easy to know T3∈TnΔ. By Lemma 1, we have that ρT3>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Hence, xu2<xv2.Form≥3, hence u3 and v3 have the meaning. For the relationship between xu3 and xv3, we have that xu3<xv3 holds. Otherwise, xu3≥xv3, let T4=T∗−u3,u2−v3,v2+v3,u2+v2,u3, and it is easy to know T4∈TnΔ. Since xu3≥xv3 and xu2<xv2, by Lemma 3, we have that ρT4>ρT∗ holds, this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. By mathematics induction, we can prove that, for any natural number i which satisfies 2≤i≤m, we all have that xui<xvi holds.From Lemma10, we can get xu2>xv1. For the relationship between xu3 and xv2, we have xu3>xv2. Otherwise, xu3≤xv2, let T5=T∗−u3,u2−v1,v2+v1,u3+v2,u2, and it is easy to know T5∈TnΔ. From xu2>xv1 and xu3≤xv2, by Lemma 3, we have that ρT5>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. By mathematics induction, we can prove that, for any natural number i which satisfies 2≤i≤m, we all have that xui>xvi−1 holds.Hence, we havexvm>xum>xvm−1.For the relationship betweenxg2 and xvm, we have xg2>xvm. Otherwise, xg2≤xvm. Let T6=T∗−um,g2−vm−1,vm+g2,vm−1+vm,um, and it is easy to know T6∈TnΔ. From xg2≤xvm and xum>xvm−1, by Lemma 3, we have that ρT6>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Thus, we have thatxg2>xvm>xum>xvm−1 holds, let T7=T∗−um,g2−vm−1,vm+g2,vm+vm−1,um, and it is easy to know T7∈TnΔ. By Lemma 7, we have that ρT7>ρT∗ holds, this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.In conclusion, the hypothesis does not hold; hence, (1) of Theorem19 holds.(2)
Assume that (2) of Theorem19 does not hold, then the nonfull internal vertex u in T∗ should satisfy that there exists v1∈W1 such that v1,u is a pedant edge. For there exist two leaf nodes i,j in T∗ such that di,r≠dj,r and maxi∈W1di,r=mini∈W1di,r. Hence by Theorem 17, we know maxj2∈W2dj2,r=maxj1∈W1dj1,r+1; thus, u is in the third last level of T∗, and this implies a contradiction with T∗ is an almost full-degree unicyclic graph with root node r. Hence, the hypothesis does not hold, and then, (2) of Theorem 19 holds.(3)
SinceW2≠∅ and maxi∈W1di,r≠mini∈W1di,r, by Theorem 17, we get maxi∈W2di,r=mini∈W2di,r=maxi∈W1di,r=mini∈W1di,r+1. And it is easy to know mini∈W1di,r≥1; hence, maxi∈W1di,r≥2. From (5) of Theorem 17, we get that dg1≥3 and dg2≥3 hold.Assume that (3) of Theorem19 does not hold, since dg1≥3 and dg2≥3, the nonfull internal vertex u in T∗ should satisfy that there exists j1∈W2 such that j1,u is a pedant edge of T∗. From W2≠∅,dg1≥3, and dg2≥3, we have that dj1,r≥2 holds.Now we will provedj1,r≥3. Assume that dj1,r≥3 does not hold, then we have dj1,r=2, by maxi∈W2di,r=mini∈W2di,r=maxi∈W1di,r=mini∈W1di,r+1, we know that there exists i∈W1 such that di,r=2. Let the shortest path from i to r be v1v2r, where v1=i,v2≠g1, and v2≠g2, and let the shortest path from j1 to r be u1u2r, where j1=u1,u2=u, and u2 is either g1 or g2. Without loss of generality, we assume that u2=g1, and it is easy to know xv2>xu2; otherwise, xv2≤xu2. Let T1=T∗−v1,v2+u2,v1, then it is easy to know T1∈TnΔ, and by Lemma 1, we have that ρT1>ρT∗ holds. This implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ; hence, xv2>xu2. For u2=g1, thus, we get xv2>xg1. And for v1 is the leaf node of T∗, g2 is the nonleaf node of T∗, and then by Lemma 10, we have xg2>xv1. Thus, we get that xv2>xg1 and xg2>xv1 hold. Let T2=T∗−v1,v2−g1,g2+v2,g2+g1,v1, then it is easy to know T2∈TnΔ. By Lemma 3, we have that ρT2>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Thus, the hypothesis does not hold; hence, dj1,r≥3.Suppose that the shortest path fromj1 to r is u1u2⋯um+1r, where u1=j1, u2=u, and um+1 = g1 or um+1 = g2. Without loss of generality, we assume that um+1=g1. From dj1,r≥3, we can get m≥2. Since maxi∈W2di,r=mini∈W2di,r=maxi∈W1di,r=mini∈W1di,r+1, there exists i∈W1 such that di,r=dj1,r.Suppose that the shortest path fromi to r is v1v2⋯vm+1r, where v1=i,vm+1≠g1, and vm+1≠g2. For the relationship between xv2 and xu2, we have xv2>xu2. Otherwise, xv2≤xu2. Let T3=T∗−v1,v2+u2,v1, then it is easy to know T3∈TnΔ. And by Lemma 1, we have that ρT3>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. In addition, we also can prove xv3>xu3; otherwise, xv3≤xu3. Let T4=T∗−u2,u3−v2,v3+u2,v3+v2,u3, then it is easy to know T4∈TnΔ. From xv2>xu2 and xv3≤xu3, by Lemma 3, we have that ρT4>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ; hence, xv3>xu3. By mathematics induction, we can prove that, for any natural number i which satisfies 2≤i≤m+1, we all have that xvi>xui holds.By Lemma10, we can get xu2>xv1. For the relationship between xu3 and xv2, we have xu3>xv2. Otherwise, xu3≤xv2. Let T5=T∗−u3,u2−v1,v2+v1,u3+v2,u2, then it is easy to know T5∈TnΔ. From xu2>xv1 and xu3≤xv2, by Lemma 3, we have that ρT5>ρT∗ holds. This implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. By mathematics induction, we can prove that, for any natural number i which satisfies 2≤i≤m+1, we all have that xui>xvi−1 holds.Hence, we havexvm+1>xum+1>xvm.Besides, for the relationship betweenxg2 and xvm+1, we have xg2>xvm+1. Otherwise, xg2≤xvm+1. Let T6=T∗−g1,g2−vm,vm+1+g1,vm+1+g2,vm, then it is easy to know T6∈TnΔ. By g1=um+1 and xum+1>xvm, we can get xg1>xvm. And for xg2≤xvm+1, by Lemma 3, we have that ρT6>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Let T7=T∗−g2,um+1−vm,vm+1+g2,vm+1+um+1,vm, then it is easy to know T7∈TnΔ. From xg2>xvm+1 and xvm+1>xum+1>xvm, we can get xg2>xvm+1>xum+1>xvm. By Lemma 7, we have ρT7>ρT∗, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.In conclusion, the hypothesis does not hold, and hence, (3) of Theorem19 holds.
Finally, we give the structure of the maximal-adjacency-spectrum unicyclic graphs in the set of unicyclic graphs given the number of vertices and the maximum degree; in the following Theorem, we describe the structure of the maximal-adjacency-spectrum unicyclic graphs inTnΔ.Theorem 20.
Suppose thatT∗∈TnΔ, and T∗ is a rooted unicyclic graph with root vertex which is the vertex that corresponds to a maximum component in the component of the Perron vector of T∗, then T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ if and only if T∗≅HnΔ.Proof.
Necessity, suppose thatT∗∈TnΔ, T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, let x=x1,x2,…,xn be the Perron vector of T∗, and r be the vertex that corresponds to a maximum component of x. Suppose that T∗ is a rooted unicyclic graph with root node r; from Theorem 18, we have that T∗ is an almost full-degree unicyclic graph with root node r.
Denote the only circle inT∗ by C; from Theorem 16, we have VC=3. Again by Theorem 12, we could suppose that VC=r,g1,g2. Denote W1 = {ii is the root node of T∗, and the shortest path from i to r neither pass g1 nor pass g2}, W2 = {ii is the root node of T∗, and the shortest path from i to r either pass g1 or pass g2}.
When the level ofT∗ is 2, obviously, T∗≅HnΔ.
When the level ofT∗ is 3, if there is no nonfull internal vertex in C, then it is easy to know that T∗≅HnΔ holds. If there exists nonfull internal vertex in C, then according to the degree of the nonfull internal vertex in C, we discuss the following two cases:Case 1. There is one nonfull internal vertex inC with degree 2.In this case, we can provemaxdg1,dg2>2. Otherwise, maxdg1,dg2=2; that is, we have that dg1=dg2=2 holds, and thus, W2=∅. From (1) of Theorem 17, we know T∗≅Tn,2Δ, then T∗ is a rooted unicyclic graph with levels 2, and this implies a contradiction with the level of T∗ is 3. Without loss of generality, we assume that maxdg1,dg2=dg1; hence, dg1>2. And for there is one nonfull internal vertex with degree 2 in C, hence dg2=2, by (5) of Theorem 17, we get that, for ∀i∈W1, we all have that di,r=1 holds. Therefore, T∗≅HnΔ.Case 2. The degree of all the nonfull internal vertices inC is not less than 3.In this case, from Theorem14, we can get that there is only one nonfull internal vertex in C. Without loss of generality, we assume that g2 is the nonfull internal vertex. For the degree of all the nonfull internal vertices in C are not less than 3, the level of T∗ is 3, and VC=r,g1,g2; we have maxj∈W2dj,r=minj∈W2dj,r=2. Then, by (4) of Theorem 17, we get maxj∈W1dj,r≤2.We can provemaxj∈W1dj,r=1. Otherwise, there exists i∈W1 such that di,r=2. Suppose that the shortest path from i to r is ru2u1, where u1=i, and u2 is neither g1 nor g2. According to the relationship between xg2 and xu2, we have xg2<xu2. Otherwise, xg2≥xu2, let T1=T∗−u1,u2+u1,g2, and it is easy to know T1∈TnΔ. By Lemma 1, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Let T2=T∗−u1,u2−g1,g2+g1,u2+u1,g2, then it is easy to know T2∈TnΔ. Again by Lemma 10, we get xg1>xu1. And we have proved xg2<xu2; hence, by Lemma 3, we have that ρT2>ρT∗ holds. This implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ; hence, maxj∈W1dj,r=1. From that maxj∈W2dj,r=minj∈W2dj,r=2,maxj∈W1dj,r=1 and there is only one nonfull internal vertex in C, we know that T∗≅HnΔ holds.In conclusion, when the level ofT∗ is 3, we have that T∗≅HnΔ holds.
Now we discuss the case in which the level ofT∗ is not less than 4.
Suppose thatmaxi∈W1∪W2di,r=k, from the level of T∗ is not less than 4, we know k≥3.
DenoteQ1 = {i∈VT∗di,r=k−1, and the shortest path from i to r pass neither g1 nor g2}, Q2 = {i∈VT∗di,r=k−1, and the shortest path from i to r pass either g1 or g2}.
From Theorem18, we get that T∗ is an almost full-degree unicyclic graph, then if there exists nonfull internal vertex in T∗, we have that the nonfull internal vertex in the second last level of T∗. And since the level of T∗ is not less than 4, if there exists nonfull internal vertex in T∗, then the nonfull internal vertex must belong to the set of VT∗\VC. Again from Theorem 13, we get that there is only one nonfull internal vertex in T∗. Thus, when the level of T∗ is not less than 4, there is at most one nonfull internal vertex in T∗.
When the level ofT∗ is not less than 4, we discuss the following three cases according to the structure of T∗.Case 1. There is no nonfull internal vertex inT∗. At this time, we can discuss the following three subcases:Subcase 1. When for arbitrary leaf nodesi,j in T∗, we all have di,r=dj,r.At this time, it is easy to know thatT∗≅HnΔ holds.Subcase 2. When there exist two leaf nodesi,j in T∗ such that di,r≠dj,r and maxi∈W1di,r=mini∈W1di,r.At this time, from Theorem17, we get maxi∈W1di,r=mini∈W1di,r=maxi∈W2di,r−1=k−1. And for ∀q1∈Q1, we all have that dq1=1 holds.Subcase 3. Whenmaxi∈W1di,r≠mini∈W1di,r.At this time, from Theorems17 and 19, we know that the following two conclusions hold. ① maxi∈W2di,r=mini∈W2di,r=maxi∈W1di,r=mini∈W1di,r+1. ② ∀q2∈Q2 all have that dq2=Δ holds.Case 2. There is only one nonfull internal vertexu in T∗, and one of the brothers of u is leaf node.Now, it is easy to know that there exist two leaf node nodesi,j in T∗ such that di,r≠dj,r, then according to case (2), we discuss the following two subcases:Subcase 1. When there exist two leaf nodesi,j in T∗, which make di,r≠dj,r and maxi∈W1di,r=mini∈W1di,r.At this time, from Theorems17 and 19, we know that the following three conclusions hold: ① maxi∈W1di,r=mini∈W1di,r=maxi∈W2di,r−1=k−1; ② ∀q1∈Q1 all have that dq1=1 holds; ③ the nonfull internal vertex u∈Q2.Subcase 2. Whenmaxi∈W1di,r≠mini∈W1di,r.From Theorems17 and 19, we know that the following three conclusions hold: ① maxi∈W2di,r=mini∈W2di,r=maxi∈W1di,r=mini∈W1di,r+1. ② ∀q2∈Q2 all have that dq2=Δ holds. ③ The nonfull internal vertex u∈Q1.Case 3. There is only one nonfull internal vertexu in T∗, and all the brothers of u are full-degree vertices.According to case (3), we could discuss the following three subcases:Subcase 1. When arbitrary leaf nodesi,j in T∗ all have di,r=dj,r.At this time, from Theorem19, we get that the nonfull internal vertex u∈Q1, and ∀q2∈Q2 all have that dq2=Δ holds. And for there is only one nonfull internal vertex in T∗, then we have that, for ∀j1∈Q1\u, we all have dj1=Δ; hence, T∗≅HnΔ holds.Subcase 2. When there two exist leaf nodesi,j in T∗, which make di,r≠dj,r and maxi∈W1di,r=mini∈W1di,r.At this time, from Theorem19, we get that the nonfull internal vertex u∈Q2. Since there exist two leaf node nodes i,j such that di,r≠dj,r and maxi∈W1di,r=mini∈W1di,r in T∗, by Theorem 17, we get maxi∈W1di,r=mini∈W1di,r=k−1.Subcase 3. Whenmaxi∈W1di,r≠mini∈W1di,r.At this time, from Theorem19, we get u∈Q1. Since maxi∈W1di,r≠mini∈W1di,r, by (3) and (4) of Theorem 17, we can get maxi∈W2di,r=mini∈W2di,r=maxi∈W1di,r=mini∈W1di,r+1. And for there is only one nonfull internal vertex u in T∗, and u∈Q1; hence, for ∀q2∈Q2, we all have dq2=Δ.In the following, we call the subcases (3.2) and (3.3)” case 3″ and the subcases (1.2), (1.3), (2.1), and (2.2) “case 4”.
Sincemaxi∈W1∪W2di,r=kk≥3, we have that T∗ is a rooted unicyclic graph with levels k+1.
Now according to the notation of the vertices inT∗, we make the following instructions: ① except r,g1,g2, if wi∈VT∗, then let wi express one of the vertices in the bottom layer of the first i of T∗. ② If wi∈VT∗, we denote wjj>i the ancestor of wi, which is in the bottom layer of the first j of T∗, (note: wi can equal to any one of the vertex r,g1,g2, and g1 does not express that g1 is in the first last level of T∗ and g2 does not express that g2 is in the second last level of T∗. The above notations in ① and ② are still established when w is changed for any other vertex, which is not g).
Assume thatT∗≇HnΔ, then the structure of T∗ must be as the following case 3 or case 4 shown.Case 3. From the discussion of subcases 3.2 and 3.3, we know that there must exist a leaf nodes2 and an nonfull internal vertex u in T∗ (it is easy to know that u is in the second last level of T∗, denote r2=u), which make u,s2 satisfy the following properties: ① s2 at least has one full-degree brother. ② The common direct ancestor of s2 and u of the nearest generation is in the bottom layer of the first l of T∗, and l≥4. We choose v2 a full-degree brother of s2, denote the common direct ancestor of s2 and u of the nearest generation is rll≥4, then the relationship of the vertices in case 1 is shown in Figure 17, where in Figure 17, u2 is a brother of u and du2=Δ.Ifxr2≥xv2, then let T1=T∗−v1,v2+v1,r2, it is easy to know T1∈TnΔ. And by Lemma 1, we can get ρT1>ρT∗, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ; hence, xr2<xv2. And from Theorem 20, we know xr2>xs2.LetT2=T∗−s2,s3−r2,r3+r2,s3+s2,r3, and it is easy to know that T2∈TnΔ. If xr3≤xs3, from xr2>xs2, and by Lemma 3, we have that ρT2>ρT∗ holds. This implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ; hence, xr3>xs3. Let T3=T∗−v2,s3−r2,r3+r2,s3+v2,r3, then it is easy to know that T3∈TnΔ. From xr2<xv2 and xr3>xs3, by Lemma 3, we have that ρT3>ρT∗ holds. This implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ. Hence, the hypothesis is not established; therefore, T∗≅HnΔ.Case 4. ForT∗ is an almost full-degree unicyclic graph with root node r, T∗≇HnΔ, and from the discussion of subcase 1.2, subcase 1,3, subcase 2.1, and subcase 2.2, we know that there must exist two leaf nodes r2,s2 in the second level of T∗, which satisfy the following properties.There is a cousin or brotheru2 of the nonleaf vertex which is of the nearest generation of r2, there also exists a cousin or brother v2 of the nonleaf vertex which is of nearest generation of s2. This makes that rt (where t≥3) is the common direct ancestor of r2 and u2 of the nearest generation, sm (where m≥3) is the common direct ancestor of s2 and v2 of the nearest generation, w is the common direct ancestor of r2,u2,s2,andv2 of the nearest generation, and u2 and v2 satisfy that u2≠v2,rt≠w, sm≠w and rt≠sm.Without loss of generality, we assume thatt≥m. Then, the relationship of the vertices in case 2 is shown as Figure 18. From the method of marking the index of the vertices in T∗, we know rt=ut,sm=vm, and st=vt.First, by Lemma10, it is easy to know maxxr2,xs2<minxu2,xv2.Ifxut≥xst, then xrt≥xvt. Since xr2<xv2, there is a natural number k that satisfies 2≤k≤t−1, which make xrk<xvk and xrk+1≥xvk+1. Let T1=T∗−rk+1,rk−vk+1,vk+rk+1,vk+vk+1,rk, then it is easy to know T1∈TnΔ. From xrk<xvk and xrk+1≥xvk+1, by Lemma 3, we have that ρT1>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Ifxut<xst, since xu2>xs2, there exists a natural number k that satisfies 2≤k≤t−1, which makes xuk>xsk and xuk+1≤xsk+1. Let T2=T∗−uk+1,uk−sk+1,sk+uk+1,sk+sk+1,uk, then it is easy to know T2∈TnΔ. From xuk>xsk and xuk+1≤xsk+1, by Lemma 3, we have that ρT2>ρT∗ holds, and this implies a contradiction with T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.Hence, the hypothesis is not established; therefore,T∗≅HnΔ.In conclusion, ifT∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, and the level of T∗ is not less than 4, we have that T∗≅HnΔ holds.
By considering the discussion of all the cases according to the level ofT∗, we know that if T∗∈TnΔ, T∗ is a unicyclic graph in which the vertex corresponding to a maximum component in the component of the Perron vector of T∗ is the root node, and T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, then T∗≅HnΔ.
Sufficiency, suppose thatT∗∈TnΔ, T∗ is a rooted unicyclic graph in which the vertex corresponding to a maximum component in the component of the Perron vector of T∗ is the root node, and T∗≅HnΔ. It is easy to know TnΔ<+∞, then there must exist maximal-adjacency-spectrum unicyclic graph in TnΔ. Suppose that T∗∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ, and let T∗∗ be a rooted unicyclic graph in which the vertex corresponding to a maximum component in the component of the Perron vector of T∗ is the root node. Then by the necessity of Theorem 20, we know T∗∗≅HnΔ. And for T∗≅HnΔ, then T∗∗≅T∗; thus, T∗ is a maximal-adjacency-spectrum unicyclic graph in TnΔ.
From Theorem20, we know that if we regard two isomorphic graphs as one graph, then there is only one maximal-adjacency-spectrum unicyclic graph in TnΔ, and the maximal-adjacency-spectrum unicyclic graphs in TnΔ is HnΔ.Figure 17
Vertex graph in case 1.Figure 18
Vertex graph in case 2.


## 4. A New Upper Bound on the Adjacency Spectral Radius of the Unicyclic Graphs

In the following, on the basis of Theorem20, we give a new upper bound on the adjacency spectral radius of the unicyclic graphs.


### 4.1. A New Upper Bound on the Adjacency Spectral Radius of the Unicyclic Graphs

About the upper bound on the adjacency spectral radius of the unicyclic graphs, Hu [3] has given that if T∈TnΔ, then one upper bound of ρT is 2Δ−1.Suppose thatT∈TnΔ, where T=VT,ET. Let C be the only circle in T, and suppose that VC=v1,v2,…,vr. Then, T−EC is a forest composed of B1,B2,…,Br, where B1,B2,…,Br are the rooted trees with the roots v1,v2,…,vr, respectively.DenoteKT=max1≤i≤rmaxdvi,u⋅u∈VBi+1.Rojo [15] has given another upper bound on the adjacency spectral radius of the unicyclic graphs through the following theorem.Theorem 21 (see [15]).
Assume thatT∈TnΔ, if Δ=3 and KT≥4, or Δ≥4, then we have ρT<2Δ−1cosπ/2KT+1.
In order to give a new upper bound on the adjacency spectral radius of the unicyclic graphs, we first introduce some definitions and lemmas.Definition 8.
For the given natural numbern and Δ, which satisfy n>Δ≥3. We suppose that F1 is a unicyclic graph with the maximum degree Δ, and let C1 be the only circle in F1, r be the vertex which corresponds to a maximum component in the components of the Perron vector of F1, F1 be the rooted unicyclic graph with root node r, and F1 satisfies the following properties:①
F1 is an almost completely full-degree unicyclic graph with the maximum degree Δ.②
ρF1≥ρHnΔ.③
There is no nonfull internal vertex inF1.④
Let the set of the vertices ofC1 which is the only circle in F1 be VC1=r,g1,g2, denote W1F1 = {ii is the leaf node of F1, and the shortest path from i to r neither pass g1 nor pass g2}, W2F1 = {ii is the leaf node of F1, and the shortest path from i to r either pass g1 or pass g2}, then we have that mini∈W1F1di,r+1=maxi∈W1F1di,r+1=mini∈W2F1di,r=maxi∈W2F1di,r hold.
Then, we callF1 is a completely Bethe unicyclic graph with the maximum degree Δ, the length of the circle is 3, and the adjacency spectral radius is not less than ρHnΔ.Definition 9.
According to the given natural numbern and Δ, which satisfy n>Δ≥3. Let F be a completely Bethe unicyclic graph with the maximum degree Δ, the length of the circle is 3, and the adjacency spectral radius is not less than ρHnΔ. If for any completely Bethe unicyclic graph F1 with the maximum degree Δ, the length of the circle is 3 and the adjacency spectral radius is not less than ρHnΔ, we all have that ρF1≥ρF holds, then we call F is the minimum completely Bethe unicyclic graph with the maximum degree Δ, the length of the circle is 3, and the adjacency spectral radius is not less than ρHnΔ. We denote the minimum completely Bethe unicyclic graph with the maximum degree Δ, the length of the circle is 3, and the adjacency spectral radius is not less than ρHnΔ by Fn,Δ∗.
Through the direct calculation, we haveKFn,Δ∗=⌈logΔ−1n/3⌉+1, where ⌈x⌉ denotes the smallest positive integral which is not less than x.
For convenience, in the following proof process, now we give another notation ofFn,Δ∗.
Denotean,Δ=KFn,Δ∗,mn,Δ=VFn,Δ∗, it is easy to know an,Δ=⌈logΔ−1n/3⌉+1, and the orderly array an,Δ,mn,Δ is only determined by n,Δ. Besides, it is easy to know that if there exist the natural number n and Δ that satisfy n>Δ≥3, which make the natural number a and m satisfy a=KFn,Δ∗ and m=VFn,Δ∗. Then, Δ is only determined by the orderly array a,m; that is, there exist the natural number n and Δ that satisfy n>Δ≥3, which make that the natural number a and m satisfy a=KFn,Δ∗,m=VFn,Δ∗. Thus, the orderly array a,m can only determine the structural of Fn,Δ∗ which satisfies a=KFn,Δ∗ and m=VFn,Δ∗. Hence, we can denote Fn,Δ∗ by Bmn,Δan,Δ. It is easy to know that if denote a=⌈logΔ−1n/3⌉+1, then we have that Fn,Δ∗=Bmn,Δa holds.Lemma 11.
(see [16]). Suppose that T∈TnΔ, where Δ≥3, if denote a=⌈logΔ−1n/3⌉+1, Aa=0Δ−10⋯⋯0Δ−100⋱⋮00⋱⋱⋱⋮⋮⋱⋱⋱Δ−10⋮⋱Δ−10Δ−20⋯⋯0Δ−22a×a, then we have that ρBmn,Δa=ρAa holds.Lemma 12.
Suppose thatT∈TnΔ, where Δ≥3, if denote a=⌈logΔ−1n/3⌉+1, then when Δ=3 and a≥4, or when Δ≥4, we have that ρBmn,Δa<2Δ−1cosπ/2a+1 holds.Proof.
By the definition ofBmn,Δa and Theorem 21, it is easy to prove that Lemma 12 holds.
Now we give a new upper bound on the adjacency spectral radius of the unicyclic graphs, that is, the following theorem.Theorem 22.
Suppose thatT∈TnΔ, then the following holds:(1)
WhenΔ=3 and n≤6, we have that ρT≤1+2 holds, and the necessary and sufficient condition for the equal sign establishes is T≅B62, that is T≅H63.(2)
WhenΔ=3 and 7<n≤12, we have that ρT≤ρ1 holds, where ρ1 is the maximum real root of the equation λ3−2λ2−3λ+2=0, and the necessary and sufficient condition for the equal sign is T≅B123, that is, T≅H123. Through the calculation by Matlab, we get ρ1=2.5616.(3)
WhenΔ=3 and n≥13, or when Δ≥4, we all have that ρT<2Δ−1cosπ/2a+1 holds, where a=⌈logΔ−1n/3⌉+1.Proof.
(1) WhenΔ=3 and n≤6, it is easy to know Fn,Δ∗=B62; by the definition of B62 and Theorem 20, it is easy to have that ρT≤ρB62 holds. From Theorem 20, we know that the equal sign establishes if and only if T≅B62. If we denote A2=0112, then from Lemma 11, we know that ρB62=ρA2 holds. Hence, we have ρT≤ρA2, through direct calculation, we get ρA2=1+2; thus, we have that ρT≤1+2 holds.
From the above proof process, we know that the necessary and sufficient condition for the equal sign in the inequalityρT≤1+2 establish is T≅B62, that is, T≅H63.
(2) WhenΔ=3 and 7<n≤12, it is easy to know Fn,Δ∗=B123; by the definition of B123 and by Theorem 20, it is easy to have that ρT≤ρB123 holds, and from Theorem 20, we know that the equal sign establishes if and only if T≅B123. If denoted A3=020201012, then from Lemma 11, we know that ρB123=ρA3 holds. Hence, we have ρT≤ρA3, through the direct calculation, we get that ρA3 is the maximum real root of the equation λ3−2λ2−3λ+2=0. Denote the maximum real root of the equation λ3−2λ2−3λ+2=0 by ρ1; thus, we have that ρT≤ρ1 holds.
From the above proof process, we know that the necessary and sufficient condition for the equal sign in the inequalityρT≤ρ1 established is T≅B123, that is, T≅H123.
(3) WhenΔ=3 and n≥13, or when Δ≥4, denote a=⌈logΔ−1n/3⌉+1, then we have Fn,Δ∗=Bmn,Δa. By the definition of Bmn,Δa and Theorem 20, we have that ρT≤ρBmn,Δa holds. Again by Lemma 12, we get ρBmn,Δa<2Δ−1cosπ/2a+1; hence, we have that ρT<2Δ−1cosπ/2a+1 holds, where a=⌈logΔ−1n/3⌉+1.


### 4.2. The Comparison of the Results in Theorems21 and 22

ChooseT∈T194, where T is shown in Figure 19. By Lemma 11, we have that ρT<23cosπ/15 holds, and by Theorem 22, we get ρT<23cosπ/7. Obviously, we have that 23cosπ/7<23cosπ/15 holds; that is, the upper bound of ρT that Theorem 22 gives is better than the one that Theorem 21 gives.Figure 19
A unicyclic graph with maximum degree 4 and vertex number 19.Actually, whenT∈TnΔ and the length of the only circle in T is 3, the upper bound of ρT that Theorem 22 gives is either equal to the one that Theorem 21 gives or better than the one that Theorem 21 gives.ChooseT1∈T194, where T1 is shown in Figure 20. By Theorem 21, we have that ρT1<23cosπ/15 holds, and by Theorem 22, we can get ρT1<23cosπ/7. Obviously, we have that 23cosπ/7<23cosπ/15 holds; that is, the upper bound of ρT that Theorem 22 gives is better than the one that Theorem 21 gives.Figure 20
Another unicyclic graph with maximum degree 4 and vertex number 19.Notice that whenT∈TnΔ and the length of the only circle in T is not less than 4, the upper bound of ρT that Theorem 22 gives may not be better than the one that Theorem 21 gives.In conclusion, sometimes, the upper bound on the adjacency spectral radius of the unicyclic graphs that Theorem22 gives is better than the one that Theorem 21 gives.


## 4.1. A New Upper Bound on the Adjacency Spectral Radius of the Unicyclic Graphs

About the upper bound on the adjacency spectral radius of the unicyclic graphs, Hu [3] has given that if T∈TnΔ, then one upper bound of ρT is 2Δ−1.Suppose thatT∈TnΔ, where T=VT,ET. Let C be the only circle in T, and suppose that VC=v1,v2,…,vr. Then, T−EC is a forest composed of B1,B2,…,Br, where B1,B2,…,Br are the rooted trees with the roots v1,v2,…,vr, respectively.DenoteKT=max1≤i≤rmaxdvi,u⋅u∈VBi+1.Rojo [15] has given another upper bound on the adjacency spectral radius of the unicyclic graphs through the following theorem.Theorem 21 (see [15]).
Assume thatT∈TnΔ, if Δ=3 and KT≥4, or Δ≥4, then we have ρT<2Δ−1cosπ/2KT+1.
In order to give a new upper bound on the adjacency spectral radius of the unicyclic graphs, we first introduce some definitions and lemmas.Definition 8.
For the given natural numbern and Δ, which satisfy n>Δ≥3. We suppose that F1 is a unicyclic graph with the maximum degree Δ, and let C1 be the only circle in F1, r be the vertex which corresponds to a maximum component in the components of the Perron vector of F1, F1 be the rooted unicyclic graph with root node r, and F1 satisfies the following properties:①
F1 is an almost completely full-degree unicyclic graph with the maximum degree Δ.②
ρF1≥ρHnΔ.③
There is no nonfull internal vertex inF1.④
Let the set of the vertices ofC1 which is the only circle in F1 be VC1=r,g1,g2, denote W1F1 = {ii is the leaf node of F1, and the shortest path from i to r neither pass g1 nor pass g2}, W2F1 = {ii is the leaf node of F1, and the shortest path from i to r either pass g1 or pass g2}, then we have that mini∈W1F1di,r+1=maxi∈W1F1di,r+1=mini∈W2F1di,r=maxi∈W2F1di,r hold.
Then, we callF1 is a completely Bethe unicyclic graph with the maximum degree Δ, the length of the circle is 3, and the adjacency spectral radius is not less than ρHnΔ.Definition 9.
According to the given natural numbern and Δ, which satisfy n>Δ≥3. Let F be a completely Bethe unicyclic graph with the maximum degree Δ, the length of the circle is 3, and the adjacency spectral radius is not less than ρHnΔ. If for any completely Bethe unicyclic graph F1 with the maximum degree Δ, the length of the circle is 3 and the adjacency spectral radius is not less than ρHnΔ, we all have that ρF1≥ρF holds, then we call F is the minimum completely Bethe unicyclic graph with the maximum degree Δ, the length of the circle is 3, and the adjacency spectral radius is not less than ρHnΔ. We denote the minimum completely Bethe unicyclic graph with the maximum degree Δ, the length of the circle is 3, and the adjacency spectral radius is not less than ρHnΔ by Fn,Δ∗.
Through the direct calculation, we haveKFn,Δ∗=⌈logΔ−1n/3⌉+1, where ⌈x⌉ denotes the smallest positive integral which is not less than x.
For convenience, in the following proof process, now we give another notation ofFn,Δ∗.
Denotean,Δ=KFn,Δ∗,mn,Δ=VFn,Δ∗, it is easy to know an,Δ=⌈logΔ−1n/3⌉+1, and the orderly array an,Δ,mn,Δ is only determined by n,Δ. Besides, it is easy to know that if there exist the natural number n and Δ that satisfy n>Δ≥3, which make the natural number a and m satisfy a=KFn,Δ∗ and m=VFn,Δ∗. Then, Δ is only determined by the orderly array a,m; that is, there exist the natural number n and Δ that satisfy n>Δ≥3, which make that the natural number a and m satisfy a=KFn,Δ∗,m=VFn,Δ∗. Thus, the orderly array a,m can only determine the structural of Fn,Δ∗ which satisfies a=KFn,Δ∗ and m=VFn,Δ∗. Hence, we can denote Fn,Δ∗ by Bmn,Δan,Δ. It is easy to know that if denote a=⌈logΔ−1n/3⌉+1, then we have that Fn,Δ∗=Bmn,Δa holds.Lemma 11.
(see [16]). Suppose that T∈TnΔ, where Δ≥3, if denote a=⌈logΔ−1n/3⌉+1, Aa=0Δ−10⋯⋯0Δ−100⋱⋮00⋱⋱⋱⋮⋮⋱⋱⋱Δ−10⋮⋱Δ−10Δ−20⋯⋯0Δ−22a×a, then we have that ρBmn,Δa=ρAa holds.Lemma 12.
Suppose thatT∈TnΔ, where Δ≥3, if denote a=⌈logΔ−1n/3⌉+1, then when Δ=3 and a≥4, or when Δ≥4, we have that ρBmn,Δa<2Δ−1cosπ/2a+1 holds.Proof.
By the definition ofBmn,Δa and Theorem 21, it is easy to prove that Lemma 12 holds.
Now we give a new upper bound on the adjacency spectral radius of the unicyclic graphs, that is, the following theorem.Theorem 22.
Suppose thatT∈TnΔ, then the following holds:(1)
WhenΔ=3 and n≤6, we have that ρT≤1+2 holds, and the necessary and sufficient condition for the equal sign establishes is T≅B62, that is T≅H63.(2)
WhenΔ=3 and 7<n≤12, we have that ρT≤ρ1 holds, where ρ1 is the maximum real root of the equation λ3−2λ2−3λ+2=0, and the necessary and sufficient condition for the equal sign is T≅B123, that is, T≅H123. Through the calculation by Matlab, we get ρ1=2.5616.(3)
WhenΔ=3 and n≥13, or when Δ≥4, we all have that ρT<2Δ−1cosπ/2a+1 holds, where a=⌈logΔ−1n/3⌉+1.Proof.
(1) WhenΔ=3 and n≤6, it is easy to know Fn,Δ∗=B62; by the definition of B62 and Theorem 20, it is easy to have that ρT≤ρB62 holds. From Theorem 20, we know that the equal sign establishes if and only if T≅B62. If we denote A2=0112, then from Lemma 11, we know that ρB62=ρA2 holds. Hence, we have ρT≤ρA2, through direct calculation, we get ρA2=1+2; thus, we have that ρT≤1+2 holds.
From the above proof process, we know that the necessary and sufficient condition for the equal sign in the inequalityρT≤1+2 establish is T≅B62, that is, T≅H63.
(2) WhenΔ=3 and 7<n≤12, it is easy to know Fn,Δ∗=B123; by the definition of B123 and by Theorem 20, it is easy to have that ρT≤ρB123 holds, and from Theorem 20, we know that the equal sign establishes if and only if T≅B123. If denoted A3=020201012, then from Lemma 11, we know that ρB123=ρA3 holds. Hence, we have ρT≤ρA3, through the direct calculation, we get that ρA3 is the maximum real root of the equation λ3−2λ2−3λ+2=0. Denote the maximum real root of the equation λ3−2λ2−3λ+2=0 by ρ1; thus, we have that ρT≤ρ1 holds.
From the above proof process, we know that the necessary and sufficient condition for the equal sign in the inequalityρT≤ρ1 established is T≅B123, that is, T≅H123.
(3) WhenΔ=3 and n≥13, or when Δ≥4, denote a=⌈logΔ−1n/3⌉+1, then we have Fn,Δ∗=Bmn,Δa. By the definition of Bmn,Δa and Theorem 20, we have that ρT≤ρBmn,Δa holds. Again by Lemma 12, we get ρBmn,Δa<2Δ−1cosπ/2a+1; hence, we have that ρT<2Δ−1cosπ/2a+1 holds, where a=⌈logΔ−1n/3⌉+1.


## 4.2. The Comparison of the Results in Theorems21 and 22

ChooseT∈T194, where T is shown in Figure 19. By Lemma 11, we have that ρT<23cosπ/15 holds, and by Theorem 22, we get ρT<23cosπ/7. Obviously, we have that 23cosπ/7<23cosπ/15 holds; that is, the upper bound of ρT that Theorem 22 gives is better than the one that Theorem 21 gives.Figure 19
A unicyclic graph with maximum degree 4 and vertex number 19.Actually, whenT∈TnΔ and the length of the only circle in T is 3, the upper bound of ρT that Theorem 22 gives is either equal to the one that Theorem 21 gives or better than the one that Theorem 21 gives.ChooseT1∈T194, where T1 is shown in Figure 20. By Theorem 21, we have that ρT1<23cosπ/15 holds, and by Theorem 22, we can get ρT1<23cosπ/7. Obviously, we have that 23cosπ/7<23cosπ/15 holds; that is, the upper bound of ρT that Theorem 22 gives is better than the one that Theorem 21 gives.Figure 20
Another unicyclic graph with maximum degree 4 and vertex number 19.Notice that whenT∈TnΔ and the length of the only circle in T is not less than 4, the upper bound of ρT that Theorem 22 gives may not be better than the one that Theorem 21 gives.In conclusion, sometimes, the upper bound on the adjacency spectral radius of the unicyclic graphs that Theorem22 gives is better than the one that Theorem 21 gives.



---

*Source: 9861834-2020-07-06.xml*