# Sharp Bounds on the Spectral Radii of Uniform Hypergraphs concerning Diameter or Clique Number

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

---

## Abstract

In this paper, we defined two classes of hypergraphs, hyperbugs and kite hypergraphs. We show that balanced hyperbugs maximize the spectral radii of hypergraphs with fixed number of vertices and diameter and kite hypergraphs minimize the spectral radii of hypergraphs with fixed number of vertices and clique number.


---

## Body

## 1. Introduction

Hypergraph theory deals extensively with hypergraph invariants, i.e., functioniH represents a certain invariant of the hypergraph as a real number or integer, [1–3]. Well-known invariants are the independence and chromatic numbers, the diameter, and so on. Extremal hypergraph theory deals with the problem of characterizing the families of hypergraph H for which an invariant iH is minimum or maximum. Usual hypergraph classes, such as complete hypergraphs, hyperpaths, hypercycles, and hyperstars, frequently appear as extremal hypergraphs in hypergraph spectral theory problems. Here we want to turn the readers’ attention to two novel, simply defined, hypergraph classes that appear as extremal hypergraphs in several hypergraph spectral theory problems. We call them hyperbugs and kite hypergraphs.In recent years, a few results are known about the spectral radii of hypergraphs with propertyP, for example, Fan et al. [4] considered the maximum spectral radius of uniform hypergraphs with few edges. Xiao et al. [5] investigated the supertrees whose spectral radii attain the maximum among all uniform supertrees with given degree sequence. Xiao and Wang [6] also determined the unique hypergraph with the maximum spectral radius among all the uniform supertrees and all the connected uniform unicyclic hypergraphs with given number of pendant edges, respectively. Zhang and Li [7] characterized the hypergraph with maximum spectral radius among all connected uniform hypergraphs with given number of pendant vertices. Su et al. [8] determined the largest spectral radius of hypertrees with r edges and given size of matching. Xiao et al. [9] determined the supertrees with the first two largest spectral radii among all supertrees in the set of m-uniform supertrees with r edges and diameter d. Su et al. [10] determined the first ⌊d/2⌋+1 largest spectral radius of k-uniform supertrees with size m and diameter d. In addition, the first two smallest spectral radii of supertrees with size m are also determined. For other related results, readers are referred to [11–20]. In the spirit of the general problem of Brualdi and Solheid [21], one can ask how large or how small can be the spectral radius of hypergraphs with some specific properties. For example: how large ρH can be if H is a k-uniform hypergraph of order n and diameter at least r? Similarly, how small ρH can be if H is a k-uniform hypergraph of order n and clique number at least 2? In fact, for k=2, this question has been answered by Stevanović and Hansen in [22, 23], respectively.Lemma 1 (see [22, 24]).
LetG be a graph of order n with diamG≥r. If r=1, then ρG=ρKn. If r≥2, then(1)ρG≤ρBn−r+2,r2,r2,holds if and only if G≅Bn−r+2,r/2,r/2, where Bp,q,r denotes the graph obtained from a complete graph Kp by deleting an edge and attaching paths Pq and Pr to its ends.Lemma 2 (see [23, 24]).
IfG is a connected graph of order n with clique number ω≥2, then ρG≥ρPKn−ω,ω holds if and only if G≅PKn−ω,ω, where PKp,q denotes the graph obtained by joining an end vertex of the path Pp to a vertex of the complete graph Kq.In this paper, we mainly generalize the above two results to thek-uniform hypergraphs.


## 2. Notations and Preliminaries

A hypergraphH is a pair V,E with E⊆PV and PV denotes the power set of V, V=VH is a nonempty finite set (the vertex set), and the elements of E=EH are called hyperedges or edges. A hypergraph H is k-uniform if every edge e∈EH contains precisely k vertices. A sub-hypergraph H′ of H is a k-uniform hypergraph such that VH′⊆VH and EH′⊆EH. For a vertex v∈V, we denote by ev the set of edges containing v. We write euv to express the edges containing the vertices u,v. The cardinality ev is the degree of v, denoted by degv. A vertex with degree one is called a core vertex. If any two edges in H share at most one vertex, then H is said to be linear hypergraph. Let H−e be obtained by deleting an edge e from H, i.e., H−e=V,E\e. H−Ve is obtained from H by deleting k vertices of edge e, i.e., H−v1,…,vk, where e=v1,…,vk.A walkW in a hypergraph H is a finite alternating sequence of vertices and edges, i.e., W=v0,e1,v1,e2,…,ek,vk, satisfying that both vi−1 and vi are incident to ei for 1≤i≤k. A walk W is a path if all the vertices vi for i=0,1,…,k and all the edges ej for j=1,2,…,k in W are distinct. The length of a path is the number of edges in it. A hypergraph is connected, if there is a path between any pair of vertices of H. In this paper, we assume that hypergraphs are k-uniform and connected.LetH=V,E be a k-uniform hypergraph. An edge e is called a pendant edge if e contains exactly k−1 core vertices. If e is not a pendant edge, it is called a nonpendant edge. A path P=v0,e1,v1,…,vp−1,ep,vp of H is called a pendant path (attached at v0), if all of the vertices v1,…,vp−1 are of degree two and the vertex vp and all the k−2 vertices in the set ei\vi−1,vi are core vertices in Hi=1,…,p. Let H=V,E be a k-uniform hypergraph of order n; if E consists of all k-subsets of V, then H is a complete k-uniform hypergraph, denoted by Knk. A clique of a k-uniform hypergraph H is a complete k-uniform sub-hypergraph of H. A maximal clique is a clique that cannot be extended to a larger clique. The clique number ωH of a hypergraph H is the number of vertices in the maximum clique of H.Definition 1.
(see [11]). The adjacency tensor of an r-uniform hypergraph H on n vertices is defined as the tensor AH of order r and dimension n whose i1,…,ir-entry is(2)Ai1,…,ir=1r−1!,ifi1,…,ir∈EH,0,otherwise.The spectrum, eigenvalues, and spectral radiusρH of H are defined to be those of its adjacency tensor A.The following relation between the spectral radius of ak-uniform hypergraph and its sub-hypergraph can be found in [11].Lemma 3 (see [11]).
LetH be a k-uniform hypergraph, and H′ is a sub-hypergraph of H; then, ρH′≤ρH.The first upper and lower bounds of spectral radius of ak-uniform hypergraph are given by Cooper et al. as follows.Lemma 4 (see [11]).
LetH be a k-uniform hypergraph. Let d be the average degree of H and Δ be the maximum degree. Then,(3)d≤ρH≤Δ.In [14], Li et al. proposed an effective method to find a k-uniform hypergraph with larger spectral radius.Definition 2.
(see [14]) (general edge-moving operation). Suppose that H=V,E is a hypergraph with u∈V and e1,e2,…,er∈E, such that u∉ei,i=1,2,…,rr≥1. Let vi∈ei and ei′=ei∖vi∪u. Let H∗=V,E∗ be the hypergraph with E∗=E∖e1,…,er∪e1′,…,er′. Then, we say that H∗ is obtained from H by moving edges e1,…,er from v1,…,vr to u.According to the definition of general edge-moving operation, Li et al. obtained the following relation of spectral radius.Lemma 5 (see [14]).
Suppose thatH is a k-uniform hypergraph and H∗ is the hypergraph obtained from H by moving edge e1,…,er from v1,…,vr to u, where H∗ contains no multiple edges. If x∈ℝn is the perron eigenvector of AH corresponding to ρH and xu≥max1≤i≤rxvi, then ρH∗>ρH.In [14], Li et al. also gave two extremal results about upper and lower bounds of the kth power of an ordinary tree T.Lemma 6 (see [14]).
LetTk be the kth power of an ordinary tree T. Suppose that Tk has n vertices. Then, we have(4)ρAPnk<ρATk<ρASnk,where the former equalities hold if and only if Tk≅Pnk, and the latter equalities hold if and only if Tk≅Snk.LetH be a k-uniform hypergraph. Let Hp,qu be the hypergraph obtained by attaching the paths Pp and Pq to u∈H. Similarly, let Hp,qu,v be the hypergraph obtained by attaching the paths Pp to u∈H and Pq to v∈H.In [17], Shan et al. gave an operation to find a k-uniform hypergraph with larger spectral radius.Lemma 7 (see [17]).
Letu,v be two non-pendant vertices of hypergraph H. If there exist an internal path P with s length in hypergraph Hp,qu,v for any p≥q≥1, then we have(5)ρHp+1,q−1u,v<ρHp,qu,v,forp−q+1≥s≥0.In [12], Guo and Zhou gave another operation to find a k-uniform hypergraph with larger spectral radius.Lemma 8 (see [12]).
Fork≥2, let H be a k-uniform hypergraph with EG≥1 and u∈VG. For p≥q≥1, we have(6)ρHp,qu>ρHp+1,q−1u.A hypergraphH is isomorphic to a hypergraph H′, if there is a bijection σ:VH⟶VH′ such that v1,v2,…,vk∈EH if and only if σv1,σv2,…,σvk∈EH′. The bijection σ is called an isomorphism of H. If H=H′, then σ is called an automorphism of H. Let x be a vector defined on VH and σ be an automorphism of H. Two vertices u and v are equivalent in H, if there exists an automorphism σ of H such that σu=v, u∼v. Denote xσ to be the vector such that xσu=xσu for each u∈VH.Lemma 9 (see [13]).
LetH be a k-uniform hypergraph and σ be an automorphism of H. Let x be an eigenvector of AH; then, xσ=x. Further, for two vertices u and v in VH, if u∼v, there must be xu=xv.Next we discuss two novel hypergraph families, i.e.,hyperbugs and kite hypergraphs, which are defined as follows.Definition 3.
A hyperbugℬp,q,s is a k-uniform hypergraph obtained from a complete k-uniform hypergraph Kpk by deleting an edge u,u2,…,uk−2,v attaching paths Pq and Ps at u and v. A hyperbug is balanced if q−s≤1 (see Figure 1 for an example).Figure 1
3-uniformℬ4,3,4.Definition 4.
A kite hypergraphPKp,q is a k-uniform hypergraph obtained by joining an end vertex of the path Pp to a vertex of the complete k-uniform hypergraph Kqk (see Figure 2 for an example).Figure 2
3-uniformPK3,4.In this paper, we obtain that ifH is a k-uniform hypergraph of order n and diameter at least r, then(7)ρH≤ρℬn−r−2k−1,r2,r2,holds if and only if H≅ℬn−r−2k−1,r/2,r/2. Furthermore, we also obtain that if H is a k-uniform hypergraph of order n with clique number ω≥2, then ρH≥ρPKn−ω,ω holds if and only if H≅PKn−ω,ω. These generalize some related results of Nikiforov and Rojo [24] and Hansen and Stevanović [22].


## 3. Main Results

### 3.1. The Spectral Radii of Uniform Hypergraphs with Fixed Number of Vertices and Diameter

LetH be a k-uniform hypergraph containing a path P as a sub-hypergraph (see Figure 3). We say that P is a pendant path if one of its ends is a cut vertex of H; we call this vertex the root of P. Note that a hypergraph can have multiple pendant paths, which may share roots; e.g., the hypergraph ℬp,q,s has two pendant paths.Figure 3
H.From Figure3, we see that if H′ is a k-uniform hypergraph and H is a k-uniform hypergraph with a pendant path P and ρH=ρ≥2, then the distribution of the entries of an eigenvector to ρ along P is well determined.In fact, letP=u1,…,ui,…,ui+k−1 be a pendant path in H with root u1. Let x1,…,xi,…,xi+k−1i∈ℕ be the entries of a positive unit eigenvector to ρH corresponding to u1,…,ui,…,ui+k−1i=nk−1+1,n∈ℕ. The eigenequation of AH for xj1≤j≤i+k−1 is(8)ρxik−1=xi−k+1xi−k+2,…,xi−1+xi+1xi+2,…,xi+k−1,which implies that(9)xi−k+1xi−k+2,…,xi−1−ρxik−1+xi+1xi+2,…,xi+k−1=0,xi−k+1xi−k+2,…,xi−1xi+1xi+2,…,xi+k−1−ρxik−1xi+1xi+2,…,xi+k−1+1=0,xi−k+1xi−k+2,…,xi−1xik−1⋅xik−1xi+1xi+2,…,xi+k−1−ρxik−1xi+1xi+2,…,xi+k−1+1=0.The above equation is equivalent to the following crucial equation:(10)X2−ρX+1=0.We can writeγ for the root of (10):(11)γ≔ρ+ρ2−42,and note that γ is real since ρ≥2; moreover, γ≥1, with strict inequality if ρ>2. Note also that the other root (10) is equal to γ−1.By equations (10) and (11), we can obtain the following theorem.Theorem 1.
LetH be a k-uniform hypergraph with ρ≔ρH≥2. Let P=u1,…,ui,…,ui+k−1 be a pendant path in H with root u1. Let x1,…,xi,…,xi+k−1,i=nkn∈ℕ be the entries of a positive unit eigenvector to ρH corresponding to u1,…,ui,…,ui+k−1,i=nk−1+1,n∈ℕ. If γ is defined by (11), then for every xj1≤j≤i+k−1, we have(12)xi−k+1>γxi−k+2,xi−k+1>γxi,i=nk−1+1,n∈ℕ.Proof.
The eigenequation ofAH for xji+1≤j≤i+k−1 is(13)ρxi+k−1k−1=xixi+1,…,xi+k−2,ρxi+k−2k−1=xixi+1,…,xi+k−3xi+k−1,…ρxi+1k−1=xixi+2,…,xi+k−1.
Sinceρ>γ, then(14)xixi+1,…,xi+k−2>γxi+k−1k−1,xixi+1,…,xi+k−3xi+k−1>γxi+k−2k−1,…xixi+2…xi+k−1>γxi+1k−1.
By multiplying the abovek−1 inequalities, we have(15)xik−1xi+1k−2,…,xi+k−1k−2>γk−1xi+1k−1xi+2k−1,…,xi+k−1k−1.
So, we have(16)xik−1>γk−1xi+1xi+2,…,xi+k−1.
By Lemma8, we have(17)xi+1=xi+2=⋯=xi+k−2=xi+k−1.
Thus,(18)xi>γxi+1,(19)xi>γxi+k−1.
Proceeding by induction, from the eigenequation ofAH for xji−k+2≤j≤i and the induction assumption, we get(20)ρxik−1=xi−k+1xi−k+2,…,xi−1+xi+1xi+2,…,xi+k−1,ρxi−1k−1=xi−k+1xi−k+2,…,xi−2xi,ρxi−2k−1=xi−k+1xi−k+2,…,xi−3xi−1xi,…ρxi−k+2k−1=xi−k+1xi−k+3,…,xi−1xi.
Thus,(21)ρxik−1≤γ−1k−1xik−1+xi−k+1xi−k+2,…,xi−1,xi−k+1xi−k+2,…,xi−1≥ρ−r−1k−1xik−1>γxik−1,xi−k+1xi−k+2,…,xi−2xi>γxi−1k−1,…xi−k+1xi−k+3,…,xi−1xi>γxi−k+2k−1.
By multiplying the abovek−1 inequalities, we have(22)xi−k+1k−1xi−k+2k−2,…,xik−2>γk−1xik−1xi−1k−1,…,xi−k+2k−1.
So, we get(23)xi−k+1k−1>γk−1xi−k+2xi−k+3,…,xi.
Suppose(24)xi−k+1<γxi−k+2,(25)xi−k+1<γxi.
Substituting equation (24) into equation (23), we obtain(26)xi−k+1k−1>γxi−k+1k−2xi,xi−k+1>γxi,which contradicts equation (25). Hence,(27)xi−k+1>γxi−k+2,(28)xi−k+1>γxi.
The proof is completed.Corollary 1.
Given the hypotheses of Theorem1., we have(29)x1>xk>x2k−1>⋯.Lemma 10.
Letp and q+r be fixed positive integers; then,(30)ρℬp,q,r<ρℬp,q+r/2,q+r/2.Proof.
According to the definition ofℬp,q,r, we must have an internal path with 2 lengths in the k-uniform hypergraph Bp,q,r. Without loss of generality, we assume q≥r≥1. By Lemma 6, we have(31)ρℬp,q,r<ρℬp,q+1,r−1,forq−r+1≥2.
Continuing this operation, whenp and q+r are fixed, we have(32)ρℬp,q,r<ρℬp,q+r/2,q+r/2.Theorem 2.
LetH be a k-uniform hypergraph of order n with diamH≥r. If r=1, then ρH=ρKnk. If r≥2, then(33)ρH≤ρℬn−r−2k−1,r/2,r/2,holds if and only if H≅ℬn−r−2k−1,r/2,r/2.Proof.
The statement is clear ifr=1, for Knk is the only hypergraph of order n and diameter 1. Suppose that r≥2; let H be a hypergraph with maximal spectral radius among all k-uniform hypergraphs of order n and diamH≥r. This choice implies that H is edge-maximal, that is, no edge can be added to H without diminishing its diameter. According to Lemma 9, we only need to show that H=ℬn−r−2k−1,p,r−p for some p, satisfying 1≤p≤r−1.
Letρ≔ρH and u,v be vertices of H at distance exactly r, for every i=0,…,r. Let Vi be the set of the vertices at distance i from u, and degrees of these vertices are greater than 2. Since H is edge-maximal, the set Vi∪Vi+1 induces a linear complete hypergraph, for every i=0,…,r−1. It is also clear that V0=1; moreover, it is not hard to see that Vr=1. Indeed, assume for a contradiction that Vr≥2 and add all edges between Vr−2 and V\v. These additional edges do not diminish the distance between u and v; hence, H is not edge-maximal, contradicting its choice; therefore, Vr=1.
Furthermore, by Lemma3, we have(34)ΔH≥ρH>ρℬn−r−2k−1,r/2,r/2>ρKn−r−2k−1−e,>δKn−r−2k−1−e≥Cn−1−r−2k−1k−1−1,and so ΔH≥Cn−1−r−2k−1k−1. Suppose that w is vertex of maximum degree in H, and let w∈Vi. Clearly, 0<i<r, and in view of(35)dw≤CVi−1+Vi+Vi+1k−1−1k−1,we find that(36)CVi−1+Vi+Vi+1k−1−1k−1=Cn−∑j<i−1Vj−∑j>i+1Vjk−1−1k−1,=Cn−1−r+1−3k−1k−1=Cn−1−r−2k−1k−1.
Hence, ifj<i−1 or j>i+1, then Vi=1; furthermore,(37)Vi−1+Vi+Vi+1k−1=n−r−2k−1.
IfVi−1=Vi+1=1, then obviously H=ℬn−r−2k−1,i,r−i, so Theorem 2 is proved in this case. Next we will show that all other cases lead to contradictions, by constructing a hypergraph H∗ of order n and diamH∗=r with ρH∗>ρ. Suppose that x:=x1,…,xn is a positive unit vector to ρH.
First, consider the caseVi−1=1 and Vi+1≥2. If Vi=1, the proof is completed. So, we suppose that Vi≥2. Let Vi−1=a,Vi+2=b, and suppose by symmetry that xb≥xa. Choose a vertex w∈Vi, obtain H′ from H, delete the edge ewa, and add the edge ewb. In other words, H′ is obtained by moving the vertex w from Vi into Vi+1. By symmetry and Lemma 8, xw′=xw for any w′∈Vi; thus, the choice of H implies that(38)0≥ρH∗−ρ≥x⊤AH∗x−x⊤AHx,=k∑e∈EH∗xe−k∑e∈EHxe=2kxewb−xewa≥0,implying that ρH∗=ρH and that x is an eigenvector to ρH. However, the neighborhood of a in H∗ is a proper subset of the neighborhood of a in H, so the eigenequations for ρH∗ and ρH for the vertex a are contradictory.
The same argument disposes also of the caseVi−1≥2 and Vi+1=1; thus, to complete the proof, it remains to consider the case Vi−1≥2 and Vi+1≥2.
LetVi−2=a,c∈Vi−1,d∈Vi+1, and Vi+2=b. Our first step is to show that(39)xc≥xa.
Note that ifi≥3 and Vi−3=z, then Theorem 1 gives xz<xa. Hence, setting l:=Vi−1, the eigenequation for the vertex a implies that(40)ρxak−1=xeaz\a+lxeac\a.
According toxz<xa and Theorem 1, we have(41)ρxak−1<xak−1+lxck−1,yielding in turn(42)xcxak−1>ρ−1l.
Since(43)ρ−1≥Cn−1−r−2k−1k−1−1−1=CVi−1+Vi+Vi+1k−1−1k−1−2>CVi−1+2k−1k−1−2≥l+2−2=l,inequality (39) is proved. By symmetry, we also see that xd>xb. Suppose, again by symmetry, that xb≥xa, which yields xa≤xb≤xd. Choose a vertex w∈Vi−1, obtain H∗ from H, delete the edges ewa, and add the edges ews for all s∈Vi+1. In other words, H∗ is obtained by moving the vertex w from Vi−1 into Vi. The choice of H implies that(44)0≥ρH∗−ρ≥x⊤AH∗x−x⊤AHx,=k∑e∈EH∗xe−k∑e∈EHxe≥2kVi+1xewd−xewa≥0.
This contradiction completes the proof of Theorem2.Remark 1.
From the above result, whenk = 2, the result of Lemma 1 is obvious [22].


### 3.2. The Spectral Radii of Uniform Hypergraphs with Fixed Number of Vertices and Clique Number

Lemma 11.
Fork≥2, let H be a k-uniform hypergraph with EH≥1 and u∈VH. For p≥q≥1, if HTu is the k-uniform hypergraph obtained by identifying u with a vertex of a hypertree T of order n, then(45)ρHTu>ρHn,1u.Proof.
This can be carried out along well-known lines by applying Lemma7 to recursively flatten T until it becomes a path.Theorem 3.
IfH is a k-uniform hypergraph of order n with clique number ω≥2, then ρH≥ρPKn−ω,ω holds if and only if H≅PKn−ω,ω.Proof.
LetH be a k-uniform hypergraph with minimal spectral among all connected k-uniform hypergraphs of order n and clique number ω. If ω=2, by Lemma 5, H must be a path, as the path is the hypergraph with smallest spectral radius among connected k-uniform hypergraphs of given order. Thus, we suppose that ω≥3 and let H′ be a complete k-uniform sub-hypergraph of H of order ω.
Further,H should be edge-minimal, that is, the removal of any edge of H either makes H disconnected or its clique number diminishes. In particular, if H′′ is the hypergraph obtained by removing the edges of H′, then the components of H′′ are supertrees, and each component has exactly one vertex in common with H′. It follows that H is isomorphic to a complete k-uniform hypergraph of order ω with hypertrees attached to some of its common vertices of edges. Moreover, Lemma 10 implies that each of those hypertrees must be a pendant path. To complete the proof, we show that there is only one such path.
LetS=v:dv≥2⊆VH′, and u,v∈S. Suppose that a path Pp=v1=v,…,vp is attached to v and Pq=u1=u,…,uq is attached to u. Let H∗ be the hypergraph obtained by deleting the edge eu2u1 and adding the edge eu2vp, that is, H∗ is obtained by removing Pq and extending Pp to Pp+q−1. To complete the proof, we need to show that ρH>ρH∗.
Letρ=ρH∗ and x be a positive eigenvector of H∗ to ρ. Write x1,…,xp+q−1 for the entries of x corresponding to v1,…,vp,u2,…,uq, and let γ be defined by (2). Now, if xu≥γ−1xv, then Theorem 1 implies that xu≥γ−1x1>x2≥xp, and so Lemma 4 implies that ρH>ρH∗. Thus, we focus on showing that xu≥γ−1xv.
Since the eigenequation foru is (46)ρxuk−1=∑i∈S\uxeiu\u<−xuk−1+∑i∈Sxeiu\u.
Hence,(47)ρ+1xuk−1<∑i∈Sxeiu\u.
Likewise, for anyw∈S\u,v, the eigenequation for w gives(48)ρ+1xwk−1>∑i∈Sxeiuu.
In particular, we see thatxw>xu for any w∈S\u,v, since ρ+1>0.
Returning to the eigenequation foru, we find that(49)ρxuk−1=∑i∈S\uxeiuu,≥xe1u\u+ω−2xuk−1.
According to Theorem1, (50)ρ−ω+2xu≥x1.
Assuming for a contradiction thatxu<γ−1x1, after some algebra, we get(51)ρ−ω+2>γ=ρ+ρ2−42,and therefore,(52)ρ−2ω+4>ρ2−4.
It is known thatρ<ΔH∗=ω, since H∗ is not a ω-regular hypergraph. Hence,(53)ω−2ω+4>0,which is a contradiction if ω≥4. If ω=3, inequality (51) becomes(54)ρ−2>ρ2−4.
Squaring both sides of this inequality, we get(55)ρ2−4ρ+4>ρ2−4,and so(56)8>4ρ.
Therefore,ρ<2, an obvious contradiction, and this completes the proof of Theorem 3.Remark 2.
From the above result, whenk = 2, the result of Lemma 2 is obvious [23].


## 3.1. The Spectral Radii of Uniform Hypergraphs with Fixed Number of Vertices and Diameter

LetH be a k-uniform hypergraph containing a path P as a sub-hypergraph (see Figure 3). We say that P is a pendant path if one of its ends is a cut vertex of H; we call this vertex the root of P. Note that a hypergraph can have multiple pendant paths, which may share roots; e.g., the hypergraph ℬp,q,s has two pendant paths.Figure 3
H.From Figure3, we see that if H′ is a k-uniform hypergraph and H is a k-uniform hypergraph with a pendant path P and ρH=ρ≥2, then the distribution of the entries of an eigenvector to ρ along P is well determined.In fact, letP=u1,…,ui,…,ui+k−1 be a pendant path in H with root u1. Let x1,…,xi,…,xi+k−1i∈ℕ be the entries of a positive unit eigenvector to ρH corresponding to u1,…,ui,…,ui+k−1i=nk−1+1,n∈ℕ. The eigenequation of AH for xj1≤j≤i+k−1 is(8)ρxik−1=xi−k+1xi−k+2,…,xi−1+xi+1xi+2,…,xi+k−1,which implies that(9)xi−k+1xi−k+2,…,xi−1−ρxik−1+xi+1xi+2,…,xi+k−1=0,xi−k+1xi−k+2,…,xi−1xi+1xi+2,…,xi+k−1−ρxik−1xi+1xi+2,…,xi+k−1+1=0,xi−k+1xi−k+2,…,xi−1xik−1⋅xik−1xi+1xi+2,…,xi+k−1−ρxik−1xi+1xi+2,…,xi+k−1+1=0.The above equation is equivalent to the following crucial equation:(10)X2−ρX+1=0.We can writeγ for the root of (10):(11)γ≔ρ+ρ2−42,and note that γ is real since ρ≥2; moreover, γ≥1, with strict inequality if ρ>2. Note also that the other root (10) is equal to γ−1.By equations (10) and (11), we can obtain the following theorem.Theorem 1.
LetH be a k-uniform hypergraph with ρ≔ρH≥2. Let P=u1,…,ui,…,ui+k−1 be a pendant path in H with root u1. Let x1,…,xi,…,xi+k−1,i=nkn∈ℕ be the entries of a positive unit eigenvector to ρH corresponding to u1,…,ui,…,ui+k−1,i=nk−1+1,n∈ℕ. If γ is defined by (11), then for every xj1≤j≤i+k−1, we have(12)xi−k+1>γxi−k+2,xi−k+1>γxi,i=nk−1+1,n∈ℕ.Proof.
The eigenequation ofAH for xji+1≤j≤i+k−1 is(13)ρxi+k−1k−1=xixi+1,…,xi+k−2,ρxi+k−2k−1=xixi+1,…,xi+k−3xi+k−1,…ρxi+1k−1=xixi+2,…,xi+k−1.
Sinceρ>γ, then(14)xixi+1,…,xi+k−2>γxi+k−1k−1,xixi+1,…,xi+k−3xi+k−1>γxi+k−2k−1,…xixi+2…xi+k−1>γxi+1k−1.
By multiplying the abovek−1 inequalities, we have(15)xik−1xi+1k−2,…,xi+k−1k−2>γk−1xi+1k−1xi+2k−1,…,xi+k−1k−1.
So, we have(16)xik−1>γk−1xi+1xi+2,…,xi+k−1.
By Lemma8, we have(17)xi+1=xi+2=⋯=xi+k−2=xi+k−1.
Thus,(18)xi>γxi+1,(19)xi>γxi+k−1.
Proceeding by induction, from the eigenequation ofAH for xji−k+2≤j≤i and the induction assumption, we get(20)ρxik−1=xi−k+1xi−k+2,…,xi−1+xi+1xi+2,…,xi+k−1,ρxi−1k−1=xi−k+1xi−k+2,…,xi−2xi,ρxi−2k−1=xi−k+1xi−k+2,…,xi−3xi−1xi,…ρxi−k+2k−1=xi−k+1xi−k+3,…,xi−1xi.
Thus,(21)ρxik−1≤γ−1k−1xik−1+xi−k+1xi−k+2,…,xi−1,xi−k+1xi−k+2,…,xi−1≥ρ−r−1k−1xik−1>γxik−1,xi−k+1xi−k+2,…,xi−2xi>γxi−1k−1,…xi−k+1xi−k+3,…,xi−1xi>γxi−k+2k−1.
By multiplying the abovek−1 inequalities, we have(22)xi−k+1k−1xi−k+2k−2,…,xik−2>γk−1xik−1xi−1k−1,…,xi−k+2k−1.
So, we get(23)xi−k+1k−1>γk−1xi−k+2xi−k+3,…,xi.
Suppose(24)xi−k+1<γxi−k+2,(25)xi−k+1<γxi.
Substituting equation (24) into equation (23), we obtain(26)xi−k+1k−1>γxi−k+1k−2xi,xi−k+1>γxi,which contradicts equation (25). Hence,(27)xi−k+1>γxi−k+2,(28)xi−k+1>γxi.
The proof is completed.Corollary 1.
Given the hypotheses of Theorem1., we have(29)x1>xk>x2k−1>⋯.Lemma 10.
Letp and q+r be fixed positive integers; then,(30)ρℬp,q,r<ρℬp,q+r/2,q+r/2.Proof.
According to the definition ofℬp,q,r, we must have an internal path with 2 lengths in the k-uniform hypergraph Bp,q,r. Without loss of generality, we assume q≥r≥1. By Lemma 6, we have(31)ρℬp,q,r<ρℬp,q+1,r−1,forq−r+1≥2.
Continuing this operation, whenp and q+r are fixed, we have(32)ρℬp,q,r<ρℬp,q+r/2,q+r/2.Theorem 2.
LetH be a k-uniform hypergraph of order n with diamH≥r. If r=1, then ρH=ρKnk. If r≥2, then(33)ρH≤ρℬn−r−2k−1,r/2,r/2,holds if and only if H≅ℬn−r−2k−1,r/2,r/2.Proof.
The statement is clear ifr=1, for Knk is the only hypergraph of order n and diameter 1. Suppose that r≥2; let H be a hypergraph with maximal spectral radius among all k-uniform hypergraphs of order n and diamH≥r. This choice implies that H is edge-maximal, that is, no edge can be added to H without diminishing its diameter. According to Lemma 9, we only need to show that H=ℬn−r−2k−1,p,r−p for some p, satisfying 1≤p≤r−1.
Letρ≔ρH and u,v be vertices of H at distance exactly r, for every i=0,…,r. Let Vi be the set of the vertices at distance i from u, and degrees of these vertices are greater than 2. Since H is edge-maximal, the set Vi∪Vi+1 induces a linear complete hypergraph, for every i=0,…,r−1. It is also clear that V0=1; moreover, it is not hard to see that Vr=1. Indeed, assume for a contradiction that Vr≥2 and add all edges between Vr−2 and V\v. These additional edges do not diminish the distance between u and v; hence, H is not edge-maximal, contradicting its choice; therefore, Vr=1.
Furthermore, by Lemma3, we have(34)ΔH≥ρH>ρℬn−r−2k−1,r/2,r/2>ρKn−r−2k−1−e,>δKn−r−2k−1−e≥Cn−1−r−2k−1k−1−1,and so ΔH≥Cn−1−r−2k−1k−1. Suppose that w is vertex of maximum degree in H, and let w∈Vi. Clearly, 0<i<r, and in view of(35)dw≤CVi−1+Vi+Vi+1k−1−1k−1,we find that(36)CVi−1+Vi+Vi+1k−1−1k−1=Cn−∑j<i−1Vj−∑j>i+1Vjk−1−1k−1,=Cn−1−r+1−3k−1k−1=Cn−1−r−2k−1k−1.
Hence, ifj<i−1 or j>i+1, then Vi=1; furthermore,(37)Vi−1+Vi+Vi+1k−1=n−r−2k−1.
IfVi−1=Vi+1=1, then obviously H=ℬn−r−2k−1,i,r−i, so Theorem 2 is proved in this case. Next we will show that all other cases lead to contradictions, by constructing a hypergraph H∗ of order n and diamH∗=r with ρH∗>ρ. Suppose that x:=x1,…,xn is a positive unit vector to ρH.
First, consider the caseVi−1=1 and Vi+1≥2. If Vi=1, the proof is completed. So, we suppose that Vi≥2. Let Vi−1=a,Vi+2=b, and suppose by symmetry that xb≥xa. Choose a vertex w∈Vi, obtain H′ from H, delete the edge ewa, and add the edge ewb. In other words, H′ is obtained by moving the vertex w from Vi into Vi+1. By symmetry and Lemma 8, xw′=xw for any w′∈Vi; thus, the choice of H implies that(38)0≥ρH∗−ρ≥x⊤AH∗x−x⊤AHx,=k∑e∈EH∗xe−k∑e∈EHxe=2kxewb−xewa≥0,implying that ρH∗=ρH and that x is an eigenvector to ρH. However, the neighborhood of a in H∗ is a proper subset of the neighborhood of a in H, so the eigenequations for ρH∗ and ρH for the vertex a are contradictory.
The same argument disposes also of the caseVi−1≥2 and Vi+1=1; thus, to complete the proof, it remains to consider the case Vi−1≥2 and Vi+1≥2.
LetVi−2=a,c∈Vi−1,d∈Vi+1, and Vi+2=b. Our first step is to show that(39)xc≥xa.
Note that ifi≥3 and Vi−3=z, then Theorem 1 gives xz<xa. Hence, setting l:=Vi−1, the eigenequation for the vertex a implies that(40)ρxak−1=xeaz\a+lxeac\a.
According toxz<xa and Theorem 1, we have(41)ρxak−1<xak−1+lxck−1,yielding in turn(42)xcxak−1>ρ−1l.
Since(43)ρ−1≥Cn−1−r−2k−1k−1−1−1=CVi−1+Vi+Vi+1k−1−1k−1−2>CVi−1+2k−1k−1−2≥l+2−2=l,inequality (39) is proved. By symmetry, we also see that xd>xb. Suppose, again by symmetry, that xb≥xa, which yields xa≤xb≤xd. Choose a vertex w∈Vi−1, obtain H∗ from H, delete the edges ewa, and add the edges ews for all s∈Vi+1. In other words, H∗ is obtained by moving the vertex w from Vi−1 into Vi. The choice of H implies that(44)0≥ρH∗−ρ≥x⊤AH∗x−x⊤AHx,=k∑e∈EH∗xe−k∑e∈EHxe≥2kVi+1xewd−xewa≥0.
This contradiction completes the proof of Theorem2.Remark 1.
From the above result, whenk = 2, the result of Lemma 1 is obvious [22].


## 3.2. The Spectral Radii of Uniform Hypergraphs with Fixed Number of Vertices and Clique Number

Lemma 11.
Fork≥2, let H be a k-uniform hypergraph with EH≥1 and u∈VH. For p≥q≥1, if HTu is the k-uniform hypergraph obtained by identifying u with a vertex of a hypertree T of order n, then(45)ρHTu>ρHn,1u.Proof.
This can be carried out along well-known lines by applying Lemma7 to recursively flatten T until it becomes a path.Theorem 3.
IfH is a k-uniform hypergraph of order n with clique number ω≥2, then ρH≥ρPKn−ω,ω holds if and only if H≅PKn−ω,ω.Proof.
LetH be a k-uniform hypergraph with minimal spectral among all connected k-uniform hypergraphs of order n and clique number ω. If ω=2, by Lemma 5, H must be a path, as the path is the hypergraph with smallest spectral radius among connected k-uniform hypergraphs of given order. Thus, we suppose that ω≥3 and let H′ be a complete k-uniform sub-hypergraph of H of order ω.
Further,H should be edge-minimal, that is, the removal of any edge of H either makes H disconnected or its clique number diminishes. In particular, if H′′ is the hypergraph obtained by removing the edges of H′, then the components of H′′ are supertrees, and each component has exactly one vertex in common with H′. It follows that H is isomorphic to a complete k-uniform hypergraph of order ω with hypertrees attached to some of its common vertices of edges. Moreover, Lemma 10 implies that each of those hypertrees must be a pendant path. To complete the proof, we show that there is only one such path.
LetS=v:dv≥2⊆VH′, and u,v∈S. Suppose that a path Pp=v1=v,…,vp is attached to v and Pq=u1=u,…,uq is attached to u. Let H∗ be the hypergraph obtained by deleting the edge eu2u1 and adding the edge eu2vp, that is, H∗ is obtained by removing Pq and extending Pp to Pp+q−1. To complete the proof, we need to show that ρH>ρH∗.
Letρ=ρH∗ and x be a positive eigenvector of H∗ to ρ. Write x1,…,xp+q−1 for the entries of x corresponding to v1,…,vp,u2,…,uq, and let γ be defined by (2). Now, if xu≥γ−1xv, then Theorem 1 implies that xu≥γ−1x1>x2≥xp, and so Lemma 4 implies that ρH>ρH∗. Thus, we focus on showing that xu≥γ−1xv.
Since the eigenequation foru is (46)ρxuk−1=∑i∈S\uxeiu\u<−xuk−1+∑i∈Sxeiu\u.
Hence,(47)ρ+1xuk−1<∑i∈Sxeiu\u.
Likewise, for anyw∈S\u,v, the eigenequation for w gives(48)ρ+1xwk−1>∑i∈Sxeiuu.
In particular, we see thatxw>xu for any w∈S\u,v, since ρ+1>0.
Returning to the eigenequation foru, we find that(49)ρxuk−1=∑i∈S\uxeiuu,≥xe1u\u+ω−2xuk−1.
According to Theorem1, (50)ρ−ω+2xu≥x1.
Assuming for a contradiction thatxu<γ−1x1, after some algebra, we get(51)ρ−ω+2>γ=ρ+ρ2−42,and therefore,(52)ρ−2ω+4>ρ2−4.
It is known thatρ<ΔH∗=ω, since H∗ is not a ω-regular hypergraph. Hence,(53)ω−2ω+4>0,which is a contradiction if ω≥4. If ω=3, inequality (51) becomes(54)ρ−2>ρ2−4.
Squaring both sides of this inequality, we get(55)ρ2−4ρ+4>ρ2−4,and so(56)8>4ρ.
Therefore,ρ<2, an obvious contradiction, and this completes the proof of Theorem 3.Remark 2.
From the above result, whenk = 2, the result of Lemma 2 is obvious [23].



---

*Source: 5805239-2021-09-10.xml*