betaFeedback

WorksMathematics

Maximum signless Laplacian spectral radius of graphs with given minimum degree and edge connectivity

Abstract

Let GG be a simple connected graph of order nn with minimum degree δδ and edge connectivity kk. Recently, in [Linear Algebra Appl. 751 (2026) 318-330], Zhao, Ye, and Fan characterized the extremal graph with maximum signless Laplacian spectral radius among all graphs of order nn with minimum degree δδ and edge connectivity kk when n≥δ2+4δ+3n \geq δ^2+4δ+3 and k∈{0,1,2}k \in \{0,1,2\}, and proposed the corresponding problem for 3≤k≤δ−13 \leq k \leq δ-1. In this paper, we solve the problem for the entire range 0≤k≤δ−10 \leq k \leq δ-1 and completely remove the order restriction. Specifically, we prove that q(G)≤q(Bn,n−δ−1k), q(G) \leq q(B_{n,n-δ-1}^{k}), with equality if and only if G≅Bn,n−δ−1kG \cong B_{n,n-δ-1}^{k}, where Bn,n−δ−1kB_{n,n-δ-1}^{k} is the graph obtained from Kn−δ−1∪Kδ+1K_{n-δ-1} \cup K_{δ+1} by adding kk edges joining a single vertex of Kn−δ−1K_{n-δ-1} to kk distinct vertices of Kδ+1K_{δ+1}.

AMS Mathematics Subject Classification: 05C50, 05C40, 05C35.

Introduction and Preliminaries

Introduction

Throughout this paper, all graphs are finite, simple and undirected. For a graph GG, let A(G)A(G) and D(G)D(G) denote its adjacency matrix and diagonal degree matrix, respectively. The signless Laplacian matrix of GG is defined as

Q(G)=D(G)+A(G),Q(G) = D(G) + A(G),

and its largest eigenvalue, denoted by q(G)q(G), is called the signless Laplacian spectral radius or the QQ-index of GG. The spectral properties of the signless Laplacian have been extensively studied; see, for instance, the foundational works [3, 5] and the comprehensive monographs [1, 4, 2].

The edge connectivity κ′(G)\kappa'(G) of a connected graph GG is the minimum number of edges whose deletion disconnects GG. The fundamental relation κ′(G)≤δ(G)\kappa'(G) \le\delta(G), where δ(G)\delta(G) is the minimum degree, makes it natural to ask how the QQ-index behaves when the minimum degree and edge connectivity are prescribed. This belongs to a broad class of extremal spectral problems in which a structural parameter is controlled by the largest eigenvalue of a graph matrix. For related results on the adjacency spectral radius and edge connectivity, we refer to [6]. For positive integers nn, bb, kk with k≤n−bk \le n-b, let Bn,bkB_{n,b}^{k} be the graph obtained from Kb∪Kn−bK_b \cup K_{n-b} by choosing a vertex v∈V(Kb)v \in V(K_b) and adding kk edges from vv to kk distinct vertices of Kn−bK_{n-b}. Recently, Zhao, Ye and Fan [8] studied the maximum QQ-index of graphs with prescribed minimum degree and edge connectivity. Under the restrictive hypothesis n≥δ2+4δ+3n \ge\delta^2 + 4\delta+ 3, they reduced the problem for 0≤k≤δ−10 \le k \le\delta- 1 to graphs formed from Kδ+1K_{\delta+1} and Kn−δ−1K_{n-\delta-1} by inserting kk joining edges. They settled the cases k∈{0,1,2}k \in\{0,1,2\} and proposed the following conjecture for 3≤k≤δ−13 \le k \le\delta- 1:

Conjecture 1.1. For 3≤k≤δ−13 \le k \le\delta- 1, the graph Bn,n−δ−1kB_{n,n-\delta-1}^{k} is the extremal graph with maximum signless Laplacian spectral radius among all graphs of order nn with minimum degree δ\delta and edge connectivity kk.

In this paper, we answer this question affirmatively and completely remove the order restriction. Furthermore, we derive the precise asymptotic expansion of the maximum QQ-index as n→∞n \to\infty, revealing a striking hierarchy in how the structural parameters influence the spectral radius at large orders.

Our proof of the extremal result has two principal ingredients. First, among all graphs obtained by inserting kk edges between two fixed cliques, the QQ-index is maximized when the joining edges form a star centered in the larger clique. Second, transferring a vertex from the smaller clique to the larger clique strictly increases the QQ-index of this extremal graph. These facts, combined with a minimum-edge-cut argument, yield the complete structural result. The asymptotic analysis is then carried out by expanding the exact characteristic equation of the extremal graph.

Preliminaries

For disjoint sets SS, T⊆V(G)T \subseteq V(G), let EG(S,T)E_G(S,T) be the set of edges with one endpoint in SS and the other in TT, and write eG(S,T)=∣EG(S,T)∣e_G(S,T) = |E_G(S,T)|. We will frequently use the following standard facts.

Lemma 1.1. Let GG be a connected graph and let HH be a spanning subgraph of GG. Then q(H)≤q(G)q(H) \le q(G). If HH is connected, equality holds if and only if H=GH = G.

Proof. Every edge uvuv contributes the positive semidefinite matrix (eu+ev)(eu+ev)T(\mathbf{e}_u+\mathbf{e}_v)(\mathbf{e}_u+\mathbf{e}_v)^{\mathsf{T}} to the signless Laplacian. The assertion follows directly from the Rayleigh principle and, in the equality case, the strict positivity of the Perron vector.

Lemma 1.2. Let GG have minimum degree δ\delta. If ∅≠S⊊V(G)\varnothing\ne S \subsetneq V(G) and eG(S,V(G)∖S)≤δ−1e_G(S,V(G)\setminus S) \le\delta- 1, then ∣S∣≥δ+1|S| \ge\delta+ 1.

Proof. Suppose for a contradiction that ∣S∣≤δ|S| \le\delta. Then every vertex u∈Su \in S has at most ∣S∣−1|S|-1 neighbors inside SS, meaning it has at least δ−∣S∣+1\delta-|S|+1 neighbors outside $S. Consequently,

eG(S,V(G)∖S)≥∣S∣(δ−∣S∣+1).e_G(S,V(G)\setminus S) \ge|S|(\delta-|S|+1).

The function f(x)=x(δ−x+1)f(x)=x(\delta-x+1) is minimized on the interval [1,δ][1,\delta] at the boundaries. For x=1x=1, f(1)=δf(1)=\delta. For x=δx=\delta, f(δ)=δf(\delta)=\delta. Thus, eG(S,V(G)∖S)≥δe_G(S,V(G)\setminus S) \ge\delta, which contradicts the assumption.

We also require the resolvent of the signless Laplacian of a complete graph. For m≥1m \ge1, Q(Km)=(m−2)Im+JmQ(K_m)=(m-2)I_m+J_m, where JmJ_m is the all-ones matrix. Thus, whenever x>2m−2x>2m-2, the inverse (xIm−Q(Km))−1(xI_m-Q(K_m))^{-1} can be explicitly computed using the Sherman-Morrison formula:

(xIm−Q(Km))−1=αm(x)Im+γm(x)Jm,(1)(xI_m-Q(K_m))^{-1}=\alpha_m(x)I_m+\gamma_m(x)J_m, \tag*{(1)}

where

αm(x)=1x−m+2,γm(x)=1(x−m+2)(x−2m+2).(2)\alpha_m(x)=\frac{1}{x-m+2},\qquad\gamma_m(x)=\frac{1}{(x-m+2)(x-2m+2)}. \tag*{(2)}

Main results

In this section, we establish the structural lemmas that lead to the main extremal theorem. We first determine the optimal arrangement of a prescribed number of edges between two fixed cliques.

Lemma 2.1. Let b≥a≥k≥1b \ge a \ge k \ge1, and let HH be obtained from Ka∪KbK_a \cup K_b by adding kk edges between the two cliques. Then

q(H)≤q(Ba+b,bk).q(H) \le q(B_{a+b,b}^{k}).

If b>ab > a, equality holds if and only if the kk joining edges have a common endpoint in KbK_b and distinct endpoints in KaK_a. If a=ba=b, equality holds if and only if the joining edges form a star in one of the two cliques.

Proof. Write the joining edges as ei=uivie_i=u_iv_i, where ui∈V(Ka)u_i \in V(K_a) and vi∈V(Kb)v_i \in V(K_b) for 1≤i≤k1 \le i \le k. Set Q0=Q(Ka∪Kb)Q_0=Q(K_a \cup K_b) and zi=eui+eviz_i=\mathbf{e}_{u_i}+\mathbf{e}_{v_i}. Let ZZ be the (a+b)×k(a+b)\times k matrix with columns z1,…,zkz_1,\ldots,z_k. Then

Q(H)=Q0+ZZT.(3)Q(H)=Q_0+ZZ^{\mathsf{T}}. \tag*{(3)}

Since HH is a connected proper supergraph of KbK_b, we have q(H)>2b−2q(H)>2b-2. For x>2b−2x>2b-2, put R(x)=(xI−Q0)−1R(x)=(xI-Q_0)^{-1}. Define k×kk\times k matrices PaP_a and PbP_b by (Pa)ij=1{ui=uj}(P_a)_{ij}=\mathbf{1}_{\{u_i=u_j\}} and (Pb)ij=1{vi=vj}(P_b)_{ij}=\mathbf{1}_{\{v_i=v_j\}}. Using (1), a direct calculation yields the compressed resolvent:

ZTR(x)Z=(γa(x)+γb(x))Jk+αa(x)Pa+αb(x)Pb.(4)Z^{\mathsf{T}}R(x)Z=\left(\gamma_a(x)+\gamma_b(x)\right)J_k+\alpha_a(x)P_a+\alpha_b(x)P_b. \tag*{(4)}

Since b≥ab\ge a, we have αb(x)≥αa(x)>0\alpha_b(x)\ge\alpha_a(x)>0. Let y=(y1,…,yk)T≥0y=(y_1,\ldots,y_k)^{\mathsf{T}}\ge0. Notice that

yT(Pa−I)y=2∑i<jui=ujyiyj,y^{\mathsf{T}}(P_a-I)y=2\sum_{\substack{i<j\\u_i=u_j}}y_i y_j,
yT(J−Pb)y=2∑i<jvi≠vjyiyj.y^{\mathsf{T}}(J-P_b)y=2\sum_{\substack{i<j\\v_i\ne v_j}}y_i y_j.

Because the joining edges are distinct, ui=uju_i=u_j implies vi≠vjv_i\ne v_j. It follows that for any y≥0y\ge0,

yT(αaI+αbJ−αaPa−αbPb)y=αbyT(J−Pb)y−αayT(Pa−I)y≥0.(5)y^{\mathsf{T}}(\alpha_a I+\alpha_b J-\alpha_a P_a-\alpha_b P_b)y =\alpha_b y^{\mathsf{T}}(J-P_b)y-\alpha_a y^{\mathsf{T}}(P_a-I)y\ge0. \tag*{(5)}

Let H⋆=Ba+b,bkH^\star=B_{a+b,b}^{k}. For its joining edges, Pa⋆=IP_a^\star=I and Pb⋆=JP_b^\star=J. Taking a nonnegative Perron vector in (5) gives

ρ(ZTR(x)Z)≤ρ((Z⋆)TR(x)Z⋆).(6)\rho\left(Z^{\mathsf{T}}R(x)Z\right)\le\rho\left((Z^\star)^{\mathsf{T}}R(x)Z^\star\right). \tag*{(6)}

Let q=q(H)q=q(H) and let X>0X>0 be a Perron vector of Q(H)Q(H). From (3), (qI−Q0)X=ZZTX(qI-Q_0)X=ZZ^{\mathsf{T}}X. With y=ZTX>0y=Z^{\mathsf{T}}X>0, this becomes y=ZTR(q)Zyy=Z^{\mathsf{T}}R(q)Zy. The matrix ZTR(q)ZZ^{\mathsf{T}}R(q)Z is positive, so its spectral radius equals one. Consequently, (6) implies ρ((Z⋆)TR(q)Z⋆)≥1\rho((Z^\star)^{\mathsf{T}}R(q)Z^\star)\ge1. The expression on the left is strictly decreasing in qq and equals one at q=q(H⋆)q=q(H^\star). Therefore, q(H)≤q(H⋆)q(H)\le q(H^\star).

Suppose first that b>ab>a. Then αb(x)>αa(x)\alpha_b(x)>\alpha_a(x). Since the Perron vector is strictly positive, equality in (5) is possible only when no two joining edges share their endpoint in KaK_a (so Pa=IP_a=I) and every two joining edges share their endpoint in KbK_b (so Pb=JP_b=J). Hence, the joining edges form the asserted star. When a=ba=b, equality requires every pair of joining edges to have a common endpoint in at least one of the cliques. A pairwise intersecting family of edges in a bipartite graph is a star, completing the proof.

The next lemma shows that making the two clique orders more unequal strictly increases the extremal QQ-index.

Lemma 2.2. Let b≥ab \ge a and 1≤k≤a−21 \le k \le a - 2. Then

q(Ba+b,bk)<q(Ba+b,b+1k),q(B^k_{a+b,b}) < q(B^k_{a+b,b+1}),

where the graph on the right has clique orders a−1a - 1 and b+1b + 1.

Proof. For x>2b−2x > 2b - 2, define Φa,b(x)=αa(x)+kγa(x)+kαb(x)+kγb(x)\Phi_{a,b}(x) = \alpha_a(x) + k\gamma_a(x) + k\alpha_b(x) + k\gamma_b(x). For Ba+b,bkB^k_{a+b,b}, the compressed resolvent in (4) evaluates to αa(x)Ik+(αb(x)+γa(x)+γb(x))Jk\alpha_a(x)I_k + \left(\alpha_b(x) + \gamma_a(x) + \gamma_b(x)\right)J_k. It follows that qa,b=q(Ba+b,bk)q_{a,b} = q(B^k_{a+b,b}) is the unique solution, in x>2b−2x > 2b - 2, of Φa,b(x)=1\Phi_{a,b}(x) = 1.

If qa,b≤2bq_{a,b} \le2b, then Kb+1K_{b+1} is a proper subgraph of Ba+b,b+1kB^k_{a+b,b+1}, and hence q(Ba+b,b+1k)>2b≥qa,bq(B^k_{a+b,b+1}) > 2b \ge q_{a,b}. It remains to consider qa,b>2bq_{a,b} > 2b.

For fixed x>2bx > 2b, regard αm(x)\alpha_m(x) and γm(x)\gamma_m(x) as functions of the continuous real variable mm. They are strictly increasing and strictly convex in the range under consideration. Indeed,

∂2αm(x)∂m2=2(x+2−m)3>0.\frac{\partial^2\alpha_m(x)}{\partial m^2} = \frac{2}{(x + 2 - m)^3} > 0.

Writing c=x+2c = x + 2, we have γm(x)=2c(c−2m)−1c(c−m)\gamma_m(x) = \frac{2}{c(c - 2m)} - \frac{1}{c(c - m)}, and therefore

∂2γm(x)∂m2=16c(c−2m)3−2c(c−m)3>0.\frac{\partial^2\gamma_m(x)}{\partial m^2} = \frac{16}{c(c - 2m)^3} - \frac{2}{c(c - m)^3} > 0.

At x=qa,bx = q_{a,b}, set Δαm=αm+1−αm\Delta\alpha_m = \alpha_{m+1} - \alpha_m and Δγm=γm+1−γm\Delta\gamma_m = \gamma_{m+1} - \gamma_m. Strict convexity and b>a−1b > a - 1 imply Δαb>Δαa−1\Delta\alpha_b > \Delta\alpha_{a-1} and Δγb>Δγa−1\Delta\gamma_b > \Delta\gamma_{a-1}. Consequently,

Φa−1,b+1(qa,b)−Φa,b(qa,b)=k(Δαb−Δαa−1)+k(Δγb−Δγa−1)>0.\Phi_{a-1,b+1}(q_{a,b}) - \Phi_{a,b}(q_{a,b}) = k(\Delta\alpha_b - \Delta\alpha_{a-1}) + k(\Delta\gamma_b - \Delta\gamma_{a-1}) > 0.

Since Φa,b(qa,b)=1\Phi_{a,b}(q_{a,b}) = 1, we have Φa−1,b+1(qa,b)>1\Phi_{a-1,b+1}(q_{a,b}) > 1. Because Φa−1,b+1\Phi_{a-1,b+1} is strictly decreasing on (2b,∞)(2b,\infty), its unique root must be larger than qa,bq_{a,b}. This proves the claim.

We can now solve the proposed problem in its full range and without any order restriction.

Theorem 2.3. Let GG be a graph of order nn, minimum degree δ\delta, and edge connectivity 1≤k≤δ−11 \le k \le\delta- 1. Then

q(G)≤q(Bn,n−δ−1k).(7)q(G) \le q(B^k_{n,n-\delta-1}). \tag*{(7)}

Equality holds if and only if G≅Bn,n−δ−1kG \cong B^k_{n,n-\delta-1}.

Proof. Choose S⊂V(G)S \subset V(G) such that eG(S,V(G)∖S)=ke_G(S,V(G) \setminus S) = k. Put T=V(G)∖ST = V(G) \setminus S, s=∣S∣s = |S|, and t=∣T∣t = |T|, and assume without loss of generality that s≤ts \le t. Since k≤δ−1k \le\delta- 1, Lemma 1.2, applied to both sides of the cut, gives s≥δ+1s \ge\delta+ 1 and t≥δ+1t \ge\delta+ 1. Thus, the existence of GG inherently forces n≥2δ+2n \ge2\delta+ 2.

Let HH be obtained from GG by adding all missing edges inside SS and inside TT. Then H[S]≅KsH[S] \cong K_s, H[T]≅KtH[T] \cong K_t, and HH has precisely the original kk edges between SS and TT. By Lemmas 1.1 and 2.1,

q(G)≤q(H)≤q(Bn,tk).(8)q(G) \le q(H) \le q(B^k_{n,t}). \tag*{(8)}

If s>δ+1s > \delta+ 1, then s≥δ+2s \ge\delta+ 2, which implies k≤δ−1≤s−3<s−2k \le\delta- 1 \le s - 3 < s - 2. Lemma 2.2 can therefore be applied repeatedly, giving

q(Bn,tk)<q(Bn,t+1k)<⋯<q(Bn,n−δ−1k).(9)q(B^k_{n,t}) < q(B^k_{n,t+1}) < \cdots< q(B^k_{n,n-\delta-1}). \tag*{(9)}

Together with (8), this proves that equality in (7) is impossible when s>δ+1s > \delta+ 1. Hence, equality requires s=δ+1s = \delta+ 1 and t=n−δ−1t = n - \delta- 1.

Equality in the first inequality of (8) forces G=HG = H, meaning G[S]G[S] and G[T]G[T] must already be complete graphs. Equality in the second inequality forces the kk cut edges to form a star centered in KtK_t with distinct endpoints in KsK_s. Thus, G≅Bn,n−δ−1kG \cong B^k_{n,n-\delta-1}. Conversely, Bn,n−δ−1kB^k_{n,n-\delta-1} has order nn, minimum degree δ\delta, and edge connectivity kk, and therefore attains the bound.

For the disconnected case (k=0k = 0), the extremal graph is simply the disjoint union of two complete graphs.

Theorem 2.4. Let GG have order nn, minimum degree δ\delta, and edge connectivity zero. Then

q(G)≤2(n−δ−2),q(G) \le2(n-\delta-2),

with equality if and only if G≅Kδ+1∪Kn−δ−1=Bn,n−δ−10G \cong K_{\delta+1} \cup K_{n-\delta-1} = B^{0}_{n,n-\delta-1}.

Proof. Every component of GG has at least δ+1\delta+1 vertices. Hence, its largest component has order at most n−δ−1n-\delta-1. If CC is a component of order rr, the maximum row sum bound for Q(C)Q(C) gives q(C)≤2Δ(C)≤2(r−1)q(C) \le2\Delta(C) \le2(r-1), with equality if and only if C≅KrC \cong K_r. It follows that q(G)≤2(n−δ−2)q(G) \le2(n-\delta-2). Equality forces a component Kn−δ−1K_{n-\delta-1}; the remaining δ+1\delta+1 vertices must induce Kδ+1K_{\delta+1} to satisfy the minimum degree condition. The converse is immediate. □\square

Combining Theorems 2.3 and 2.4 yields the complete solution to the problem proposed by Zhao, Ye, and Fan.

Corollary 2.5. Let GG have order nn, minimum degree δ\delta, and edge connectivity 0≤k≤δ−10 \le k \le\delta-1. Then

max⁡Gq(G)=q(Bn,n−δ−1k),\max_G q(G) = q(B^{k}_{n,n-\delta-1}),

and the extremal graph is unique up to isomorphism. In particular, for every 3≤k≤δ−13 \le k \le\delta-1, Problem 2 in [8] has an affirmative answer, with no additional restriction on nn.

Let a=δ+1a=\delta+1 and b=n−δ−1b=n-\delta-1. For k≥1k \ge1, an equitable partition of Bn,bkB^{k}_{n,b} consists of the kk endpoints in KaK_a, the remaining a−ka-k vertices of KaK_a, the center vertex in KbK_b, and the remaining b−1b-1 vertices of KbK_b. The corresponding quotient matrix of the signless Laplacian is

Bn,δ,k=(δ+kδ+1−k10k2δ−k00k0n−δ+k−2n−δ−20012n−2δ−5).(10)\mathcal{B}_{n,\delta,k} = \begin{pmatrix} \delta+k & \delta+1-k & 1 & 0 \\ k & 2\delta-k & 0 & 0 \\ k & 0 & n-\delta+k-2 & n-\delta-2 \\ 0 & 0 & 1 & 2n-2\delta-5 \end{pmatrix}. \tag*{(10)}

Therefore, q(Bn,n−δ−1k)=ρ(Bn,δ,k)q(B^{k}_{n,n-\delta-1})=\rho(\mathcal{B}_{n,\delta,k}). Equivalently, it is the unique solution x>2n−2δ−4x>2n-2\delta-4 of the equation:

1=1x−δ+1+k(x−δ+1)(x−2δ)+kx−n+δ+3+k(x−n+δ+3)(x−2n+2δ+4).(11)1 = \frac{1}{x-\delta+1}+\frac{k}{(x-\delta+1)(x-2\delta)}+\frac{k}{x-n+\delta+3}+\frac{k}{(x-n+\delta+3)(x-2n+2\delta+4)}. \tag*{(11)}

If we set A=x−δ+1A=x-\delta+1, B=x−2δB=x-2\delta, C=x−n+δ+3C=x-n+\delta+3, and D=x−2n+2δ+4D=x-2n+2\delta+4, then (11) is equivalent to the quartic polynomial equation:

ABCD−BCD−kCD−kABD−kAB=0.(12)ABCD-BCD-kCD-kABD-kAB=0. \tag*{(12)}

The maximum QQ-index is the largest real root of (12). For k=0k=0, the maximum equals 2(n−δ−2)2(n-\delta-2).

Asymptotic Behavior of the Maximum Q-Index

In this section, we investigate the asymptotic behavior of the maximum signless Laplacian spectral radius qn=q(Bn,n−δ−1k)q_n=q(B^{k}_{n,n-\delta-1}) as the order n→∞n\to\infty, while the minimum degree δ\delta and edge connectivity kk are kept fixed. This provides a quantitative understanding of how the spectral radius grows with the graph order.

Recall from Section 2 that qnq_n is the unique root greater than 2n−2δ−42n-2\delta-4 of the equation

1=1x−δ+1+k(x−δ+1)(x−2δ)+kx−n+δ+3+k(x−n+δ+3)(x−2n+2δ+4).(13)1=\frac{1}{x-\delta+1}+\frac{k}{(x-\delta+1)(x-2\delta)}+\frac{k}{x-n+\delta+3}+\frac{k}{(x-n+\delta+3)(x-2n+2\delta+4)}. \tag*{(13)}

Since the maximum degree of Bn,n−δ−1kB^k_{n,n-\delta-1} is n−δ−2+kn-\delta-2+k, the standard row-sum bound gives qn≤2(n−δ−2+k)q_n\leq2(n-\delta-2+k). On the other hand, the graph contains Kn−δ−1K_{n-\delta-1} as a subgraph, so qn>2(n−δ−2)q_n>2(n-\delta-2). Thus, qn=2n−2δ−4+ϵnq_n=2n-2\delta-4+\epsilon_n, where ϵn→0\epsilon_n\to0 as n→∞n\to\infty. We determine the precise asymptotic expansion of ϵn\epsilon_n.

Theorem 3.1. For fixed δ≥1\delta\geq1 and 1≤k≤δ−11\leq k\leq\delta-1, the maximum signless Laplacian spectral radius satisfies

q(Bn,n−δ−1k)=2n−2δ−4+kn+k(δ+k+32)n2+O(1n3)(14)q(B^k_{n,n-\delta-1})=2n-2\delta-4+\frac{k}{n}+\frac{k\left(\delta+k+\frac{3}{2}\right)}{n^2}+O\left(\frac{1}{n^3}\right) \tag*{(14)}

as n→∞n\to\infty.

Proof. Substitute x=2n−2δ−4+ϵx=2n-2\delta-4+\epsilon into (13). The first three terms on the right-hand side can be expanded in powers of 1/n1/n as follows:

1x−δ+1=12n−3δ−3+ϵ=12n+3δ+34n2+O(n−3),\frac{1}{x-\delta+1}=\frac{1}{2n-3\delta-3+\epsilon}=\frac{1}{2n}+\frac{3\delta+3}{4n^2}+O(n^{-3}),
k(x−δ+1)(x−2δ)=k4n2+O(n−3),\frac{k}{(x-\delta+1)(x-2\delta)}=\frac{k}{4n^2}+O(n^{-3}),
kx−n+δ+3=kn−δ−1+ϵ=kn+k(δ+1)n2+O(n−3).\frac{k}{x-n+\delta+3}=\frac{k}{n-\delta-1+\epsilon}=\frac{k}{n}+\frac{k(\delta+1)}{n^2}+O(n^{-3}).

Summing these three terms yields

Σ1=kn+12n+k(δ+1)+3δ+34+k4n2+O(n−3)=2k+12n+C1n2+O(n−3),(15)\Sigma_1=\frac{k}{n}+\frac{1}{2n}+\frac{k(\delta+1)+\frac{3\delta+3}{4}+\frac{k}{4}}{n^2}+O(n^{-3})=\frac{2k+1}{2n}+\frac{C_1}{n^2}+O(n^{-3}), \tag*{(15)}

where C1=k(δ+1)+3δ+3+k4C_1=k(\delta+1)+\frac{3\delta+3+k}{4}. Let Σ2\Sigma_2 denote the fourth term in (13). Then (13) is equivalent to

Σ2=1−Σ1=1−2k+12n−C1n2+O(n−3).(16)\Sigma_2=1-\Sigma_1=1-\frac{2k+1}{2n}-\frac{C_1}{n^2}+O(n^{-3}). \tag*{(16)}

On the other hand, the fourth term is explicitly given by

Σ2=k(n−δ−1+ϵ)ϵ.(17)\Sigma_2=\frac{k}{(n-\delta-1+\epsilon)\epsilon}. \tag*{(17)}

Equating (16) and (17) and solving for ϵ\epsilon, we obtain

ϵ(n−δ−1+ϵ)=k(1−2k+12n−C1n2+O(n−3))−1=k+k(2k+1)2n+O(n−2).(18)\epsilon(n-\delta-1+\epsilon)=k\left(1-\frac{2k+1}{2n}-\frac{C_1}{n^2}+O(n^{-3})\right)^{-1}=k+\frac{k(2k+1)}{2n}+O(n^{-2}). \tag*{(18)}

Assume an expansion of the form ϵ=c1n+c2n2+O(n−3)\epsilon=\frac{c_1}{n}+\frac{c_2}{n^2}+O(n^{-3}). Substituting this into the left-hand side of (18) gives

ϵ(n−δ−1+ϵ)=(c1n+c2n2)(n−δ−1+c1n)=c1+c2−c1(δ+1)n+O(n−2).(19)\epsilon(n-\delta-1+\epsilon)=\left(\frac{c_1}{n}+\frac{c_2}{n^2}\right)\left(n-\delta-1+\frac{c_1}{n}\right)=c_1+\frac{c_2-c_1(\delta+1)}{n}+O(n^{-2}). \tag*{(19)}

Matching the coefficients of n0n^0 and n−1n^{-1} in (18) and (19), we immediately find

c1=k,(20)c_1=k, \tag*{(20)}

and

c2−k(δ+1)=k(2k+1)2⟹c2=k(δ+1)+k2+k2=k(δ+k+32).(21)c_2-k(\delta+1)=\frac{k(2k+1)}{2}\Longrightarrow c_2=k(\delta+1)+k^2+\frac{k}{2}=k\left(\delta+k+\frac{3}{2}\right). \tag*{(21)}

Substituting c1c_1 and c2c_2 back into the expansion for ϵ\epsilon yields the desired result.

Remark 3.2. The asymptotic expansion (14) reveals that the maximum QQ-index is overwhelmingly dominated by the largest clique Kn−δ−1K_{n-\delta-1}, which contributes the leading term 2n−2δ−42n-2\delta-4. The structural parameters δ\delta and kk only manifest in the lower-order correction terms O(1/n)O(1/n) and O(1/n2)O(1/n^2). Interestingly, the first-order correction k/nk/n depends linearly on the edge connectivity kk, but is completely independent of the minimum degree δ\delta. The minimum degree δ\delta only begins to influence the spectral radius at the second order O(1/n2)O(1/n^2).

Conclusion

In this paper, we completely resolved the extremal problem for the signless Laplacian spectral radius of graphs with prescribed minimum degree and edge connectivity. We proved that the graph Bn,n−δ−1kB^k_{n,n-\delta-1} is the unique extremal graph for all admissible parameters 0≤k≤δ−10 \le k \le\delta-1, successfully removing the restrictive quadratic order condition n≥δ2+4δ+3n \ge\delta^2+4\delta+3 that was required in previous literature. The methodology developed herein highlights the power of combining resolvent representations with structural transformations. By completing the two sides of a minimum edge cut to form cliques, we created an upper comparison graph. The resolvent comparison then elegantly optimized the placement of the cut edges, and the strict convexity of the resolvent components drove the clique-transfer lemma, which forced one side of the cut to collapse to the smallest possible order δ+1\delta+1.

Furthermore, we established the precise asymptotic expansion of the maximum QQ-index as the graph order n→∞n \to\infty. This quantitative analysis revealed a striking hierarchy in how the structural parameters influence the spectral radius at large orders: the edge connectivity kk governs the first-order correction term O(1/n)O(1/n), whereas the minimum degree δ\delta only manifests in the second-order correction term O(1/n2)O(1/n^2).

These algebraic and structural transformations identify the unique extremal graph and its spectral behavior for every admissible parameter set without relying on tedious case analyses. Future research directions include extending this resolvent-based clique-transfer technique and asymptotic analysis to other graph matrices, such as the standard Laplacian or adjacency matrices, and applying similar principles to other connectivity measures, such as vertex connectivity or restricted edge connectivity.

References

  1. [1]A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Springer, New York, 2012.
  2. [2]S. M. Cioabă, D. A. Gregory and W. H. Haemers, Eigenvalue problems for the signless Laplacian, Linear Algebra Appl. 452 (2014), 25–38.
  3. [3]D. Cvetković, P. Rowlinson and S. K. Simić, Signless Laplacians of finite graphs, Linear Algebra Appl. 423(2–3) (2007), 155–171.DOI
  4. [4]D. Cvetković, P. Rowlinson and S. K. Simić, Signless Laplacians of Finite Graphs: Linear Algebraic Aspects, Cambridge University Press, Cambridge, 2010.
  5. [5]K. C. Das, The largest signless Laplacian eigenvalue of a graph, Linear Algebra Appl. 389 (2004), 147–155.
  6. [6]R. Guo, The spectral radius of graphs with given edge connectivity, Linear Algebra Appl. 429(1) (2008), 144–151.
  7. [8]Y. Zhao, H. Ye and D. Fan, Connectivity, spanning tree packing number and signless Laplacian spectral radius, Linear Algebra Appl. (2026), doi:10.1016/j.laa.2026.09.002.DOI

Paper details

vlnc:W_4mp8dmet
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents