WorksMathematics
Maximum signless Laplacian spectral radius of graphs with given minimum degree and edge connectivity
Abstract
Let be a simple connected graph of order with minimum degree and edge connectivity . 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 with minimum degree and edge connectivity when and , and proposed the corresponding problem for . In this paper, we solve the problem for the entire range and completely remove the order restriction. Specifically, we prove that with equality if and only if , where is the graph obtained from by adding edges joining a single vertex of to distinct vertices of .
AMS Mathematics Subject Classification: 05C50, 05C40, 05C35.
Introduction and Preliminaries
Introduction
Throughout this paper, all graphs are finite, simple and undirected. For a graph , let and denote its adjacency matrix and diagonal degree matrix, respectively. The signless Laplacian matrix of is defined as
and its largest eigenvalue, denoted by , is called the signless Laplacian spectral radius or the -index of . 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 of a connected graph is the minimum number of edges whose deletion disconnects . The fundamental relation , where is the minimum degree, makes it natural to ask how the -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 , , with , let be the graph obtained from by choosing a vertex and adding edges from to distinct vertices of . Recently, Zhao, Ye and Fan [8] studied the maximum -index of graphs with prescribed minimum degree and edge connectivity. Under the restrictive hypothesis , they reduced the problem for to graphs formed from and by inserting joining edges. They settled the cases and proposed the following conjecture for :
Conjecture 1.1. For , the graph is the extremal graph with maximum signless Laplacian spectral radius among all graphs of order with minimum degree and edge connectivity .
In this paper, we answer this question affirmatively and completely remove the order restriction. Furthermore, we derive the precise asymptotic expansion of the maximum -index as , 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 edges between two fixed cliques, the -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 -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 , , let be the set of edges with one endpoint in and the other in , and write . We will frequently use the following standard facts.
Lemma 1.1. Let be a connected graph and let be a spanning subgraph of . Then . If is connected, equality holds if and only if .
Proof. Every edge contributes the positive semidefinite matrix 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 have minimum degree . If and , then .
Proof. Suppose for a contradiction that . Then every vertex has at most neighbors inside , meaning it has at least neighbors outside $S. Consequently,
The function is minimized on the interval at the boundaries. For , . For , . Thus, , which contradicts the assumption.
We also require the resolvent of the signless Laplacian of a complete graph. For , , where is the all-ones matrix. Thus, whenever , the inverse can be explicitly computed using the Sherman-Morrison formula:
where
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 , and let be obtained from by adding edges between the two cliques. Then
If , equality holds if and only if the joining edges have a common endpoint in and distinct endpoints in . If , equality holds if and only if the joining edges form a star in one of the two cliques.
Proof. Write the joining edges as , where and for . Set and . Let be the matrix with columns . Then
Since is a connected proper supergraph of , we have . For , put . Define matrices and by and . Using (1), a direct calculation yields the compressed resolvent:
Since , we have . Let . Notice that
Because the joining edges are distinct, implies . It follows that for any ,
Let . For its joining edges, and . Taking a nonnegative Perron vector in (5) gives
Let and let be a Perron vector of . From (3), . With , this becomes . The matrix is positive, so its spectral radius equals one. Consequently, (6) implies . The expression on the left is strictly decreasing in and equals one at . Therefore, .
Suppose first that . Then . Since the Perron vector is strictly positive, equality in (5) is possible only when no two joining edges share their endpoint in (so ) and every two joining edges share their endpoint in (so ). Hence, the joining edges form the asserted star. When , 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 -index.
Lemma 2.2. Let and . Then
where the graph on the right has clique orders and .
Proof. For , define . For , the compressed resolvent in (4) evaluates to . It follows that is the unique solution, in , of .
If , then is a proper subgraph of , and hence . It remains to consider .
For fixed , regard and as functions of the continuous real variable . They are strictly increasing and strictly convex in the range under consideration. Indeed,
Writing , we have , and therefore
At , set and . Strict convexity and imply and . Consequently,
Since , we have . Because is strictly decreasing on , its unique root must be larger than . This proves the claim.
We can now solve the proposed problem in its full range and without any order restriction.
Theorem 2.3. Let be a graph of order , minimum degree , and edge connectivity . Then
Equality holds if and only if .
Proof. Choose such that . Put , , and , and assume without loss of generality that . Since , Lemma 1.2, applied to both sides of the cut, gives and . Thus, the existence of inherently forces .
Let be obtained from by adding all missing edges inside and inside . Then , , and has precisely the original edges between and . By Lemmas 1.1 and 2.1,
If , then , which implies . Lemma 2.2 can therefore be applied repeatedly, giving
Together with (8), this proves that equality in (7) is impossible when . Hence, equality requires and .
Equality in the first inequality of (8) forces , meaning and must already be complete graphs. Equality in the second inequality forces the cut edges to form a star centered in with distinct endpoints in . Thus, . Conversely, has order , minimum degree , and edge connectivity , and therefore attains the bound.
For the disconnected case (), the extremal graph is simply the disjoint union of two complete graphs.
Theorem 2.4. Let have order , minimum degree , and edge connectivity zero. Then
with equality if and only if .
Proof. Every component of has at least vertices. Hence, its largest component has order at most . If is a component of order , the maximum row sum bound for gives , with equality if and only if . It follows that . Equality forces a component ; the remaining vertices must induce to satisfy the minimum degree condition. The converse is immediate.
Combining Theorems 2.3 and 2.4 yields the complete solution to the problem proposed by Zhao, Ye, and Fan.
Corollary 2.5. Let have order , minimum degree , and edge connectivity . Then
and the extremal graph is unique up to isomorphism. In particular, for every , Problem 2 in [8] has an affirmative answer, with no additional restriction on .
Let and . For , an equitable partition of consists of the endpoints in , the remaining vertices of , the center vertex in , and the remaining vertices of . The corresponding quotient matrix of the signless Laplacian is
Therefore, . Equivalently, it is the unique solution of the equation:
If we set , , , and , then (11) is equivalent to the quartic polynomial equation:
The maximum -index is the largest real root of (12). For , the maximum equals .
Asymptotic Behavior of the Maximum Q-Index
In this section, we investigate the asymptotic behavior of the maximum signless Laplacian spectral radius as the order , while the minimum degree and edge connectivity are kept fixed. This provides a quantitative understanding of how the spectral radius grows with the graph order.
Recall from Section 2 that is the unique root greater than of the equation
Since the maximum degree of is , the standard row-sum bound gives . On the other hand, the graph contains as a subgraph, so . Thus, , where as . We determine the precise asymptotic expansion of .
Theorem 3.1. For fixed and , the maximum signless Laplacian spectral radius satisfies
as .
Proof. Substitute into (13). The first three terms on the right-hand side can be expanded in powers of as follows:
Summing these three terms yields
where . Let denote the fourth term in (13). Then (13) is equivalent to
On the other hand, the fourth term is explicitly given by
Equating (16) and (17) and solving for , we obtain
Assume an expansion of the form . Substituting this into the left-hand side of (18) gives
Matching the coefficients of and in (18) and (19), we immediately find
and
Substituting and back into the expansion for yields the desired result.
Remark 3.2. The asymptotic expansion (14) reveals that the maximum -index is overwhelmingly dominated by the largest clique , which contributes the leading term . The structural parameters and only manifest in the lower-order correction terms and . Interestingly, the first-order correction depends linearly on the edge connectivity , but is completely independent of the minimum degree . The minimum degree only begins to influence the spectral radius at the second order .
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 is the unique extremal graph for all admissible parameters , successfully removing the restrictive quadratic order condition 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 .
Furthermore, we established the precise asymptotic expansion of the maximum -index as the graph order . This quantitative analysis revealed a striking hierarchy in how the structural parameters influence the spectral radius at large orders: the edge connectivity governs the first-order correction term , whereas the minimum degree only manifests in the second-order correction term .
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]A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Springer, New York, 2012.
- [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]D. Cvetković, P. Rowlinson and S. K. Simić, Signless Laplacians of finite graphs, Linear Algebra Appl. 423(2–3) (2007), 155–171.DOI
- [4]D. Cvetković, P. Rowlinson and S. K. Simić, Signless Laplacians of Finite Graphs: Linear Algebraic Aspects, Cambridge University Press, Cambridge, 2010.
- [5]K. C. Das, The largest signless Laplacian eigenvalue of a graph, Linear Algebra Appl. 389 (2004), 147–155.
- [6]R. Guo, The spectral radius of graphs with given edge connectivity, Linear Algebra Appl. 429(1) (2008), 144–151.
- [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