# On Extremal Spectral Radii of Uniform Supertrees with Given Independence Number

Authors: Lei Zhang; Haizhen Ren
Journal: Discrete Dynamics in Nature and Society
 (2022)

---

## Abstract

A supertree is a connected and acyclic hypergraph. Denote byTm,n,α the set of m-uniform supertrees of order n with independent number α. Focusing on the spectral radius in Tm,n,α, this present completely determines the hypergraphs with maximum spectral radius among all the supertrees with n vertices and independence number α for m−1/mn≤α≤n−1, which extend the results of Lu et al. from tree to uniform supertree. Our techniques are based on the structure properties of supertrees with given independence number and general edge-moving operation. As a byproduct, we also determine the hypergraphs with minimum signless Laplacian spectral radius in Tm,n,α.


---

## Body

## 1. Introduction

LetTm,n,α be a hypergraph with the vertex set VH=1,…,n and edge set EH⊆2VH, where 2VH stands for the power set of VH. The hypergraph H considered here always is simple, i.e., ei≠ej if i≠j, for any ei,ej∈EH. A linear hypergraph is a hypergraph such that its each pair of edges has at most one common vertex (see [1]). A hypergraph H is said to be m-uniform if each edge of H contains precisely m vertices. Suppose I⊂VH. Then, I is called an independent set of H if e⊈I, for any e∈EH. The independence number of H, i.e., αH, is the maximum size of an independent set in H. Two vertices of a hypergraph are adjacent if they belong to the same edge. Say that two edges of a hypergraph are adjacent if their intersection is not empty. In a hypergraph H, the vertex v∈VH is said to be incident to the edge e∈EH if v belongs to e; the alternating sequence of vertices and edges of H, i.e., v1,e1,v2,e2,…,vt,et,vt+1, is called the path of length t in H if any two vertices(or two edges) in this alternating sequence are different, and vi,vi+1∈ei, for i=1,…,t. In particular, we will get a cycle of length t if t>1 and v1=vt+1. A hypergraph H is connected if any two vertices are connected by a path of H and is called acyclic if it contains no cycle. A supertree is a connected and acyclic hypergraph (see [2]). The other undefined definitions here can refer to [1–4].As the development of spectral graph theory, the study on spectra of hypergraphs developed very rapidly. Especially, for the spectral radii ofm-uniform hypergraphs, many researchers gave various upper bounds of it and simultaneously characterized their extremal hypergraphs [5–8]. As a special kind of m-uniform hypergraphs, m-uniform supertrees have attracted much attention and research interest, such as for m-uniform supertrees of order n, i.e., Tm,n. Li et al. studied its extremal spectral properties and determined that the hyperstar (which will be denoted by Sm,n later) attains uniquely the maximum spectral radius in Tm,n [2]; furthermore, Yuan et al. obtained the third and the fourth supertrees with the largest spectral radius in Tm,n ([9]). In addition, Yuan et al. [10] gave the first eight supertrees in Tm,n with the largest spectral radius. In recent years, motivated by the general problem of Brualdi and Solheid [11], it has been found interesting to study spectral radii of hypergraphs with some specific properties. Some scholars have also studied the spectral extremal problems of supertrees with fixed parameters. For example, Xiao et al. [12] investigated m-uniform supertrees with given degree sequence, etc. Zhang et al. considered [13] m-uniform supertrees with perfect matching and gave their maximum value and corresponding supertrees.Denote byTm,n,α the set of m-uniform supertrees of order n with given independent number α. In this present study, we mainly concern the spectral radius in Tm,n,α. This study is organized as follows. First, some necessary notations and useful results are presented in Section 2. Then, in Section 3, by using the structure properties of supertrees with given independence number together with the general edge-moving operation, we prove that Tm,n,α∗ (see Figure 1) is the extremal hypergraph with maximum spectral radius in Tm,n,α for ⌈m−1/mn⌉≤α≤n−1. Furthermore, the hypergraphs with minimum signless Laplacian spectral radius in Tm,n,α are also completely determined.Figure 1
Tm,n,α∗, where α=n−k.


## 2. Preliminary

LetH be a hypergraph with the adjacency tensor AH. The largest eigenvalue of AH, i.e., ρAH, is called the spectral radius of H. We know that AH is weakly irreducible if H is connected. From the Perron–Frobenius theorem, the spectral radius is simple and has a unique positive eigenvector. We will refer to such an eigenvector as the Perron vector of H. Suppose DH is the degree diagonal tensor of H. Then, QH=DH+AH is defined as the signless Laplacian tensor of H. Similarly, the signless Laplacian spectral radius of H, i.e., ρQH, is the largest eigenvalue of QH.SupposeH is an m-uniform hypergraph with the integer m≥2. An m-uniform hypergraph H′ is called a subhypergraph of H if VH′⊆VH and EH′⊆EH. In particular, we call an m-uniform hypergraph H′ as an induced subhypergraph of H if VH′⊆VH and EH′=e∈EH:e⊆VH′. Denote by HS the induced subhypergraph of H on the vertex set S⊆VH. Let NHv (v∈VH) denote the set of the neighbors of v. Denote by dHv=NHv the degree of v in H. If dHv=1, then v is called a leaf. A pendant edge is defined as the edge which is incident with exactly m−1 leaves. A vertex is said to be a support vertex if it has exactly m−1 leaves as its neighbors. For a subhypergraph H′ of the hypergraph H, let NH′v=NHv∩VH′ and dH′v=NH′v, for v∈VH. We will use H−v1v2⋯vm−1 to denote the hypergraph that arises from H by deleting the edge e=v1,v2,…,vm−1∈EH. Similarly, H+v1v2⋯vm−1 is a hypergraph that arises from H by adding an edge e=v1,v2,…,vm−1∉EH, where v1,v2,…,vm−1∈VH.An orderm dimension n tensor A=ai1i2⋯im1≤ij≤n,j=1,…,m over the complex field ℂ is a multidimensional array with all entries ai1i2⋯im∈ℂ.Definition 1 (see [14]).
LetAbe defined as the above, and letx=x1,…,xn⊤be a column vector of dimensionnover the complex fieldℂ. Then,Axm−1is defined to be a vector inℂn, and itsith component is(1)Axm−1i=∑i2,…,im=1naii2⋯imxi2⋯xim,i=1,…,n.
A numberλ∈ℂ is called an eigenvalue of A if there exists a nonzero vector x∈ℂn such that(2)Axm−1=λxm−1,xm=x1m,…,xnm⊤,where x is called an eigenvector of A corresponding to the eigenvalue λ.
Then, the spectral radius ofA, denoted by ρA, is the maximum absolute value of the eigenvalues of A. Here, by the theory of optimization, the other definition of ρA is stated in the following Lemma.Lemma 1 (see [15]).
Suppose thatAis a symmetric nonnegative tensor of ordermand dimensionn. Then,(3)ρA=maxx⊤Ax|x∈ℝ+n,xmm=1,where xmm=∑i=1nxim. In particular, x is an optimal solution of the above maximization problem if and only if it is an eigenvector of A corresponding to ρA.Definition 2 (see [16]).
The adjacency tensor of anm-uniform hypergraphHonnvertices is defined as the tensorAHof ordermand dimensionnwhosei1⋯im-entry is(4)Ai1⋯im=1m−1!,ifi1,…,im∈EH,0,otherwise.
The spectrum, eigenvalues, and spectral radiusρAH of H are defined to be those of its adjacency tensor A.
In [2], Li et al. define a kind of m-uniform hypergraphs, that is, supertrees, and propose an effective method to find an m-uniform hypergraph with larger spectral radius, see as follows.Definition 3.
(see [2], general edge-moving operation). Suppose thatH=V,Eis a hypergraph withu∈Vande1,e2,…,er∈Esuch thatu∉ei,i=1,2,…,rr≥1. Setvi∈eiandei′=ei∖vi∪u. Denote byH′=V,E′the hypergraph withE′=E∖e1,…,er∪e1′,…,er′. Then,H′is called the hypergraph obtained fromHby moving edgese1,…,erfromv1,…,vrtou.Lemma 2 (see [2]).
Suppose thatHis a connectedm-uniform hypergraph andH′is the hypergraph obtained fromHby moving edgee1,…,erfromv1,…,vrtou, whereH′contains no multiple edges. Ifx∈ℝnis the Perron eigenvector ofAH⊲corresponding toρAH, andxu≥max1≤i≤rxvi, thenρAH′>ρAH.Definition 4.
(see [17]). LetH=V,Ebe anm-uniform hypergraph withnvertices andtedges. If there is a disjoint partition of the vertex setV=V0∪V1∪⋯∪Vtsuch thatV0=1,V1=⋯=Vt=m−1andE=V0∪Vi|i∈t, thenHis called a hyperstar, denoted bySm,n.


## 3. Main Results

LetTm,n,αbe the set ofm-uniform supertrees of ordernwith independence numberα. Setα=n−k. Since⌈m−1/mn⌉≤α≤n−1.Then, we have1≤k≤⌈m−1/mn⌉.Obvious,Tm,n,n−1=Sm,nifk=1, whereSm,nis them-uniform hyperstar of ordern. Thus, we considerk≥2in the rest of study.LetSm,k be a hyperstar with VSm,k=v0,v1,…,vm−1,vm,…,v2m−2,…,vk−1 such that dSm,kv0=k−1/m−1 and dSm,kv1=⋯=dSm,kvk−1=1. Tm,n,n−k1 denotes a set of m-uniform supertrees on n vertices which obtained from Sm,k by attaching at least one pendant hyperedge to each vertex of VSm,k so that the total number of the leaves in Tm,n,n−k1 is n−k (see Figure 2).Figure 2
Tm,n,α1, where α=n−k.LetTm,n,n−k2 be a set of m-uniform supertrees on n vertices which obtained from the hyperstar Sm,k+1 by attaching at least one pendant hyperedge to each vertex of VSm,k+1 so that the total number of the leaves in Tm,n,n−k2 is n−k−1, where k≠m−1/mn (see Figure 3). Notice that Tm,n,n−k1,Tm,n,n−k2⊆Tm,n,n−k.Figure 3
Tm,n,α2, where α=n−k.Tm,n,n−k∗ denotes the m-uniform supertrees on n vertices which obtained from Sm,k by attaching one pendant hyperedge to each vertex of VSm,k and attaching n−mk+m−1 vertices to v0 (see Figure 4). Then, Tm,n,n−k∗∈Tm,n,n−k1⊆Tm,n,n−k.Figure 4
Tm,n,α∗, where α=n−k.Lemma 3.
LetTbe anm-uniform supertree.RTdenotes the set of the leaves ofT. Then, for everym-uniform supertreeT, there exists a maximum independent setITofTsuch thatRT⊆IT.Proof.
LetIT be a maximum independence set such that IT∩RT is as large as possible. Suppose that there exists a leaf v∈RT, but v∉IT. Let u be the support vertex of v. Then, u∈IT. Set IT=IT\u∪v. Thus, I′T is also a maximum independence set of T such that I′T∩RT>IT∩RT, a contradiction. The proof is complete.Lemma 4.
LetT∈Tm,n,n−ksuch that the spectral radius ofTis as large as possible. Then, T∈Tm,n,n−k1.Proof.
Let(5)x=x1,x2,…,xn⊤be the Perron vector of AT, where xi corresponds to the vertex vi1≤i≤n. First, we prove that T∈Tm,n,n−k1∪Tm,n,n−k2. Suppose T∈Tm,n,n−k\Tm,n,n−k1∪Tm,n,n−k2. Then, the number of the support vertices of the induced sub-supertree TVT\RT is at least 2. Choose two support vertices of TVT\RT, say v1 and v2, such that the distance between v1 and v2 in TVT\RT is as lager as possible. Then, T is shown as in Figure 5, where a,b≥1,(6)dTui≥2fori=1,…,a,dTua+i=1fori=1,…,sifs≥1,dTwi≥2fori=1,…,b,dTwb+i=1fori=1,…,tift≥1,and for other vertices in T, the degree of each of them in T is 1. Let H1 be the component of T−v1c1⋯cm−2v3−v2d1⋯dm−2v4 containing the vertices v3,v4 if v1,v2⊈e∈ET (see Figure 5). If v1,v2⊆e∈ET, denote H1=∅ (see Figure 5). We consider the following three cases.Figure 5
T∈Tm,n,n−k\Tm,n,n−k1∪Tm,n,n−k2.Case 1.
s,t≥1.
By Lemma3, there exists a maximum independent set IT such that RT⊆IT. Since s,t≥1, we have(7)αT=IT=∑i=1am−1dTui−1+sm−1+∑i=1bm−1dTwi−1+tm−1+αH1.
We constructT1 from T as follows:(8)T1=T−∑i=0a−1m−1v1u1+iu2+i⋯um−1+i+∑i=0a−1m−1v2u1+iu2+i⋯um−1+i,ifxv1≤xv2,T−∑i=0b−1m−1v2w1+iw2+i⋯wm−1+i+∑i=0b−1m−1v2w1+iw2+i⋯wm−1+i,ifxv1>xv2,
LetIT1 be a maximum independent set of T1 such that RT1⊆IT1. Then, in either case,(9)αT1=IT1=∑i=1am−1dT1ui−1+sm−1+∑i=1bm−1dT1wi−1+tm−1+αH1=αT.
Hence,T1∈Tm,n,n−k. By Lemma 2, we have(10)ρAT<ρAT1.
It is a contradiction.Case 2.
s=0, but t≥1 (or s≥1 but t=0).
Assume, without loss of generality, thats=0, but t≥1 (see Figure 6). Similar to Case 1, let IT be a maximum independent set of T such that RT⊆IT. Then,(11)αT=IT=∑i=1am−1dTui−1+∑i=1bm−1dTwi−1+tm−1+αTVH1∪v1.
We can constructT1 from T as(12)T2=T−∑i=0a−1m−1v1u1+iu2+i⋯um−1+i+∑i=0a−1m−1v2u1+iu2+i⋯um−1+i,ifxv1≤xv2,T−∑i=0b−1m−1v2w1+iw2+i⋯wm−1+i+∑i=0b−1m−1v2w1+iw2+i⋯wm−1+i,ifxv1>xv2,
LetIT2 be a maximum independent set of T2 such that RT2⊆IT2. Then, in either case,(13)αT2=IT2=∑i=1am−1dTui−1+∑i=1bm−1dTwi−1+tm−1+αTVH1∪v1=αT.
Thus,T2∈Tm,n,n−k. By Lemma 2, we obtain(14)ρAT<ρAT2,a contradiction.Figure 6
T′′.Case 3.
s,t=0 (see Figure 7).
LetIT be a maximum independent set of T such that RT⊆IT. Then,(15)αT=IT=∑i=1am−1dTui−1+∑i=1bm−1dTwi−1+αTVH1∪v1,v2.
Let(16)T3=T−∑i=0a−1m−1v1u1+iu2+i⋯um−1+i+∑i=0a−1m−1v2u1+iu2+i⋯um−1+i,fxv1≤xv2,T−∑i=0b−1m−1v2w1+iw2+i⋯wm−1+i+∑i=0b−1m−1v2w1+iw2+i⋯wm−1+i,ifxv1>xv2.
SupposeIT3 is a maximum independent set of T3 such that RT3⊆IT3. Then, in either case,(17)αT3=IT3=∑i=1am−1dT1ui−1+∑i=1bm−1dT1wi−1+αT3VH1∪v1,v2=αT.
Therefore,T3∈Tm,n,n−k. By Lemma 2, we obtain(18)ρAT<ρAT3,a contradiction.
From Cases1–3 we know that T∈Tm,n,n−k1∪Tm,n,n−k2. In the following, we prove T∉Tm,n,n−k2. Suppose that T∈Tm,n,n−k2. Let(19)Nv0=v1,…,vm−1,vm,…,v2m−2,…,vksee Fig.3.
Ifxv0≥xv1, set T′ is a hypergraph obtained from T by moving dv1−1 pendant edges attaching vertices v1 from v1 to v0. Then, in either case, T′∈Tm,n,n−k1. By Lemma 2, we have(20)ρAT<ρAT′,a contradiction. If xv0<xv1, set T′′ is a hypergraph obtained from T by moving all edges attaching vertices v0 from v0 to v1. Then, in either case, T′′∈Tm,n,n−k1. By Lemma 2, we have(21)ρAT<ρAT′,a contradiction. Hence, we obtain that T∈Tm,n,n−k1. This completes the proof.
Now, we give our main result of this section.Figure 7
T′′′.Theorem 1.
LetT∈Tm,n,αwithα=n−kandk≥2. Then,(22)ρAT≤ρATm,n,α∗and equality holds if and only ifT=Tm,n,α∗.Proof.
LetT∈Tm,n,n−k such that the spectral radius of T is as large as possible. By Lemma 4, T∈Tm,n,n−k1. Since Tm,n,n−k∗∈Tm,n,n−k1⊆Tm,n,n−k, suppose T≠Tm,n,n−k∗. Then, we can assume that dv1≥3 (see Figures 2–4). Let(23)Nv1=v0,v2,…,vm−1,f1,f2,…,fm−1,fm,…,f2m−2,…,fs,(24)Nv0=v1,v2,…,vk−1,w1,w2,…,wm−1,wm,…,w2m−2,…,wt,where dw1=⋯=dwt=1. Then,(25)sm−1≥2andt≥m−1.
Ifk=m−1, then t≥2m−1 since T≠Tm,n,n−k∗. Assume, without loss of generality, that xv1≤xv0. Let(26)T′=T−v1f1f2⋯fm−1+v0f1f2⋯fm−1.
Then, by Lemma2, we have(27)ρAT<ρAT′,a contradiction. Thus, we will assume that k≥2m−1.
Let(28)T3=T−v1f1f2⋯fm−1+v0f1f2⋯fm−1,ifxv1≤xv0,T−v0w1w2·swm−1+v1w1w2⋯wm−1,ifxv1>xv0andtm−1≥2,T−v0vm⋯v2m−2−v0v2m−1⋯v3m−3−⋯−v0vk−1−m−2⋯vk−1+v1vm⋯v2m−2+v1v2m−1⋯v3m−3+⋯+v1vk−1−m−2⋯vk−1,ifxv1>xv0andtm−1=1.
Then, in either case, by Lemma2, we have(29)ρAT<ρAT′,and notice that αT′=αT=n−k, a contradiction. The proof is complete.Remark 1.
Whenm=2, Theorem 1 implies that the results of Lu et al. (Theorem 3 (see [18])).
In addition, we cite the following lemma.Lemma 5 (see [2]).
LetH=V,Ebe a connected hypergraph withei∈Efori=1,2,…,randu∈Vsuch thatu∉ei. Forvi∈eii=1,2,…,r,H′denotes the hypergraph obtained fromHby moving edgese1,…,erfromv1,…,vrtou, andH′contains no multiple edges. Ifxis the principal eigenvector ofQHcorresponding toρQH, suppose that(30)xu≥max1≤i≤rxvi.
Then,(31)ρQH′>ρQH.
By the same argument as the proof of Theorem1, we have the following result on signless Laplacian spectral radius of Tm,n,α.Theorem 2.
LetT∈Tm,n,αwithα=n−kandk≥2. Then,(32)ρQT≥ρQTm,n,α∗and equality holds if and only ifT=Tm,n,α∗.



---

*Source: 3930470-2022-05-19.xml*