betaFeedback

WorksMathematics

Maxima of the Q-index: Forbidden an odd wheel

Abstract

In 2013, Freitas, Nikiforov and Patuzzi (EJLA, 2013) proposed the problem of determining the maximum signless Laplacian spectral radius of an nn-vertex FF-free graph. Recently, Yuan, Zhai and Zhang (LAA, 2026) determined the maximum signless Laplacian spectral radius of graphs without wheels of sufficiently large order. In this paper, we consider the problem of forbidding a single wheel W2k+1=K1∨C2kW_{2k+1}=K_1\vee C_{2k}. We show that, for every fixed integer k≥3k\ge 3 and sufficiently large nn, the unique extremal graph maximizing the signless Laplacian spectral radius among all nn-vertex W2k+1W_{2k+1}-free graphs is Kk∨(K2∪(n−k−2)K1)K_k\vee(K_2\cup(n-k-2)K_1).

Introduction

All graphs considered in this paper are finite and simple, and subgraph containment is not necessarily induced. For a graph G=(V(G),E(G))G=(V(G),E(G)), we call ∣V(G)∣|V(G)| the order of GG and e(G):=∣E(G)∣e(G):=|E(G)| the size of GG. Let A(G)A(G) be its adjacency matrix, D(G)D(G) the diagonal matrix of vertex degrees, and Q(G)=D(G)+A(G)Q(G)=D(G)+A(G) its signless Laplacian. The largest eigenvalue of Q(G)Q(G) is called the QQ-index of GG, denoted by q(G)q(G). For a fixed graph FF, the signless Laplacian spectral extremal problem asks for the maximum of q(G)q(G) among all nn-vertex FF-free graphs. This problem was proposed by de Freitas, Nikiforov and Patuzzi [11].

For integers s,ts,t, let KsK_s, CsC_s and PsP_s be the clique, cycle and path of order ss, respectively. Let Ks,t=sK1∨tK1K_{s,t}=sK_1\vee tK_1 be the complete bipartite graph. Let Ws+1:=K1∨CsW_{s+1}:=K_1\vee C_s be the wheel of order s+1s+1. We call a wheel an odd wheel if its order is odd. For 1≤k<n1\le k<n, let Sn,k:=Kk∨(n−k)K1S_{n,k}:=K_k\vee(n-k)K_1 be the complete split graph of order nn, and for k≤n−2k\le n-2 let Sn,k+S_{n,k}^{+} be obtained from Sn,kS_{n,k} by adding one edge to its independent set. To be more specific,

Sn,k+:=Kk∨(K2∪(n−k−2)K1).S_{n,k}^{+}:=K_k\vee\left(K_2\cup(n-k-2)K_1\right).

Several results are known for the maximum QQ-index of a graph with forbidden subgraphs, including cliques [13], paths [15], cycles [11, 18, 16], K2,tK_{2,t}’s [12], books [4], fans [17], linear forests [6, 7], vertex-disjoint cliques [5, 21, 24], intersecting odd cycles [22, 8] and so on.

For wheels, Zhao, Huang and Lin [23] proved that Sn,2S_{n,2} is the unique nn-vertex wheel-free graph with maximum QQ-index for n≥4n\ge4. Chen and Ma [2] determined the maximum QQ-index of graphs without both W5W_5 and C6C_6. Recently, Yuan, Zhai and Zhang [19] determined the maximum QQ-index of graphs without all wheels of sufficiently large order. For a fixed odd wheel, the adjacency spectral extremal problem was studied by Cioabă, Desai and Tait [9] and Zhang [20]. A related adjacency spectral problem with a fixed number of edges was considered in [3].

For general forbidden graphs, Zheng, Li and Su [26] proved a signless Laplacian spectral version of the Erdős–Stone–Simonovits theorem for graphs with chromatic number at least three. Moreover, Zheng, Li and Li [25] proved an exact signless Laplacian spectral Turán theorem for color-critical graphs with chromatic number at least four. In particular, their result determines the maximum QQ-index of graphs without a fixed even wheel. However, it does not apply to any odd wheel W2k+1W_{2k+1}.

In this paper, we determine the maximum QQ-index of nn-vertex graphs containing no W2k+1W_{2k+1} for fixed k≥3k\ge3 and sufficiently large nn.

Theorem 1.1. For every fixed integer k≥3k\ge3, there is a constant N(k)N(k) such that, for any n≥N(k)n\ge N(k), every nn-vertex W2k+1W_{2k+1}-free graph GG satisfies q(G)≤q(Sn,k+)q(G)\le q(S_{n,k}^{+}), with equality if and only if G≅Sn,k+G\cong S_{n,k}^{+}.

The rest of the paper is arranged as follows. In Section 2, we present some preliminary results, including structural lemmas and a Schur-complement estimate. We prove the extremal result for graphs with sublinearly many large degree vertices in Section 3. Section 4 establishes a spectral stability theorem. Finally, Section 5 completes the proof of Theorem 1.1.

Preliminaries

Basic notations and estimates

Given a graph GG, a vertex v∈V(G)v\in V(G) and sets X,Y⊆V(G)X,Y\subseteq V(G). Let K[X]K[X] be the complete graph on XX and K[X,Y]K[X,Y] be the complete bipartite graph with partition set XX and YY if they are disjoint. Let G[X]=G∩K[X]G[X]=G\cap K[X] and G[X,Y]=G∩K[X,Y]G[X,Y]=G\cap K[X,Y]. Denote by e(X)e(X) the number of edges of G[X]G[X] and by e(X,Y)e(X,Y) the number of edges of G[X,Y]G[X,Y]. Denote by NG(v)N_G(v) the neighborhood of vv in GG (we may write N(v)N(v) for short) and dG(v):=∣NG(v)∣d_G(v):=|N_G(v)| the degree of vv in GG. Also, NX(v):=NG(v)∩XN_X(v):=N_G(v)\cap X, dX(v):=∣NX(v)∣d_X(v):=|N_X(v)|, NX(Y):=⋃v∈YNX(v)N_X(Y):=\bigcup_{v\in Y}N_X(v) and Δ(G):=max⁡v∈GdG(v)\Delta(G):=\max_{v\in G}d_G(v).

Lemma 2.1. Let k≥3k\ge3 and n≥4kn\ge4k. The graph Sn,k+S^+_{n,k} is W2k+1W_{2k+1}-free. If qF=q(Sn,k+)q_F=q(S^+_{n,k}) and qS=q(Sn,k)q_S=q(S_{n,k}), then

n<n+2(k−1)−2k(k−1)n<qS<qF<n+2k.n<n+2(k-1)-\frac{2k(k-1)}{n}<q_S<q_F<n+2k.

Moreover, qFq_F is the largest root of

Pn,k(x)=x3−(n+3k)x2+(kn+4k2+2n−4)x−2k2(k+1).P_{n,k}(x)=x^3-(n+3k)x^2+(kn+4k^2+2n-4)x-2k^2(k+1).

Proof. A vertex outside the KkK_k-part of Sn,k+S^+_{n,k} has degree at most k+1<2kk+1<2k and cannot be a hub (i.e. the only vertex of degree 2k2k in W2k+1W_{2k+1}). For a hub in KkK_k, a 2k2k-cycle in its neighborhood would use at least k+1k+1 vertices outside the KkK_k-part and thus at least two edges outside. This is a contradiction since there is only one edge outside the KkK_k-part in Sn,k+S^+_{n,k}. The equitable signless Laplacian quotient of Sn,k+S^+_{n,k}, with the classes corresponding to the KkK_k-part, the two outside edge endpoints, and the remaining vertices, is

(n+k−22n−k−2kk+20k0k).\begin{pmatrix} n+k-2 & 2 & n-k-2 \\ k & k+2 & 0 \\ k & 0 & k \end{pmatrix}.

Its positive quotient Perron eigenvector lifts to a positive eigenvector of Q(Sn,k+)Q(S^+_{n,k}), yielding the displayed characteristic polynomial. The analogous quotient of Sn,kS_{n,k} has characteristic polynomial p(x)=x2−(n+2(k−1))x+2k(k−1)p(x)=x^2-(n+2(k-1))x+2k(k-1). As adding an outside edge strictly increases the QQ-index of the connected graph Sn,kS_{n,k}, we have qF>qSq_F>q_S. One can check that p(n)<0p(n)<0, Pn,k(n+2k)>0P_{n,k}(n+2k)>0 and Pn,kP_{n,k} is increasing on [n,+∞)[n,+\infty). Hence qS>nq_S>n and qF<n+2kq_F<n+2k. Together with p(qS)=0p(q_S)=0, we get n+2(k−1)−qS=2k(k−1)/qS<2k(k−1)/nn+2(k-1)-q_S=2k(k-1)/q_S<2k(k-1)/n. The proof is done.

References

  1. [1]J.A. Bondy, M. Simonovits, Cycles of even length in graphs, J. Combin. Theory Ser. B 16 (1974) 97–105.DOI
  2. [2]D. Chen, X. Ma, The maximum signless Laplacian spectral radius of graphs with forbidden subgraphs, Filomat 37 (2023) 8319–8330.DOI
  3. [3]H. Chen, J. Gao, S. Li, The edge spectral extremal problem for odd wheels in nonzero residue classes, arXiv:2609.13666 (2026).arxiv.org/abs/2609.13666
  4. [4]M. Chen, Y. Jin, P. Zhang, The signless Laplacian spectral radius of book-free graphs, Discrete Math. 348 (2025) 114448.DOI
  5. [5]M. Chen, Y. Jin, P. Zhang, The signless Laplacian spectral Turán problems for disjoint triangles, arXiv:2610.30859 (2026).arxiv.org/abs/2610.30859
  6. [6]M. Chen, A. Liu, X. Zhang, The signless Laplacian spectral radius of graphs with forbidding linear forests, Linear Algebra Appl. 591 (2020) 25–43.arxiv.org/abs/2007.08627
  7. [7]M. Chen, A. Liu, X. Zhang, On the Aα-spectral radius of graphs without linear forests, Appl. Math. Comput. 450 (2023) 128005.
  8. [8]M. Chen, A. Liu, X. Zhang, The signless Laplacian spectral radius of graphs without intersecting odd cycles, Electron. J. Linear Algebra 40 (2024) 370–381.arxiv.org/abs/2108.03895
  9. [9]S.M. Cioabă, D.N. Desai, M. Tait, The spectral radius of graphs with no odd wheels, European J. Combin. 99 (2022) 103420.arxiv.org/abs/2104.07729
  10. [10]L. Feng, G. Yu, On three conjectures involving the signless Laplacian spectral radius of graphs, Publ. Inst. Math. (Beograd) 85(99) (2009), 35–38.DOI
  11. [11]M.A.A. de Freitas, V. Nikiforov, L. Patuzzi, Maxima of the Q-index: Forbidden 4-cycle and 5-cycle, Electron. J. Linear Algebra 26 (2013) 905–916.
  12. [12]M.A.A. de Freitas, V. Nikiforov, L. Patuzzi, Maxima of the Q-index: Graphs with no K_{s,t}, Linear Algebra Appl. 496 (2016) 381–391.arxiv.org/abs/1507.00625
  13. [13]B. He, Y. Jin, X. Zhang, Sharp bounds for the signless Laplacian spectral radius in terms of clique number, Linear Algebra Appl. 438 (2013) 3851–3861.arxiv.org/abs/1209.3214
  14. [14]R. Merris, A note on Laplacian graph eigenvalues, Linear Algebra Appl. 285 (1998) 33–35.DOI
  15. [15]V. Nikiforov, X. Yuan, Maxima of the Q-index: Graphs without long paths, Electron. J. Linear Algebra 27 (2014) 504–514.arxiv.org/abs/1308.4341
  16. [16]V. Nikiforov, X. Yuan, Maxima of the Q-index: Forbidden even cycles, Linear Algebra Appl. 471 (2015) 636–653.arxiv.org/abs/1410.2142
  17. [17]B. Wang, M. Zhai, Maxima of the Q-index: Forbidden a fan, Discrete Math. 346 (2023) 113264.DOI
  18. [18]X. Yuan, Maxima of the Q-index: Forbidden odd cycles, Linear Algebra Appl. 458 (2014) 207–216.DOI
  19. [19]W. Yuan, M. Zhai, Y. Zhang, Maximal Q-index: Graphs without long wheels, Linear Algebra Appl. 749 (2026) 1–14.DOI
  20. [20]W. Zhang, More results on the spectral radius of graphs with no odd wheels, Discrete Math. 348 (2025) 114550.arxiv.org/abs/2408.03595
  21. [21]Y. Zhang, L. Wang, The signless Laplacian spectral radius of 2K₃-free graphs, Discrete Math. 347 (2024) 114075.DOI
  22. [22]Y. Zhao, X. Huang, H. Guo, The signless Laplacian spectral radius of graphs with no intersecting triangles, Linear Algebra Appl. 618 (2021) 12–21.arxiv.org/abs/2009.04738
  23. [23]Y. Zhao, X. Huang, H. Lin, The maximum spectral radius of wheel-free graphs, Discrete Math. 344 (2021) 112341.arxiv.org/abs/2007.06922
  24. [24]X. Zhao, L. You, J. Zeng, The signless Laplacian spectral radius of graphs without disjoint cliques, arXiv:2606.30272 (2026).arxiv.org/abs/2606.30272
  25. [25]J. Zheng, Y. Li, H. Li, The signless Laplacian spectral Turán problems for color-critical graphs, Linear Algebra Appl. 730 (2026) 546–565.arxiv.org/abs/2504.07852
  26. [26]J. Zheng, H. Li, L. Su, A signless Laplacian spectral Erdős–Stone–Simonovits theorem, Discrete Math. 349 (2026) 114665.arxiv.org/abs/2502.11170

Paper details

vlnc:W_8pnnmm2w
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

ChatGPT (OpenAI)

View statement
Looking for related papers…
Contents