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)) G = ( V ( G ) , E ( G )) , we call ∣ V ( G ) ∣ |V(G)| ∣ V ( G ) ∣ the order of G G G and e ( G ) : = ∣ E ( G ) ∣ e(G):=|E(G)| e ( G ) := ∣ E ( G ) ∣ the size of G G G . Let A ( G ) A(G) A ( G ) be its adjacency matrix, D ( G ) D(G) D ( G ) the diagonal matrix of vertex degrees, and Q ( G ) = D ( G ) + A ( G ) Q(G)=D(G)+A(G) Q ( G ) = D ( G ) + A ( G ) its signless Laplacian. The largest eigenvalue of Q ( G ) Q(G) Q ( G ) is called the Q Q Q -index of G G G , denoted by q ( G ) q(G) q ( G ) . For a fixed graph F F F , the signless Laplacian spectral extremal problem asks for the maximum of q ( G ) q(G) q ( G ) among all n n n -vertex F F F -free graphs. This problem was proposed by de Freitas, Nikiforov and Patuzzi [11 ] .
For integers s , t s,t s , t , let K s K_s K s , C s C_s C s and P s P_s P s be the clique, cycle and path of order s s s , respectively. Let K s , t = s K 1 ∨ t K 1 K_{s,t}=sK_1\vee tK_1 K s , t = s K 1 ∨ t K 1 be the complete bipartite graph. Let W s + 1 : = K 1 ∨ C s W_{s+1}:=K_1\vee C_s W s + 1 := K 1 ∨ C s be the wheel of order s + 1 s+1 s + 1 . We call a wheel an odd wheel if its order is odd. For 1 ≤ k < n 1\le k<n 1 ≤ k < n , let S n , k : = K k ∨ ( n − k ) K 1 S_{n,k}:=K_k\vee(n-k)K_1 S n , k := K k ∨ ( n − k ) K 1 be the complete split graph of order n n n , and for k ≤ n − 2 k\le n-2 k ≤ n − 2 let S n , k + S_{n,k}^{+} S n , k + be obtained from S n , k S_{n,k} S n , k by adding one edge to its independent set. To be more specific,
S n , k + : = K k ∨ ( K 2 ∪ ( n − k − 2 ) K 1 ) . S_{n,k}^{+}:=K_k\vee\left(K_2\cup(n-k-2)K_1\right). S n , k + := K k ∨ ( K 2 ∪ ( n − k − 2 ) K 1 ) .
Several results are known for the maximum Q Q Q -index of a graph with forbidden subgraphs, including cliques [13 ] , paths [15 ] , cycles [11 , 18 , 16 ] , K 2 , t K_{2,t} K 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 S n , 2 S_{n,2} S n , 2 is the unique n n n -vertex wheel-free graph with maximum Q Q Q -index for n ≥ 4 n\ge4 n ≥ 4 . Chen and Ma [2 ] determined the maximum Q Q Q -index of graphs without both W 5 W_5 W 5 and C 6 C_6 C 6 . Recently, Yuan, Zhai and Zhang [19 ] determined the maximum Q Q Q -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 Q Q Q -index of graphs without a fixed even wheel. However, it does not apply to any odd wheel W 2 k + 1 W_{2k+1} W 2 k + 1 .
In this paper, we determine the maximum Q Q Q -index of n n n -vertex graphs containing no W 2 k + 1 W_{2k+1} W 2 k + 1 for fixed k ≥ 3 k\ge3 k ≥ 3 and sufficiently large n n n .
Theorem 1.1. For every fixed integer k ≥ 3 k\ge3 k ≥ 3 , there is a constant N ( k ) N(k) N ( k ) such that, for any n ≥ N ( k ) n\ge N(k) n ≥ N ( k ) , every n n n -vertex W 2 k + 1 W_{2k+1} W 2 k + 1 -free graph G G G satisfies q ( G ) ≤ q ( S n , k + ) q(G)\le q(S_{n,k}^{+}) q ( G ) ≤ q ( S n , k + ) , with equality if and only if G ≅ S n , k + G\cong S_{n,k}^{+} G ≅ 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 G G G , a vertex v ∈ V ( G ) v\in V(G) v ∈ V ( G ) and sets X , Y ⊆ V ( G ) X,Y\subseteq V(G) X , Y ⊆ V ( G ) . Let K [ X ] K[X] K [ X ] be the complete graph on X X X and K [ X , Y ] K[X,Y] K [ X , Y ] be the complete bipartite graph with partition set X X X and Y Y Y if they are disjoint. Let G [ X ] = G ∩ K [ X ] G[X]=G\cap K[X] G [ X ] = G ∩ K [ X ] and G [ X , Y ] = G ∩ K [ X , Y ] G[X,Y]=G\cap K[X,Y] G [ X , Y ] = G ∩ K [ X , Y ] . Denote by e ( X ) e(X) e ( X ) the number of edges of G [ X ] G[X] G [ X ] and by e ( X , Y ) e(X,Y) e ( X , Y ) the number of edges of G [ X , Y ] G[X,Y] G [ X , Y ] . Denote by N G ( v ) N_G(v) N G ( v ) the neighborhood of v v v in G G G (we may write N ( v ) N(v) N ( v ) for short) and d G ( v ) : = ∣ N G ( v ) ∣ d_G(v):=|N_G(v)| d G ( v ) := ∣ N G ( v ) ∣ the degree of v v v in G G G . Also, N X ( v ) : = N G ( v ) ∩ X N_X(v):=N_G(v)\cap X N X ( v ) := N G ( v ) ∩ X , d X ( v ) : = ∣ N X ( v ) ∣ d_X(v):=|N_X(v)| d X ( v ) := ∣ N X ( v ) ∣ , N X ( Y ) : = ⋃ v ∈ Y N X ( v ) N_X(Y):=\bigcup_{v\in Y}N_X(v) N X ( Y ) := ⋃ v ∈ Y N X ( v ) and Δ ( G ) : = max v ∈ G d G ( v ) \Delta(G):=\max_{v\in G}d_G(v) Δ ( G ) := max v ∈ G d G ( v ) .
Lemma 2.1. Let k ≥ 3 k\ge3 k ≥ 3 and n ≥ 4 k n\ge4k n ≥ 4 k . The graph S n , k + S^+_{n,k} S n , k + is W 2 k + 1 W_{2k+1} W 2 k + 1 -free. If q F = q ( S n , k + ) q_F=q(S^+_{n,k}) q F = q ( S n , k + ) and q S = q ( S n , k ) q_S=q(S_{n,k}) q S = q ( S n , k ) , then
n < n + 2 ( k − 1 ) − 2 k ( k − 1 ) n < q S < q F < n + 2 k . n<n+2(k-1)-\frac{2k(k-1)}{n}<q_S<q_F<n+2k. n < n + 2 ( k − 1 ) − n 2 k ( k − 1 ) < q S < q F < n + 2 k . Moreover, q F q_F q F is the largest root of
P n , k ( x ) = x 3 − ( n + 3 k ) x 2 + ( k n + 4 k 2 + 2 n − 4 ) x − 2 k 2 ( k + 1 ) . P_{n,k}(x)=x^3-(n+3k)x^2+(kn+4k^2+2n-4)x-2k^2(k+1). P n , k ( x ) = x 3 − ( n + 3 k ) x 2 + ( k n + 4 k 2 + 2 n − 4 ) x − 2 k 2 ( k + 1 ) . Proof. A vertex outside the K k K_k K k -part of S n , k + S^+_{n,k} S n , k + has degree at most k + 1 < 2 k k+1<2k k + 1 < 2 k and cannot be a hub (i.e. the only vertex of degree 2 k 2k 2 k in W 2 k + 1 W_{2k+1} W 2 k + 1 ). For a hub in K k K_k K k , a 2 k 2k 2 k -cycle in its neighborhood would use at least k + 1 k+1 k + 1 vertices outside the K k K_k K k -part and thus at least two edges outside. This is a contradiction since there is only one edge outside the K k K_k K k -part in S n , k + S^+_{n,k} S n , k + . The equitable signless Laplacian quotient of S n , k + S^+_{n,k} S n , k + , with the classes corresponding to the K k K_k K k -part, the two outside edge endpoints, and the remaining vertices, is
( n + k − 2 2 n − k − 2 k k + 2 0 k 0 k ) . \begin{pmatrix}
n+k-2 & 2 & n-k-2 \\
k & k+2 & 0 \\
k & 0 & k
\end{pmatrix}. n + k − 2 k k 2 k + 2 0 n − k − 2 0 k . Its positive quotient Perron eigenvector lifts to a positive eigenvector of Q ( S n , k + ) Q(S^+_{n,k}) Q ( S n , k + ) , yielding the displayed characteristic polynomial. The analogous quotient of S n , k S_{n,k} S n , k has characteristic polynomial p ( x ) = x 2 − ( n + 2 ( k − 1 ) ) x + 2 k ( k − 1 ) p(x)=x^2-(n+2(k-1))x+2k(k-1) p ( x ) = x 2 − ( n + 2 ( k − 1 )) x + 2 k ( k − 1 ) . As adding an outside edge strictly increases the Q Q Q -index of the connected graph S n , k S_{n,k} S n , k , we have q F > q S q_F>q_S q F > q S . One can check that p ( n ) < 0 p(n)<0 p ( n ) < 0 , P n , k ( n + 2 k ) > 0 P_{n,k}(n+2k)>0 P n , k ( n + 2 k ) > 0 and P n , k P_{n,k} P n , k is increasing on [ n , + ∞ ) [n,+\infty) [ n , + ∞ ) . Hence q S > n q_S>n q S > n and q F < n + 2 k q_F<n+2k q F < n + 2 k . Together with p ( q S ) = 0 p(q_S)=0 p ( q S ) = 0 , we get n + 2 ( k − 1 ) − q S = 2 k ( k − 1 ) / q S < 2 k ( k − 1 ) / n n+2(k-1)-q_S=2k(k-1)/q_S<2k(k-1)/n n + 2 ( k − 1 ) − q S = 2 k ( k − 1 ) / q S < 2 k ( k − 1 ) / n . The proof is done.
Structural lemmas
Lemma 2.2. Let k ≥ 3 k\ge3 k ≥ 3 and G G G be a W 2 k + 1 W_{2k+1} W 2 k + 1 -free graph. Pick u ∈ V ( G ) u\in V(G) u ∈ V ( G ) , S ⊆ N ( u ) S\subseteq N(u) S ⊆ N ( u ) with ∣ S ∣ = k − 1 |S|=k-1 ∣ S ∣ = k − 1 , and let T ⊆ V ( G ) ∖ ( S ∪ { u } ) T\subseteq V(G)\setminus(S\cup\{u\}) T ⊆ V ( G ) ∖ ( S ∪ { u }) be a vertex set whose vertices are adjacent to every vertex of S ∪ { u } S\cup\{u\} S ∪ { u } . then:
If ∣ T ∣ ≥ k + 1 |T| \ge k+1 ∣ T ∣ ≥ k + 1 , then e ( T ) ≤ 1 e(T) \le1 e ( T ) ≤ 1 .
if ∣ T ∣ ≥ k |T| \ge k ∣ T ∣ ≥ k , then ∣ N ( z ) ∩ T ∣ ≤ 1 |N(z) \cap T| \le1 ∣ N ( z ) ∩ T ∣ ≤ 1 holds for any z ∈ N ( u ) \ ( S ∪ T ) z \in N(u) \backslash(S \cup T) z ∈ N ( u ) \ ( S ∪ T ) .
Proof. For (1), suppose to the contrary that ∣ T ∣ ≥ k + 1 |T| \ge k+1 ∣ T ∣ ≥ k + 1 and e ( T ) ≥ 2 e(T) \ge2 e ( T ) ≥ 2 . Clearly, we have either P 3 ∪ ( k − 2 ) K 1 ⊆ G [ T ] P_3 \cup(k-2)K_1 \subseteq G[T] P 3 ∪ ( k − 2 ) K 1 ⊆ G [ T ] or 2 K 2 ∪ ( k − 3 ) K 1 ⊆ G [ T ] 2K_2 \cup(k-3)K_1 \subseteq G[T] 2 K 2 ∪ ( k − 3 ) K 1 ⊆ G [ T ] . We obtain k − 1 k-1 k − 1 vertex-disjoint paths covering k + 1 k+1 k + 1 vertices in T T T in both cases. Hence, we can use the k − 1 k-1 k − 1 vertices in S S S to connect the endpoints of these paths cyclically, forming a C 2 k C_{2k} C 2 k in G [ N ( u ) ] G[N(u)] G [ N ( u )] . This is a contradiction since G G G is W 2 k + 1 W_{2k+1} W 2 k + 1 -free.
For (2), suppose ∣ T ∣ ≥ k |T| \ge k ∣ T ∣ ≥ k and ∣ N ( z ) ∩ T ∣ ≥ 2 |N(z) \cap T| \ge2 ∣ N ( z ) ∩ T ∣ ≥ 2 for some z ∈ N ( u ) \ ( S ∪ T ) z \in N(u) \backslash(S \cup T) z ∈ N ( u ) \ ( S ∪ T ) . Clearly, we have P 3 ∪ ( k − 2 ) K 1 ⊆ G [ T ∪ { z } ] P_3 \cup(k-2)K_1 \subseteq G[T \cup\{z\}] P 3 ∪ ( k − 2 ) K 1 ⊆ G [ T ∪ { z }] and z z z is not an endpoint but the middle vertex of the P 3 P_3 P 3 . Similarly as the proof of (1), we then get a C 2 k C_{2k} C 2 k in G [ N ( u ) ] G[N(u)] G [ N ( u )] , a contradiction.
Lemma 2.3. Let G G G be a W 2 k + 1 W_{2k+1} W 2 k + 1 -free graph and A A A , B B B be disjoint vertex sets in G G G with ∣ A ∣ ≥ k |A| \ge k ∣ A ∣ ≥ k . Put M = ∑ a ∈ A ∣ B \ N ( a ) ∣ M = \sum_{a \in A} |B \backslash N(a)| M = ∑ a ∈ A ∣ B \ N ( a ) ∣ . Then
e ( B ) ≤ ( k − 1 2 + k M ∣ A ∣ ) ∣ B ∣ . e(B) \le\left(\frac{k-1}{2}+\frac{kM}{|A|}\right)|B|. e ( B ) ≤ ( 2 k − 1 + ∣ A ∣ k M ) ∣ B ∣. Proof. Let T = B ∩ ⋂ s ∈ S N ( s ) T = B \cap\bigcap_{s \in S} N(s) T = B ∩ ⋂ s ∈ S N ( s ) . By the pigeonhole principle, we can pick a set S ⊆ A S \subseteq A S ⊆ A with ∣ S ∣ = k |S| = k ∣ S ∣ = k and ∣ B \ T ∣ ≤ ∑ s ∈ S ∣ B \ N ( s ) ∣ ≤ k ∣ A ∣ M |B \backslash T| \le\sum_{s \in S}|B \backslash N(s)| \le\frac{k}{|A|}M ∣ B \ T ∣ ≤ ∑ s ∈ S ∣ B \ N ( s ) ∣ ≤ ∣ A ∣ k M . If some v ∈ T v \in T v ∈ T has k k k neighbors in G [ T ] G[T] G [ T ] , these k k k vertices alternating the k k k vertices in S S S form a C 2 k C_{2k} C 2 k in N ( v ) N(v) N ( v ) , a contradiction. Thus Δ ( G [ T ] ) ≤ k − 1 \Delta(G[T]) \le k-1 Δ ( G [ T ]) ≤ k − 1 . Therefore,
e ( B ) ≤ e ( T ) + ∣ B \ T ∣ ∣ B ∣ ≤ ( k − 1 2 + k M ∣ A ∣ ) ∣ B ∣ . e(B) \le e(T)+|B \backslash T||B| \le\left(\frac{k-1}{2}+\frac{kM}{|A|}\right)|B|. e ( B ) ≤ e ( T ) + ∣ B \ T ∣∣ B ∣ ≤ ( 2 k − 1 + ∣ A ∣ k M ) ∣ B ∣.
For an n n n -vertex graph G G G and a number x ≤ n − 1 x \le n-1 x ≤ n − 1 , let L G ( x ) = { v : d G ( v ) ≥ x } L_G(x)=\{v:d_G(v)\ge x\} L G ( x ) = { v : d G ( v ) ≥ x } . Fix 0 < ε < 1 / 2 0<\varepsilon<1/2 0 < ε < 1/2 and α = ε 2 k \alpha=\frac{\varepsilon}{2k} α = 2 k ε . Define L = L G ( ε n ) L=L_G(\varepsilon n) L = L G ( ε n ) , R = V ( G ) \ L R=V(G)\backslash L R = V ( G ) \ L , U = L G ( n − 1 − α n ) U=L_G(n-1-\alpha n) U = L G ( n − 1 − α n ) , W = L \ U W=L\backslash U W = L \ U .
Lemma 2.4. There exists N 0 = N 0 ( k , ε ) N_0=N_0(k,\varepsilon) N 0 = N 0 ( k , ε ) such that for every n ≥ N 0 n\ge N_0 n ≥ N 0 and every n n n -vertex W 2 k + 1 W_{2k+1} W 2 k + 1 -free graph G G G , then:
d U ( v ) ≤ k − 1 d_U(v)\le k-1 d U ( v ) ≤ k − 1 for every vertex v ∈ L v\in L v ∈ L .
If d U ( u ) = k − 1 d_U(u)=k-1 d U ( u ) = k − 1 for some u ∈ U u\in U u ∈ U , then d W ( u ) = 0 d_W(u)=0 d W ( u ) = 0 .
For every vertex u ∈ U u\in U u ∈ U , d L ( u ) ≤ D 0 : = ⌈ ( k − 1 ) ( 4 / ε ) k ⌉ d_L(u)\le D_0:=\lceil(k-1)(4/\varepsilon)^k\rceil d L ( u ) ≤ D 0 := ⌈( k − 1 ) ( 4/ ε ) k ⌉ .
Proof. For (1), suppose that v ∈ L v \in L v ∈ L is adjacent to k k k vertices u 1 , … , u k ∈ U u_1,\ldots,u_k \in U u 1 , … , u k ∈ U . Since d G ( v ) ≥ ε n d_G(v) \ge\varepsilon n d G ( v ) ≥ ε n and each u j u_j u j has at most n − d G ( u j ) ≤ α n + 1 n-d_G(u_j) \le\alpha n+1 n − d G ( u j ) ≤ α n + 1 nonneighbours (including itself),
∣ N ( v ) ∩ ⋂ j = 1 k N ( u j ) ∣ ≥ ε n − k ( α n + 1 ) > k \left|N(v) \cap\bigcap_{j=1}^{k}N(u_j)\right| \ge\varepsilon n-k(\alpha n+1)>k N ( v ) ∩ j = 1 ⋂ k N ( u j ) ≥ ε n − k ( α n + 1 ) > k
for n ≥ N 0 ( k , ε ) n \ge N_0(k,\varepsilon) n ≥ N 0 ( k , ε ) . Hence, the vertices u 1 , … , u k u_1,\ldots,u_k u 1 , … , u k together with k k k vertices in N ( v ) ∩ ⋂ j = 1 k N ( u j ) N(v) \cap\bigcap_{j=1}^{k}N(u_j) N ( v ) ∩ ⋂ j = 1 k N ( u j ) form an alternating C 2 k C_{2k} C 2 k inside N ( v ) N(v) N ( v ) , a contradiction.
For (2), let S ⊆ N U ( u ) S \subseteq N_U(u) S ⊆ N U ( u ) with ∣ S ∣ = k − 1 |S|=k-1 ∣ S ∣ = k − 1 , and suppose that z ∈ N W ( u ) z \in N_W(u) z ∈ N W ( u ) . Note that z ∈ W ⊆ L z \in W \subseteq L z ∈ W ⊆ L and { u } ∪ S ⊆ U \{u\} \cup S \subseteq U { u } ∪ S ⊆ U , similarly as the previous proof,
∣ N ( z ) ∩ N ( u ) ∩ ⋂ s ∈ S N ( s ) ∣ ≥ ε n − k ( α n + 1 ) > k \left|N(z) \cap N(u) \cap\bigcap_{s\in S}N(s)\right| \ge\varepsilon n-k(\alpha n+1)>k N ( z ) ∩ N ( u ) ∩ s ∈ S ⋂ N ( s ) ≥ ε n − k ( α n + 1 ) > k
for n ≥ N 0 ( k , ε ) n \ge N_0(k,\varepsilon) n ≥ N 0 ( k , ε ) . Hence, the k k k vertices of S ∪ { z } S \cup\{z\} S ∪ { z } and k k k vertices in N ( z ) ∩ N ( u ) ∩ ⋂ s ∈ S N ( s ) N(z) \cap N(u) \cap\bigcap_{s\in S}N(s) N ( z ) ∩ N ( u ) ∩ ⋂ s ∈ S N ( s ) form an alternating C 2 k C_{2k} C 2 k inside N ( u ) N(u) N ( u ) , a contradiction, too.
For (3), every vertex v ∈ N L ( u ) = N ( u ) ∩ L v \in N_L(u)=N(u)\cap L v ∈ N L ( u ) = N ( u ) ∩ L satisfies
d N ( u ) ( v ) ≥ d G ( v ) − ∣ V ( G ) ∖ N ( u ) ∣ ≥ ε n − ( n − d G ( u ) ) ≥ ε n − α n − 1 ≥ ε n 2 . d_{N(u)}(v) \ge d_G(v)-|V(G)\setminus N(u)| \ge\varepsilon n-(n-d_G(u)) \ge\varepsilon n-\alpha n-1 \ge\frac{\varepsilon n}{2}. d N ( u ) ( v ) ≥ d G ( v ) − ∣ V ( G ) ∖ N ( u ) ∣ ≥ ε n − ( n − d G ( u )) ≥ ε n − α n − 1 ≥ 2 ε n .
for n ≥ N 0 ( k , ε ) n \ge N_0(k,\varepsilon) n ≥ N 0 ( k , ε ) . Since G [ N ( u ) ] G[N(u)] G [ N ( u )] is C 2 k C_{2k} C 2 k -free, it is K k , k K_{k,k} K k , k -free. Thus, every k k k -subset of N ( u ) N(u) N ( u ) can be contained in the neighborhoods of at most k − 1 k-1 k − 1 vertices in N L ( u ) N_L(u) N L ( u ) . This gives
d L ( u ) ( ⌊ ε n / 2 ⌋ k ) ≤ ∑ v ∈ N L ( u ) ( d N ( u ) ( v ) k ) ≤ ( k − 1 ) ( d G ( u ) k ) . d_L(u)\binom{\lfloor\varepsilon n/2\rfloor}{k}\le\sum_{v\in N_L(u)}\binom{d_{N(u)}(v)}{k}\le(k-1)\binom{d_G(u)}{k}. d L ( u ) ( k ⌊ ε n /2 ⌋ ) ≤ v ∈ N L ( u ) ∑ ( k d N ( u ) ( v ) ) ≤ ( k − 1 ) ( k d G ( u ) ) .
Note that ⌊ ε n / 2 ⌋ − k + 1 ≥ ε n / 4 \lfloor\varepsilon n/2\rfloor-k+1\ge\varepsilon n/4 ⌊ ε n /2 ⌋ − k + 1 ≥ ε n /4 for n ≥ N 0 ( k , ε ) n\ge N_0(k,\varepsilon) n ≥ N 0 ( k , ε ) . Then
( ⌊ ε n / 2 ⌋ k ) ≥ ( ε n / 4 ) k k ! , ( d G ( u ) k ) ≤ n k k ! . \binom{\lfloor\varepsilon n/2\rfloor}{k}\ge\frac{(\varepsilon n/4)^k}{k!},\qquad\binom{d_G(u)}{k}\le\frac{n^k}{k!}. ( k ⌊ ε n /2 ⌋ ) ≥ k ! ( ε n /4 ) k , ( k d G ( u ) ) ≤ k ! n k .
It follows that d L ( u ) ≤ ( k − 1 ) ( 4 / ε ) k ≤ D 0 d_L(u)\le(k-1)(4/\varepsilon)^k\le D_0 d L ( u ) ≤ ( k − 1 ) ( 4/ ε ) k ≤ D 0 .
We may also use the classical result of Bondy and Simonovits [1 ] that, for every fixed integer k ≥ 3 k\ge3 k ≥ 3 , every C 2 k C_{2k} C 2 k -free graph on m m m vertices has at most O k ( m 1 + 1 / k ) = o k ( m 2 ) O_k(m^{1+1/k})=o_k(m^2) O k ( m 1 + 1/ k ) = o k ( m 2 ) edges.
A Schur-complement estimate
For integers s , t > 0 s,t>0 s , t > 0 , let J s × t J_{s\times t} J s × t be the s × t s\times t s × t matrix whose entries are all 1’s. Write J t : = J t × t J_t:=J_{t\times t} J t := J t × t and 1 t = J t × 1 \mathbf{1}_t=J_{t\times1} 1 t = J t × 1 for short. Also, I t I_t I t is the t × t t\times t t × t unit matrix. We use λ max ( M ) \lambda_{\max}(M) λ m a x ( M ) to denote the spectral radius of a matrix M M M .
In this subsection, suppose ∣ L ∣ = o ( n ) |L|=o(n) ∣ L ∣ = o ( n ) , q = q ( G ) > n q=q(G)>n q = q ( G ) > n , and let x = ( x v ) x=(x_v) x = ( x v ) be a nonnegative q q q -eigenvector normalized by max v x v = 1 \max_v x_v=1 max v x v = 1 . Order vertices by L ⊔ R L\sqcup R L ⊔ R . We write x T = ( x L T , x R T ) x^{\mathsf T}=(x_L^{\mathsf T},x_R^{\mathsf T}) x T = ( x L T , x R T ) and write
Q ( G ) = ( A B B T C ) , P = B ( q I ∣ R ∣ − C ) − 1 B T . Q(G)=\begin{pmatrix} A & B \\ B^{\mathsf T} & C \end{pmatrix},\qquad P=B(qI_{|R|}-C)^{-1}B^{\mathsf T}. Q ( G ) = ( A B T B C ) , P = B ( q I ∣ R ∣ − C ) − 1 B T .
Put a 0 = ( 1 − 2 ε ) − 1 a_0=(1-2\varepsilon)^{-1} a 0 = ( 1 − 2 ε ) − 1 and r = 16 a 0 e ( R ) / n 2 r=16a_0e(R)/n^2 r = 16 a 0 e ( R ) / n 2 .
Lemma 2.5. For all sufficiently large n n n , P ≤ ( 1 + r ) J ∣ L ∣ P\leq(1+r)J_{|L|} P ≤ ( 1 + r ) J ∣ L ∣ entrywise.
Proof. We write Q R = Q ( G [ R ] ) Q_R=Q(G[R]) Q R = Q ( G [ R ]) for short. Since 0 ≤ C ≤ ∣ L ∣ I ∣ R ∣ + Q R 0\leq C\leq|L|I_{|R|}+Q_R 0 ≤ C ≤ ∣ L ∣ I ∣ R ∣ + Q R entrywise and both matrices have spectral radius smaller than q q q , the comparison of their nonnegative Neumann series and simple calculations give
( q I ∣ R ∣ − C ) − 1 ≤ ( ( q − ∣ L ∣ ) I ∣ R ∣ − Q R ) − 1 (qI_{|R|}-C)^{-1}\leq((q-|L|)I_{|R|}-Q_R)^{-1} ( q I ∣ R ∣ − C ) − 1 ≤ (( q − ∣ L ∣ ) I ∣ R ∣ − Q R ) − 1 = 1 q − ∣ L ∣ ( I ∣ R ∣ + Q R ( ( q − ∣ L ∣ ) I ∣ R ∣ − Q R ) − 1 ) =\frac{1}{q-|L|}\left(I_{|R|}+Q_R((q-|L|)I_{|R|}-Q_R)^{-1}\right) = q − ∣ L ∣ 1 ( I ∣ R ∣ + Q R (( q − ∣ L ∣ ) I ∣ R ∣ − Q R ) − 1 ) entrywise. Hence
P = B ( q I ∣ R ∣ − C ) − 1 B T P=B(qI_{|R|}-C)^{-1}B^{\mathsf T} P = B ( q I ∣ R ∣ − C ) − 1 B T ≤ 1 q − ∣ L ∣ B ( I ∣ R ∣ + Q R ( ( q − ∣ L ∣ ) I ∣ R ∣ − Q R ) − 1 ) B T \leq\frac{1}{q-|L|}B\left(I_{|R|}+Q_R((q-|L|)I_{|R|}-Q_R)^{-1}\right)B^{\mathsf T} ≤ q − ∣ L ∣ 1 B ( I ∣ R ∣ + Q R (( q − ∣ L ∣ ) I ∣ R ∣ − Q R ) − 1 ) B T = 1 q − ∣ L ∣ B B T + 1 q − ∣ L ∣ B Q R ( ( q − ∣ L ∣ ) I ∣ R ∣ − Q R ) − 1 B T (1) =\frac{1}{q-|L|}BB^{\mathsf T}+\frac{1}{q-|L|}BQ_R((q-|L|)I_{|R|}-Q_R)^{-1}B^{\mathsf T} \tag*{(1)} = q − ∣ L ∣ 1 B B T + q − ∣ L ∣ 1 B Q R (( q − ∣ L ∣ ) I ∣ R ∣ − Q R ) − 1 B T (1) ≤ J ∣ L ∣ + 1 q − ∣ L ∣ B Q R ( ( q − ∣ L ∣ ) I ∣ R ∣ − Q R ) − 1 B T \leq J_{|L|}+\frac{1}{q-|L|}BQ_R((q-|L|)I_{|R|}-Q_R)^{-1}B^{\mathsf T} ≤ J ∣ L ∣ + q − ∣ L ∣ 1 B Q R (( q − ∣ L ∣ ) I ∣ R ∣ − Q R ) − 1 B T entrywise. The last inequality holds since the entries of 1 q − ∣ L ∣ B B T \frac{1}{q-|L|}BB^{\mathsf T} q − ∣ L ∣ 1 B B T are at most n − ∣ L ∣ q − ∣ L ∣ < 1 \frac{n-|L|}{q-|L|}<1 q − ∣ L ∣ n − ∣ L ∣ < 1 .
We next estimate the second term. Let b = ( b v ) b=(b_v) b = ( b v ) be any column of B T B^{\mathsf T} B T . Then 0 ≤ b ≤ 1 0\leq b\leq1 0 ≤ b ≤ 1 . Set z = ( z v ) = ( ( q − ∣ L ∣ ) I ∣ R ∣ − Q R ) − 1 b z=(z_v)=((q-|L|)I_{|R|}-Q_R)^{-1}b z = ( z v ) = (( q − ∣ L ∣ ) I ∣ R ∣ − Q R ) − 1 b . ( ( q − ∣ L ∣ ) I ∣ R ∣ − Q R ) − 1 ((q-|L|)I_{|R|}-Q_R)^{-1} (( q − ∣ L ∣ ) I ∣ R ∣ − Q R ) − 1 is entrywise nonnegative by its Neumann series, so z ≥ 0 z\geq0 z ≥ 0 entrywise. Choose u ∈ R u\in R u ∈ R such that z u = max v ∈ R z v z_u=\max_{v\in R}z_v z u = max v ∈ R z v . Note that b u ≤ 1 b_u\leq1 b u ≤ 1 and z v ≤ z u z_v\leq z_u z v ≤ z u for every v ∈ R v\in R v ∈ R . Consider the row of u u u in ( ( q − ∣ L ∣ ) I ∣ R ∣ − Q R ) z = b ((q-|L|)I_{|R|}-Q_R)z=b (( q − ∣ L ∣ ) I ∣ R ∣ − Q R ) z = b , we get
( q − ∣ L ∣ ) z u = b u + d R ( u ) z u + ∑ v ∈ N R ( u ) z v ≤ 1 + 2 d R ( u ) z u ≤ 1 + 2 Δ ( G [ R ] ) z u . (q-|L|)z_u=b_u+d_R(u)z_u+\sum_{v\in N_R(u)}z_v\leq1+2d_R(u)z_u\leq1+2\Delta(G[R])z_u. ( q − ∣ L ∣ ) z u = b u + d R ( u ) z u + v ∈ N R ( u ) ∑ z v ≤ 1 + 2 d R ( u ) z u ≤ 1 + 2Δ ( G [ R ]) z u .
This implies z u ≤ 1 q − ∣ L ∣ − 2 Δ ( G [ R ] ) z_u \le\frac{1}{q-|L|-2\Delta(G[R])} z u ≤ q − ∣ L ∣ − 2Δ ( G [ R ]) 1 . In other words, z ≤ 1 q − ∣ L ∣ − 2 Δ ( G [ R ] ) 1 z \le\frac{1}{q-|L|-2\Delta(G[R])}^{1} z ≤ q − ∣ L ∣ − 2Δ ( G [ R ]) 1 1 .
This holds for every column of B T B^{\mathsf T} B T , which means
( ( q − ∣ L ∣ ) I ∣ R ∣ − Q R ) − 1 B T ≤ 1 q − ∣ L ∣ − 2 Δ ( G [ R ] ) J ∣ R ∣ × ∣ L ∣ . \left((q-|L|)I_{|R|}-Q_R\right)^{-1}B^{\mathsf T}\le\frac{1}{q-|L|-2\Delta(G[R])}J_{|R|\times|L|}. ( ( q − ∣ L ∣ ) I ∣ R ∣ − Q R ) − 1 B T ≤ q − ∣ L ∣ − 2Δ ( G [ R ]) 1 J ∣ R ∣ × ∣ L ∣ .
Note that 0 ≤ B ≤ J ∣ L ∣ × ∣ R ∣ 0\le B\le J_{|L|\times|R|} 0 ≤ B ≤ J ∣ L ∣ × ∣ R ∣ entrywise, and J ∣ L ∣ × ∣ R ∣ Q R J ∣ R ∣ × ∣ L ∣ = 4 e ( R ) J ∣ L ∣ J_{|L|\times|R|}Q_RJ_{|R|\times|L|}=4e(R)J_{|L|} J ∣ L ∣ × ∣ R ∣ Q R J ∣ R ∣ × ∣ L ∣ = 4 e ( R ) J ∣ L ∣ . It holds
B Q R ( ( q − ∣ L ∣ ) I ∣ R ∣ − Q R ) − 1 B T ≤ 1 q − ∣ L ∣ − 2 Δ ( G [ R ] ) J ∣ L ∣ × ∣ R ∣ Q R J ∣ R ∣ × ∣ L ∣ = 4 e ( R ) q − ∣ L ∣ − 2 Δ ( G [ R ] ) J ∣ L ∣ . \begin{aligned}
BQ_R\left((q-|L|)I_{|R|}-Q_R\right)^{-1}B^{\mathsf T}
\le\frac{1}{q-|L|-2\Delta(G[R])}J_{|L|\times|R|}Q_RJ_{|R|\times|L|} \\
&= \frac{4e(R)}{q-|L|-2\Delta(G[R])}J_{|L|}.
\end{aligned} B Q R ( ( q − ∣ L ∣ ) I ∣ R ∣ − Q R ) − 1 B T ≤ q − ∣ L ∣ − 2Δ ( G [ R ]) 1 J ∣ L ∣ × ∣ R ∣ Q R J ∣ R ∣ × ∣ L ∣ = q − ∣ L ∣ − 2Δ ( G [ R ]) 4 e ( R ) J ∣ L ∣ .
This inequation, together with (1), gives P ≤ ( 1 + 4 e ( R ) ( q − ∣ L ∣ ) ( q − ∣ L ∣ − 2 Δ ( G [ R ] ) ) ) J ∣ L ∣ P\le\left(1+\frac{4e(R)}{(q-|L|)(q-|L|-2\Delta(G[R]))}\right)J_{|L|} P ≤ ( 1 + ( q − ∣ L ∣ ) ( q − ∣ L ∣ − 2Δ ( G [ R ])) 4 e ( R ) ) J ∣ L ∣ .
It remains to prove 4 e ( R ) ( q − ∣ L ∣ ) ( q − ∣ L ∣ − 2 Δ ( G [ R ] ) ) < r = 16 a 0 e ( R ) / n 2 \frac{4e(R)}{(q-|L|)(q-|L|-2\Delta(G[R]))}<r=16a_0e(R)/n^2 ( q − ∣ L ∣ ) ( q − ∣ L ∣ − 2Δ ( G [ R ])) 4 e ( R ) < r = 16 a 0 e ( R ) / n 2 . This is trivial since q − ∣ L ∣ > n 2 q-|L|>\frac{n}{2} q − ∣ L ∣ > 2 n and q − ∣ L ∣ − 2 Δ ( G [ R ] ) > 1 − 2 ε 2 n = n 2 a 0 q-|L|-2\Delta(G[R])>\frac{1-2\varepsilon}{2}n=\frac{n}{2a_0} q − ∣ L ∣ − 2Δ ( G [ R ]) > 2 1 − 2 ε n = 2 a 0 n for large n n n .
Lemma 2.6. Let X = ∑ v ∈ L x v X=\sum_{v\in L}x_v X = ∑ v ∈ L x v , δ R ( v ) = ∣ R ∖ N G ( v ) ∣ \delta_R(v)=|R\setminus N_G(v)| δ R ( v ) = ∣ R ∖ N G ( v ) ∣ , and
M = A ( G [ L ] ) + J ∣ L ∣ − n I ∣ L ∣ + diag ( d G ( v ) : v ∈ L ) . \mathcal{M}=A(G[L])+J_{|L|}-nI_{|L|}+\operatorname{diag}(d_G(v):v\in L). M = A ( G [ L ]) + J ∣ L ∣ − n I ∣ L ∣ + diag ( d G ( v ) : v ∈ L ) . We have
( q − n ) x L ≤ M x L + r X 1 , (2) (q-n)x_L\le\mathcal{M}x_L+rX\mathbf{1}, \tag*{(2)} ( q − n ) x L ≤ M x L + r X 1 , (2) ( q − n ) X ≤ ∑ v ∈ L ( 2 d L ( v ) − δ R ( v ) ) x v + r ∣ L ∣ X , (3) (q-n)X\le\sum_{v\in L}(2d_L(v)-\delta_R(v))x_v+r|L|X, \tag*{(3)} ( q − n ) X ≤ v ∈ L ∑ ( 2 d L ( v ) − δ R ( v )) x v + r ∣ L ∣ X , (3) q − n ≤ λ max ( M ) + r ∣ L ∣ . (4) q-n\le\lambda_{\max}(\mathcal{M})+r|L|. \tag*{(4)} q − n ≤ λ m a x ( M ) + r ∣ L ∣. (4) Furthermore, for a vertex u u u with x u = 1 x_u=1 x u = 1 , we have u ∈ L u\in L u ∈ L and
q − n ≤ d L ( u ) − δ R ( u ) − ∣ L ∣ + ∑ v ∈ N L ( u ) x v + ( 1 + r ) X . (5) q-n\le d_L(u)-\delta_R(u)-|L|+\sum_{v\in N_L(u)}x_v+(1+r)X. \tag*{(5)} q − n ≤ d L ( u ) − δ R ( u ) − ∣ L ∣ + v ∈ N L ( u ) ∑ x v + ( 1 + r ) X . (5)
Proof. Since q I − Q ( G ) qI-Q(G) q I − Q ( G ) is positive semidefinite, its Schur complement q I − A − P qI-A-P q I − A − P is positive semidefinite and singular. Hence q = λ max ( A + P ) q=\lambda_{\max}(A+P) q = λ m a x ( A + P ) . Also, ( A + P ) x L = q x L (A+P)x_L=qx_L ( A + P ) x L = q x L . Note that M = A ( G [ L ] ) + J − n I + diag ( d G ( v ) : v ∈ L ) = A + J − n I \mathcal{M}=A(G[L])+J-nI+\operatorname{diag}(d_G(v):v\in L)=A+J-nI M = A ( G [ L ]) + J − n I + diag ( d G ( v ) : v ∈ L ) = A + J − n I . We then have M x L = ( q − n ) x L + X 1 − P x L \mathcal{M}x_L=(q-n)x_L+X\mathbf{1}-Px_L M x L = ( q − n ) x L + X 1 − P x L . By Lemma 2.5, we soon get (2). It can be checked that the row sum at v ∈ L v\in L v ∈ L of M \mathcal{M} M equals 2 d L ( v ) − δ R ( v ) 2d_L(v)-\delta_R(v) 2 d L ( v ) − δ R ( v ) . By (2), this gives (3).
By Lemma 2.5, A + P ≤ A + ( 1 + r ) J ∣ L ∣ A+P\le A+(1+r)J_{|L|} A + P ≤ A + ( 1 + r ) J ∣ L ∣ entrywise. Both matrices are nonnegative and symmetric, so Perron–Frobenius monotonicity gives q ≤ λ max ( A + ( 1 + r ) J ∣ L ∣ ) q \le\lambda_{\max}(A+(1+r)J_{|L|}) q ≤ λ m a x ( A + ( 1 + r ) J ∣ L ∣ ) . Therefore q − n ≤ λ max ( M + r J ∣ L ∣ ) ≤ λ max ( M ) + λ max ( r J ∣ L ∣ ) = λ max ( M ) + r ∣ L ∣ q-n \le\lambda_{\max}(\mathcal{M}+rJ_{|L|}) \le\lambda_{\max}(\mathcal{M})+\lambda_{\max}(rJ_{|L|})=\lambda_{\max}(\mathcal{M})+r|L| q − n ≤ λ m a x ( M + r J ∣ L ∣ ) ≤ λ m a x ( M ) + λ m a x ( r J ∣ L ∣ ) = λ m a x ( M ) + r ∣ L ∣ , which completes the proof of (4). If u ∈ R u\in R u ∈ R , its eigenvalue equation would imply q ≤ 2 d G ( u ) < n q\le2d_G(u)<n q ≤ 2 d G ( u ) < n , which is a contradiction. Hence u ∈ L u\in L u ∈ L . Consider u ∈ L u\in L u ∈ L with x u = 1 x_u=1 x u = 1 in (2), we get (5).
Proof of the extremal case
In this section, we deal with the case when the n n n -vertex W 2 k + 1 W_{2k+1} W 2 k + 1 -free graph contains only o ( n ) o(n) o ( n ) vertices of degree at least Θ ( n ) \Theta(n) Θ ( n ) .
Theorem 3.1. Fix k ≥ 3 k\ge3 k ≥ 3 and 0 < ε < 1 / 2 0<\varepsilon<1/2 0 < ε < 1/2 . If G G G is an n n n -vertex W 2 k + 1 W_{2k+1} W 2 k + 1 -free graph with q ( G ) ≥ q ( S n , k + ) q(G)\ge q(S^+_{n,k}) q ( G ) ≥ q ( S n , k + ) and ∣ L G ( ε n ) ∣ = o k , ε ( n ) |L_G(\varepsilon n)|=o_{k,\varepsilon}(n) ∣ L G ( ε n ) ∣ = o k , ε ( n ) , then G ≅ S n , k + G\cong S^+_{n,k} G ≅ S n , k + holds for all sufficiently large n n n .
We prove the theorem by several claims. Throughout the proof, we consider an n n n -vertex W 2 k + 1 W_{2k+1} W 2 k + 1 -free graph G G G with n ≥ N n\ge N n ≥ N , q ≥ q ( S n , k + ) q\ge q(S^+_{n,k}) q ≥ q ( S n , k + ) and ∣ L ∣ = o ( n ) |L|=o(n) ∣ L ∣ = o ( n ) , where we write q = q ( G ) q=q(G) q = q ( G ) and use L , R , U , W L,R,U,W L , R , U , W defined before. Moreover, define δ ( v ) = n − 1 − d G ( v ) \delta(v)=n-1-d_G(v) δ ( v ) = n − 1 − d G ( v ) and δ R ( v ) = ∣ R ∖ N ( v ) ∣ \delta_R(v)=|R\setminus N(v)| δ R ( v ) = ∣ R ∖ N ( v ) ∣ for v ∈ L v\in L v ∈ L . Choose a nonnegative q q q -eigenvector x x x with max v ∈ V ( G ) x v = 1 \max_{v\in V(G)}x_v=1 max v ∈ V ( G ) x v = 1 , and put X = ∑ v ∈ L x v X=\sum_{v\in L}x_v X = ∑ v ∈ L x v . By Lemma 2.1,
q − n > 2 ( k − 1 ) − 2 k ( k − 1 ) n > 0. (6) q-n>2(k-1)-\frac{2k(k-1)}{n}>0. \tag*{(6)} q − n > 2 ( k − 1 ) − n 2 k ( k − 1 ) > 0. (6)
Lemma 2.6 ensures that a vertex u u u with x u = 1 x_u=1 x u = 1 belongs to L L L . Recall α = ε / ( 2 k ) \alpha=\varepsilon/(2k) α = ε / ( 2 k ) , a 0 = ( 1 − 2 ε ) − 1 a_0=(1-2\varepsilon)^{-1} a 0 = ( 1 − 2 ε ) − 1 and r = 16 a 0 e ( R ) / n 2 r=16a_0e(R)/n^2 r = 16 a 0 e ( R ) / n 2 , and set
D 0 = [ ( k − 1 ) ( 4 / ε ) k ] , b 0 = 1 + a 0 α , b 1 = b 0 ∣ L ∣ n = o ( 1 ) . D_0=\left[(k-1)(4/\varepsilon)^k\right],\qquad b_0=\frac{1+a_0}{\alpha},\qquad b_1=b_0\frac{|L|}{n}=o(1). D 0 = [ ( k − 1 ) ( 4/ ε ) k ] , b 0 = α 1 + a 0 , b 1 = b 0 n ∣ L ∣ = o ( 1 ) .
Claim 1. u ∈ U u\in U u ∈ U .
Proof. For large n n n , R R R is nonempty as ∣ L ∣ = o ( n ) |L|=o(n) ∣ L ∣ = o ( n ) . Pick a vertex v m ∈ R v_m\in R v m ∈ R with x v m = max v ∈ R x v x_{v_m}=\max_{v\in R}x_v x v m = max v ∈ R x v . The eigenvalue equation at v m v_m v m , together with x v ≤ 1 x_v\le1 x v ≤ 1 on L L L , gives
( q − d G ( v m ) ) x v m = ∑ v ∈ N L ( v m ) x v + ∑ v ∈ N R ( v m ) x v ≤ ∣ L ∣ + d R ( v m ) x v m . (q-d_G(v_m))x_{v_m}=\sum_{v\in N_L(v_m)}x_v+\sum_{v\in N_R(v_m)}x_v\le|L|+d_R(v_m)x_{v_m}. ( q − d G ( v m )) x v m = v ∈ N L ( v m ) ∑ x v + v ∈ N R ( v m ) ∑ x v ≤ ∣ L ∣ + d R ( v m ) x v m .
Since d R ( v m ) ≤ d G ( v m ) < ε n d_R(v_m)\le d_G(v_m)<\varepsilon n d R ( v m ) ≤ d G ( v m ) < ε n and q > n q>n q > n , it follows that
x v m ≤ ∣ L ∣ q − d G ( v m ) − d R ( v m ) ≤ ∣ L ∣ ( 1 − 2 ε ) n = a 0 ∣ L ∣ n . x_{v_m}\le\frac{|L|}{q-d_G(v_m)-d_R(v_m)}\le\frac{|L|}{(1-2\varepsilon)n}=a_0\frac{|L|}{n}. x v m ≤ q − d G ( v m ) − d R ( v m ) ∣ L ∣ ≤ ( 1 − 2 ε ) n ∣ L ∣ = a 0 n ∣ L ∣ .
Consequently,
∑ v ∈ V ( G ) x v ≤ ∣ L ∣ + ∣ R ∣ x v m ≤ ( 1 + a 0 ) ∣ L ∣ . (7) \sum_{v\in V(G)} x_v \le|L| + |R|x_{v_m} \le(1+a_0)|L|. \tag*{(7)} v ∈ V ( G ) ∑ x v ≤ ∣ L ∣ + ∣ R ∣ x v m ≤ ( 1 + a 0 ) ∣ L ∣. (7)
As x u = 1 x_u=1 x u = 1 , the eigenvalue equation at u u u implies
q − d G ( u ) = ∑ v ∈ N ( u ) x v ≤ ∑ v ∈ V ( G ) x v . q-d_G(u)=\sum_{v\in N(u)}x_v\le\sum_{v\in V(G)}x_v. q − d G ( u ) = v ∈ N ( u ) ∑ x v ≤ v ∈ V ( G ) ∑ x v .
Note that δ ( u ) = q − d G ( u ) − ( 1 + q − n ) < q − d G ( u ) \delta(u)=q-d_G(u)-(1+q-n)<q-d_G(u) δ ( u ) = q − d G ( u ) − ( 1 + q − n ) < q − d G ( u ) . Thus
0 ≤ δ ( u ) < ( 1 + a 0 ) ∣ L ∣ = o ( n ) . (8) 0\le\delta(u)<(1+a_0)|L|=o(n). \tag*{(8)} 0 ≤ δ ( u ) < ( 1 + a 0 ) ∣ L ∣ = o ( n ) . (8)
In particular, for large n n n , we have δ ( u ) ≤ α n \delta(u)\le\alpha n δ ( u ) ≤ α n , so u ∈ U u\in U u ∈ U .
Claim 2. x v ≤ b 1 x_v\le b_1 x v ≤ b 1 for v ∈ W v\in W v ∈ W .
Proof. By Lemma 2.4 , since n n n is sufficiently large,
d L ( u ) ≤ D 0 . (9) d_L(u)\le D_0. \tag*{(9)} d L ( u ) ≤ D 0 . (9) For v ∈ W v\in W v ∈ W , we have δ ( v ) > α n \delta(v)>\alpha n δ ( v ) > α n . Applying the eigenvalue equation at v ∈ W v\in W v ∈ W and using (7) and q − d G ( v ) = 1 + q − n + δ ( v ) > δ ( v ) > α n q-d_G(v)=1+q-n+\delta(v)>\delta(v)>\alpha n q − d G ( v ) = 1 + q − n + δ ( v ) > δ ( v ) > α n , we get
0 ≤ x v = ∑ i ∈ N ( v ) x i q − d G ( v ) ≤ ( 1 + a 0 ) ∣ L ∣ α n = b 0 ∣ L ∣ n = b 1 = o ( 1 ) 0\le x_v=\frac{\sum_{i\in N(v)}x_i}{q-d_G(v)}
\le\frac{(1+a_0)|L|}{\alpha n}
=b_0\frac{|L|}{n}
=b_1=o(1) 0 ≤ x v = q − d G ( v ) ∑ i ∈ N ( v ) x i ≤ α n ( 1 + a 0 ) ∣ L ∣ = b 0 n ∣ L ∣ = b 1 = o ( 1 ) holds for every $v\in W.
Claim 3. e ( R ) = o ( n 2 ) e(R)=o(n^2) e ( R ) = o ( n 2 ) . In particular, r = o ( 1 ) r=o(1) r = o ( 1 ) .
Proof. Every W 2 k + 1 W_{2k+1} W 2 k + 1 -free graph has C 2 k C_{2k} C 2 k -free neighborhoods. In particular, G [ R ∩ N ( u ) ] G[R\cap N(u)] G [ R ∩ N ( u )] is C 2 k C_{2k} C 2 k -free and has o ( n 2 ) o(n^2) o ( n 2 ) edges. The set R ∖ N ( u ) R\setminus N(u) R ∖ N ( u ) has δ R ( u ) ≤ δ ( u ) = o ( n ) \delta_R(u)\le\delta(u)=o(n) δ R ( u ) ≤ δ ( u ) = o ( n ) vertices, whose degrees are all less than ε n \varepsilon n ε n . Hence
e ( R ) ≤ e ( G [ R ∩ N ( u ) ] ) + ε n δ R ( u ) = o ( n 2 ) . e(R)\le e(G[R\cap N(u)])+\varepsilon n\delta_R(u)=o(n^2). e ( R ) ≤ e ( G [ R ∩ N ( u )]) + ε n δ R ( u ) = o ( n 2 ) . It follows that r = 16 a 0 e ( R ) / n 2 = o ( 1 ) r=16a_0e(R)/n^2=o(1) r = 16 a 0 e ( R ) / n 2 = o ( 1 ) .
Claim 4. r ∣ L ∣ = o ( 1 ) r|L|=o(1) r ∣ L ∣ = o ( 1 ) .
Proof. By Claim 3, we can assume ∣ L ∣ → ∞ |L| \to\infty ∣ L ∣ → ∞ . Let X = ∑ v ∈ L x v X = \sum_{v\in L} x_v X = ∑ v ∈ L x v . The fact that δ R ( u ) + q − n ≥ 0 \delta_R(u)+q-n \ge0 δ R ( u ) + q − n ≥ 0 and ∑ v ∈ N L ( u ) x v ≤ d L ( u ) \sum_{v\in N_L(u)} x_v \le d_L(u) ∑ v ∈ N L ( u ) x v ≤ d L ( u ) , together with (5) and (9), implies
∣ L ∣ − X ≤ 2 D 0 + r X ≤ 2 D 0 + r ∣ L ∣ . (10) |L|-X \le2D_0+rX \le2D_0+r|L|. \tag*{(10)} ∣ L ∣ − X ≤ 2 D 0 + r X ≤ 2 D 0 + r ∣ L ∣. (10)
By Claim 3 and (10), we have X = ∣ L ∣ − o ( ∣ L ∣ ) X=|L|-o(|L|) X = ∣ L ∣ − o ( ∣ L ∣ ) . Put
A ∗ = { v ∈ L : x v ≥ 1 2 } , X W = ∑ i ∈ W x i . A_*=\{v\in L:x_v\ge\tfrac{1}{2}\},\qquad X_W=\sum_{i\in W}x_i. A ∗ = { v ∈ L : x v ≥ 2 1 } , X W = i ∈ W ∑ x i .
The inequality X ≤ ∣ A ∗ ∣ + 1 2 ( ∣ L ∣ − ∣ A ∗ ∣ ) X\le|A_*|+\frac{1}{2}(|L|-|A_*|) X ≤ ∣ A ∗ ∣ + 2 1 ( ∣ L ∣ − ∣ A ∗ ∣ ) gives ∣ A ∗ ∣ ≥ 2 X − ∣ L ∣ ≥ ∣ L ∣ / 2 |A_*|\ge2X-|L|\ge|L|/2 ∣ A ∗ ∣ ≥ 2 X − ∣ L ∣ ≥ ∣ L ∣/2 for large n n n , so in particular ∣ A ∗ ∣ ≥ k |A_*|\ge k ∣ A ∗ ∣ ≥ k . By (7), for each v ∈ A ∗ v\in A_* v ∈ A ∗ , the eigenvalue equation gives
δ ( v ) x v ≤ ( q − d G ( v ) ) x v = ∑ i ∈ N ( v ) x i ≤ ( 1 + a 0 ) ∣ L ∣ . \delta(v)x_v\le(q-d_G(v))x_v=\sum_{i\in N(v)}x_i\le(1+a_0)|L|. δ ( v ) x v ≤ ( q − d G ( v )) x v = i ∈ N ( v ) ∑ x i ≤ ( 1 + a 0 ) ∣ L ∣.
Since x v ≥ 1 / 2 x_v\ge1/2 x v ≥ 1/2 , we obtain δ ( v ) ≤ 2 ( 1 + a 0 ) ∣ L ∣ = o ( n ) \delta(v)\le2(1+a_0)|L|=o(n) δ ( v ) ≤ 2 ( 1 + a 0 ) ∣ L ∣ = o ( n ) . Thus A ∗ ⊆ U A_*\subseteq U A ∗ ⊆ U for all sufficiently large n n n .
By Claim 2,
( 1 − b 1 ) ∣ W ∣ ≤ ∑ v ∈ W ( 1 − x v ) ≤ ∣ L ∣ − X ≤ 2 D 0 + r ∣ L ∣ . (1-b_1)|W|\le\sum_{v\in W}(1-x_v)\le|L|-X\le2D_0+r|L|. ( 1 − b 1 ) ∣ W ∣ ≤ v ∈ W ∑ ( 1 − x v ) ≤ ∣ L ∣ − X ≤ 2 D 0 + r ∣ L ∣.
Taking n n n sufficiently large that b 1 ≤ 1 / 2 b_1\le1/2 b 1 ≤ 1/2 , we have
∣ W ∣ ≤ 4 D 0 + 2 r ∣ L ∣ = 4 D 0 + 32 a 0 ∣ L ∣ n 2 e ( R ) . (11) |W|\le4D_0+2r|L|=4D_0+\frac{32a_0|L|}{n^2}e(R). \tag*{(11)} ∣ W ∣ ≤ 4 D 0 + 2 r ∣ L ∣ = 4 D 0 + n 2 32 a 0 ∣ L ∣ e ( R ) . (11)
Define
M = ∑ v ∈ L δ R ( v ) x v . M=\sum_{v\in L}\delta_R(v)x_v. M = v ∈ L ∑ δ R ( v ) x v .
By Lemma 2.4 (1), every vertex has at most k − 1 k-1 k − 1 neighbors in U U U . Therefore e ( U , W ) = ∑ v ∈ W d U ( v ) ≤ ( k − 1 ) ∣ W ∣ e(U,W)=\sum_{v\in W}d_U(v)\le(k-1)|W| e ( U , W ) = ∑ v ∈ W d U ( v ) ≤ ( k − 1 ) ∣ W ∣ . Since L = U ∪ W L=U\cup W L = U ∪ W ,
∑ v ∈ L d L ( v ) x v = ∑ v ∈ U ( d U ( v ) + d W ( v ) ) x v + ∑ v ∈ W ( d U ( v ) + d W ( v ) ) x v ≤ ( k − 1 ) ∑ v ∈ U x v + e ( U , W ) + ( k − 1 ) ∑ v ∈ W x v + ∣ W ∣ ∑ v ∈ W x v ≤ ( k − 1 ) X + ( k − 1 ) ∣ W ∣ + ∣ W ∣ X W . (12) \begin{aligned}
\sum_{v\in L}d_L(v)x_v
&=\sum_{v\in U}(d_U(v)+d_W(v))x_v+\sum_{v\in W}(d_U(v)+d_W(v))x_v\\
&\le(k-1)\sum_{v\in U}x_v+e(U,W)+(k-1)\sum_{v\in W}x_v+|W|\sum_{v\in W}x_v\\
&\le(k-1)X+(k-1)|W|+|W|X_W. \tag*{(12)}
\end{aligned} v ∈ L ∑ d L ( v ) x v = v ∈ U ∑ ( d U ( v ) + d W ( v )) x v + v ∈ W ∑ ( d U ( v ) + d W ( v )) x v ≤ ( k − 1 ) v ∈ U ∑ x v + e ( U , W ) + ( k − 1 ) v ∈ W ∑ x v + ∣ W ∣ v ∈ W ∑ x v ≤ ( k − 1 ) X + ( k − 1 ) ∣ W ∣ + ∣ W ∣ X W . (12)
Here d W ( v ) ≤ ∣ W ∣ d_W(v) \le|W| d W ( v ) ≤ ∣ W ∣ for v ∈ W v \in W v ∈ W and x v ≤ 1 x_v \le1 x v ≤ 1 for v ∈ U v \in U v ∈ U . Using (3) , (6) and (12) , we obtain
M ≤ 2 ∑ v ∈ L d L ( v ) x v − ( q − n ) X + r ∣ L ∣ X ≤ 2 k ( k − 1 ) n X + 2 ( k − 1 ) ∣ W ∣ + 2 ∣ W ∣ X W + r ∣ L ∣ X ≤ 2 k ( k − 1 ) ∣ L ∣ n + 2 ( k − 1 ) ∣ W ∣ + 2 b 1 ∣ W ∣ 2 + 16 a 0 ∣ L ∣ 2 n 2 e ( R ) . (13) \begin{aligned}
M &\le2\sum_{v\in L}d_L(v)x_v-(q-n)X+r|L|X\\
&\le\frac{2k(k-1)}{n}X+2(k-1)|W|+2|W|X_W+r|L|X\\
&\le\frac{2k(k-1)|L|}{n}+2(k-1)|W|+2b_1|W|^2+\frac{16a_0|L|^2}{n^2}e(R). \tag*{(13)}
\end{aligned} M ≤ 2 v ∈ L ∑ d L ( v ) x v − ( q − n ) X + r ∣ L ∣ X ≤ n 2 k ( k − 1 ) X + 2 ( k − 1 ) ∣ W ∣ + 2∣ W ∣ X W + r ∣ L ∣ X ≤ n 2 k ( k − 1 ) ∣ L ∣ + 2 ( k − 1 ) ∣ W ∣ + 2 b 1 ∣ W ∣ 2 + n 2 16 a 0 ∣ L ∣ 2 e ( R ) . (13)
We apply Lemma 2.3 with A = A ∗ A=A_\ast A = A ∗ and B = R B=R B = R . The sets are disjoint and ∣ A ∗ ∣ ≥ k |A_\ast|\ge k ∣ A ∗ ∣ ≥ k . Since x v ≥ 1 / 2 x_v\ge1/2 x v ≥ 1/2 for v ∈ A ∗ v\in A_\ast v ∈ A ∗ ,
∑ v ∈ A ∗ δ R ( v ) ≤ 2 ∑ v ∈ A ∗ δ R ( v ) x v ≤ 2 M . \sum_{v\in A_\ast}\delta_R(v)\le2\sum_{v\in A_\ast}\delta_R(v)x_v\le2M. v ∈ A ∗ ∑ δ R ( v ) ≤ 2 v ∈ A ∗ ∑ δ R ( v ) x v ≤ 2 M .
Thus, using ∣ A ∗ ∣ ≥ ∣ L ∣ / 2 |A_\ast|\ge|L|/2 ∣ A ∗ ∣ ≥ ∣ L ∣/2 , ∣ R ∣ ≤ n |R|\le n ∣ R ∣ ≤ n and (13) ,
e ( R ) ≤ ( k − 1 2 + k ∣ A ∗ ∣ ∑ v ∈ A ∗ δ R ( v ) ) ∣ R ∣ ≤ ( k − 1 ) n 2 + 4 k n ∣ L ∣ M ≤ ( k − 1 ) n 2 + 8 k 2 ( k − 1 ) + 8 k n ∣ W ∣ ∣ L ∣ ( k − 1 + b 1 ∣ W ∣ ) + 64 k a 0 ∣ L ∣ n e ( R ) . (14) \begin{aligned}
e(R)&\le\left(\frac{k-1}{2}+\frac{k}{|A_\ast|}\sum_{v\in A_\ast}\delta_R(v)\right)|R|\\
&\le\frac{(k-1)n}{2}+\frac{4kn}{|L|}M\\
&\le\frac{(k-1)n}{2}+8k^2(k-1)+\frac{8kn|W|}{|L|}(k-1+b_1|W|)+\frac{64ka_0|L|}{n}e(R). \tag*{(14)}
\end{aligned} e ( R ) ≤ ( 2 k − 1 + ∣ A ∗ ∣ k v ∈ A ∗ ∑ δ R ( v ) ) ∣ R ∣ ≤ 2 ( k − 1 ) n + ∣ L ∣ 4 k n M ≤ 2 ( k − 1 ) n + 8 k 2 ( k − 1 ) + ∣ L ∣ 8 k n ∣ W ∣ ( k − 1 + b 1 ∣ W ∣ ) + n 64 k a 0 ∣ L ∣ e ( R ) . (14)
Note that n ∣ L ∣ b 1 ∣ W ∣ 2 = b 0 ∣ W ∣ 2 ≤ b 0 ∣ L ∣ ∣ W ∣ \frac{n}{|L|}b_1|W|^2=b_0|W|^2\le b_0|L||W| ∣ L ∣ n b 1 ∣ W ∣ 2 = b 0 ∣ W ∣ 2 ≤ b 0 ∣ L ∣∣ W ∣ . We conclude that
e ( R ) ≤ ( k − 1 ) n 2 + 8 k 2 ( k − 1 ) + 8 k ( ( k − 1 ) n ∣ L ∣ + b 0 ∣ L ∣ ) ∣ W ∣ + 64 k a 0 ∣ L ∣ n e ( R ) . (15) e(R)\le\frac{(k-1)n}{2}+8k^2(k-1)+8k\left(\frac{(k-1)n}{|L|}+b_0|L|\right)|W|+\frac{64ka_0|L|}{n}e(R). \tag*{(15)} e ( R ) ≤ 2 ( k − 1 ) n + 8 k 2 ( k − 1 ) + 8 k ( ∣ L ∣ ( k − 1 ) n + b 0 ∣ L ∣ ) ∣ W ∣ + n 64 k a 0 ∣ L ∣ e ( R ) . (15)
By (11) and (15) ,
( 1 − θ n ) e ( R ) ≤ ( k − 1 ) n 2 + 8 k 2 ( k − 1 ) + 32 k D 0 ( ( k − 1 ) n ∣ L ∣ + b 0 ∣ L ∣ ) , (1-\theta_n)e(R)\le\frac{(k-1)n}{2}+8k^2(k-1)+32kD_0\left(\frac{(k-1)n}{|L|}+b_0|L|\right), ( 1 − θ n ) e ( R ) ≤ 2 ( k − 1 ) n + 8 k 2 ( k − 1 ) + 32 k D 0 ( ∣ L ∣ ( k − 1 ) n + b 0 ∣ L ∣ ) ,
where θ n = 64 k a 0 ∣ L ∣ n + 256 k a 0 ( ∣ L ∣ n + b 0 ∣ L ∣ 2 n 2 ) . (16) \text{where }\theta_n=64ka_0\frac{|L|}{n}+256ka_0\left(\frac{|L|}{n}+b_0\frac{|L|^2}{n^2}\right). \tag*{(16)} where θ n = 64 k a 0 n ∣ L ∣ + 256 k a 0 ( n ∣ L ∣ + b 0 n 2 ∣ L ∣ 2 ) . (16)
The constants k , ε , α , D 0 , a 0 , b 0 k,\varepsilon,\alpha,D_0,a_0,b_0 k , ε , α , D 0 , a 0 , b 0 are fixed. ∣ L ∣ n → 0 \frac{|L|}{n}\to0 n ∣ L ∣ → 0 implies θ n → 0 \theta_n\to0 θ n → 0 . For large n n n , it holds θ n ≤ 1 / 2 \theta_n\le1/2 θ n ≤ 1/2 . Since 1 ≤ ∣ L ∣ ≤ n 1\le|L|\le n 1 ≤ ∣ L ∣ ≤ n , the right side of (16) is O k , ε ( n ) O_{k,\varepsilon}(n) O k , ε ( n ) .
Therefore, e ( R ) = O k , ε ( n ) e(R)=O_{k,\varepsilon}(n) e ( R ) = O k , ε ( n ) , which implies
r ∣ L ∣ = 16 a 0 ∣ L ∣ n 2 e ( R ) = O k , ε ( ∣ L ∣ / n ) = o ( 1 ) . r|L|=\frac{16a_0|L|}{n^2}e(R)=O_{k,\varepsilon}(|L|/n)=o(1). r ∣ L ∣ = n 2 16 a 0 ∣ L ∣ e ( R ) = O k , ε ( ∣ L ∣/ n ) = o ( 1 ) .
□
Claim 5. δ R ( u ) = 0 \delta_R(u)=0 δ R ( u ) = 0 and U = L U=L U = L . In particular, d L ( u ) = Δ ( G [ L ] ) = k − 1 d_L(u)=\Delta(G[L])=k-1 d L ( u ) = Δ ( G [ L ]) = k − 1 and ∣ L ∣ ≥ k |L|\ge k ∣ L ∣ ≥ k .
Proof. Write d U = d U ( u ) d_U=d_U(u) d U = d U ( u ) , d W = d W ( u ) d_W=d_W(u) d W = d W ( u ) for short. Since u ∈ U u\in U u ∈ U , Lemma 2.4 (1) gives d U ≤ k − 1 d_U\le k-1 d U ≤ k − 1 . In (5) , the neighbors of u u u in U U U contribute at most d U d_U d U to ∑ v ∈ N L ( u ) x v \sum_{v\in N_L(u)}x_v ∑ v ∈ N L ( u ) x v , and those in W W W contribute at most b 1 d W b_1d_W b 1 d W by Claim 2. Moreover, ∣ L ∣ − X ≥ ( 1 − b 1 ) ∣ W ∣ |L|-X\ge(1-b_1)|W| ∣ L ∣ − X ≥ ( 1 − b 1 ) ∣ W ∣ . Hence by (5) ,
q − n ≤ 2 d U + ( 1 + b 1 ) d W − ( 1 − b 1 ) ∣ W ∣ − δ R ( u ) + r ∣ L ∣ , d U ≤ k − 1 , d W ≤ D 0 , ∣ W ∣ ≥ d W . (17) \begin{aligned}
q-n &\le2d_U+(1+b_1)d_W-(1-b_1)|W|-\delta_R(u)+r|L|,\\
d_U&\le k-1,\qquad d_W\le D_0,\qquad|W|\ge d_W. \tag*{(17)}
\end{aligned} q − n d U ≤ 2 d U + ( 1 + b 1 ) d W − ( 1 − b 1 ) ∣ W ∣ − δ R ( u ) + r ∣ L ∣ , ≤ k − 1 , d W ≤ D 0 , ∣ W ∣ ≥ d W . (17) If d U ≤ k − 2 d_U\le k-2 d U ≤ k − 2 , then
q − n ≤ 2 ( k − 2 ) + 2 b 1 d W + r ∣ L ∣ ≤ 2 k − 4 + 2 b 1 D 0 + r ∣ L ∣ = 2 k − 4 + o ( 1 ) , q-n\le2(k-2)+2b_1d_W+r|L|\le2k-4+2b_1D_0+r|L|=2k-4+o(1), q − n ≤ 2 ( k − 2 ) + 2 b 1 d W + r ∣ L ∣ ≤ 2 k − 4 + 2 b 1 D 0 + r ∣ L ∣ = 2 k − 4 + o ( 1 ) , contrary to (6) for large enough n n n . Therefore d U = k − 1 d_U=k-1 d U = k − 1 . By Lemma 2.4 (2), the fact u ∈ U u\in U u ∈ U and d U ( u ) = k − 1 d_U(u)=k-1 d U ( u ) = k − 1 force d W = 0 d_W=0 d W = 0 . By (17) and (6) ,
( 1 − b 1 ) ∣ W ∣ + δ R ( u ) ≤ 2 ( k − 1 ) − ( q − n ) + r ∣ L ∣ < 2 k ( k − 1 ) n + r ∣ L ∣ = o ( 1 ) . (1-b_1)|W|+\delta_R(u)\le2(k-1)-(q-n)+r|L|<\frac{2k(k-1)}{n}+r|L|=o(1). ( 1 − b 1 ) ∣ W ∣ + δ R ( u ) ≤ 2 ( k − 1 ) − ( q − n ) + r ∣ L ∣ < n 2 k ( k − 1 ) + r ∣ L ∣ = o ( 1 ) . Here ∣ W ∣ |W| ∣ W ∣ and δ R ( u ) \delta_R(u) δ R ( u ) are nonnegative integers and 1 − b 1 ≥ 1 / 2 1-b_1\ge1/2 1 − b 1 ≥ 1/2 for large n n n . It follows that ∣ W ∣ = δ R ( u ) = 0 |W|=\delta_R(u)=0 ∣ W ∣ = δ R ( u ) = 0 . This leads to U = L U=L U = L . Thus by Lemma 2.4 (1),
d L ( u ) = Δ ( G [ L ] ) = k − 1 , ∣ L ∣ ≥ k . d_L(u)=\Delta(G[L])=k-1,\qquad|L|\ge k. d L ( u ) = Δ ( G [ L ]) = k − 1 , ∣ L ∣ ≥ k . □
Claim 6. e ( R ) ≤ 1 e(R)\le1 e ( R ) ≤ 1 and d L ( v ) = k − 1 d_L(v)=k-1 d L ( v ) = k − 1 , δ R ( v ) = 0 \delta_R(v)=0 δ R ( v ) = 0 for every v ∈ L v\in L v ∈ L .
Proof. Since U = L U=L U = L , Lemma 2.4 (1) gives d L ( v ) ≤ k − 1 d_L(v)\le k-1 d L ( v ) ≤ k − 1 for every v ∈ L v\in L v ∈ L . Define
σ v = 2 ( k − 1 − d L ( v ) ) + δ R ( v ) ≥ 0 , D = ∑ v ∈ L σ v , ρ = 2 ( k − 1 ) − λ max ( M ) . \sigma_v=2(k-1-d_L(v))+\delta_R(v)\ge0,\qquad D=\sum_{v\in L}\sigma_v,\qquad\rho=2(k-1)-\lambda_{\max}(\mathcal{M}). σ v = 2 ( k − 1 − d L ( v )) + δ R ( v ) ≥ 0 , D = v ∈ L ∑ σ v , ρ = 2 ( k − 1 ) − λ m a x ( M ) . The row sum of M \mathcal{M} M at v v v is 2 d L ( v ) − δ R ( v ) = 2 ( k − 1 ) − σ v 2d_L(v)-\delta_R(v)=2(k-1)-\sigma_v 2 d L ( v ) − δ R ( v ) = 2 ( k − 1 ) − σ v . It is easy to check by the definition of M \mathcal{M} M that M + n I ∣ L ∣ \mathcal{M}+nI_{|L|} M + n I ∣ L ∣ is entrywise positive. So by the
maximum-row-sum inequality, λ max ( M ) ≤ 2 ( k − 1 ) \lambda_{\max}(\mathcal{M}) \le2(k-1) λ m a x ( M ) ≤ 2 ( k − 1 ) , and then ρ ≥ 0 \rho\ge0 ρ ≥ 0 . By (4) , (6) and r ∣ L ∣ = o ( 1 ) r|L|=o(1) r ∣ L ∣ = o ( 1 ) ,
0 ≤ ρ ≤ 2 ( k − 1 ) − ( q − n ) + r ∣ L ∣ < 2 k ( k − 1 ) n + r ∣ L ∣ = o ( 1 ) . (18) 0 \le\rho\le2(k-1)-(q-n)+r|L| < \frac{2k(k-1)}{n}+r|L|=o(1). \tag*{(18)} 0 ≤ ρ ≤ 2 ( k − 1 ) − ( q − n ) + r ∣ L ∣ < n 2 k ( k − 1 ) + r ∣ L ∣ = o ( 1 ) . (18)
Let y > 0 y>0 y > 0 be an eigenvector of M \mathcal{M} M for λ max ( M ) = 2 ( k − 1 ) − ρ \lambda_{\max}(\mathcal{M})=2(k-1)-\rho λ m a x ( M ) = 2 ( k − 1 ) − ρ , normalized by max v ∈ L y v = 1 \max_{v\in L}y_v=1 max v ∈ L y v = 1 . Pick w ∈ L w\in L w ∈ L with y w = 1 y_w=1 y w = 1 . Recall that the row sum ∑ v ∈ L M w v = 2 ( k − 1 ) − σ w \sum_{v\in L}\mathcal{M}_{wv}=2(k-1)-\sigma_w ∑ v ∈ L M w v = 2 ( k − 1 ) − σ w . The eigenvector equation of the row of w w w gives
ρ = σ w + ∑ v ∈ L ∖ { w } M w v ( 1 − y v ) . \rho=\sigma_w+\sum_{v\in L\setminus\{w\}}\mathcal{M}_{wv}(1-y_v). ρ = σ w + v ∈ L ∖ { w } ∑ M w v ( 1 − y v ) .
Every summand on the right is nonnegative and M w v ≥ 1 \mathcal{M}_{wv}\ge1 M w v ≥ 1 , so y v ≥ 1 − ρ y_v\ge1-\rho y v ≥ 1 − ρ for every v v v , which holds for v = w v=w v = w as well. On the other hand, the symmetry of M \mathcal{M} M and its row-sum formula give
( 2 ( k − 1 ) − ρ ) ∑ v ∈ L y v = ∑ v ∈ L ( 2 ( k − 1 ) − σ v ) y v , i.e. ρ ∑ v ∈ L y v = ∑ v ∈ L σ v y v . (2(k-1)-\rho)\sum_{v\in L}y_v=\sum_{v\in L}(2(k-1)-\sigma_v)y_v,\qquad\text{i.e.}\quad\rho\sum_{v\in L}y_v=\sum_{v\in L}\sigma_vy_v. ( 2 ( k − 1 ) − ρ ) v ∈ L ∑ y v = v ∈ L ∑ ( 2 ( k − 1 ) − σ v ) y v , i.e. ρ v ∈ L ∑ y v = v ∈ L ∑ σ v y v .
Since ρ = o ( 1 ) \rho=o(1) ρ = o ( 1 ) , it holds 1 − ρ ≥ 1 / 2 1-\rho\ge1/2 1 − ρ ≥ 1/2 . Therefore
ρ ∣ L ∣ ≥ ρ ∑ v ∈ L y v = ∑ v ∈ L σ v y v ≥ ( 1 − ρ ) D ≥ D / 2 , i.e. ρ ≥ D 2 ∣ L ∣ . (19) \rho|L|\ge\rho\sum_{v\in L}y_v=\sum_{v\in L}\sigma_vy_v\ge(1-\rho)D\ge D/2,\qquad\text{i.e.}\quad\rho\ge\frac{D}{2|L|}. \tag*{(19)} ρ ∣ L ∣ ≥ ρ v ∈ L ∑ y v = v ∈ L ∑ σ v y v ≥ ( 1 − ρ ) D ≥ D /2 , i.e. ρ ≥ 2∣ L ∣ D . (19)
Combining (19) with (18) , we get D = o ( ∣ L ∣ ) D=o(|L|) D = o ( ∣ L ∣ ) .
Let B = { v ∈ L : σ v > 0 } B=\{v\in L:\sigma_v>0\} B = { v ∈ L : σ v > 0 } . Because every positive σ v \sigma_v σ v is an integer, ∣ B ∣ ≤ D |B|\le D ∣ B ∣ ≤ D . By Claim 5 , Δ ( G [ L ] ) = k − 1 \Delta(G[L])=k-1 Δ ( G [ L ]) = k − 1 , so at most ∣ B ∣ + ( k − 1 ) ∣ B ∣ ≤ k D = o ( ∣ L ∣ ) |B|+(k-1)|B|\le kD=o(|L|) ∣ B ∣ + ( k − 1 ) ∣ B ∣ ≤ k D = o ( ∣ L ∣ ) vertices lie in B ∪ N L ( B ) B\cup N_L(B) B ∪ N L ( B ) .
Since n n n is sufficiently large, we can pick a vertex v 0 ∈ L ∖ ( B ∪ N L ( B ) ) v_0\in L\setminus(B\cup N_L(B)) v 0 ∈ L ∖ ( B ∪ N L ( B )) . Thus σ v 0 = 0 \sigma_{v_0}=0 σ v 0 = 0 and σ v = 0 \sigma_v=0 σ v = 0 for every v ∈ N L ( v 0 ) v\in N_L(v_0) v ∈ N L ( v 0 ) . By the definition of σ v \sigma_v σ v , this implies ∣ N L ( v 0 ) ∣ = d L ( v 0 ) = k − 1 |N_L(v_0)|=d_L(v_0)=k-1 ∣ N L ( v 0 ) ∣ = d L ( v 0 ) = k − 1 . It also implies δ R ( v 0 ) = 0 \delta_R(v_0)=0 δ R ( v 0 ) = 0 and δ R ( v ) = 0 \delta_R(v)=0 δ R ( v ) = 0 for v ∈ N L ( v 0 ) v\in N_L(v_0) v ∈ N L ( v 0 ) , which means each vertex in { v 0 } ∪ N L ( v 0 ) \{v_0\}\cup N_L(v_0) { v 0 } ∪ N L ( v 0 ) is adjacent to every vertex of R R R . Note that N L ( v 0 ) ⊆ N ( v 0 ) N_L(v_0)\subseteq N(v_0) N L ( v 0 ) ⊆ N ( v 0 ) , R ⊆ V ( G ) ∖ ( { v 0 } ∪ N L ( v 0 ) ) R\subseteq V(G)\setminus(\{v_0\}\cup N_L(v_0)) R ⊆ V ( G ) ∖ ({ v 0 } ∪ N L ( v 0 )) , and ∣ R ∣ = n − ∣ L ∣ = n − o ( n ) ≥ k + 1 |R|=n-|L|=n-o(n)\ge k+1 ∣ R ∣ = n − ∣ L ∣ = n − o ( n ) ≥ k + 1 for large n n n . By Lemma 2.2 (1) (with ( S , T , u ) (S,T,u) ( S , T , u ) in the lemma be ( N L ( v 0 ) , R , v 0 ) (N_L(v_0),R,v_0) ( N L ( v 0 ) , R , v 0 ) ), we have e ( R ) ≤ 1 e(R)\le1 e ( R ) ≤ 1 .
Now suppose D ≥ 1 D\ge1 D ≥ 1 . By (19) , ρ ≥ D 2 ∣ L ∣ \rho\ge\frac{D}{2|L|} ρ ≥ 2∣ L ∣ D . Using (4) and e ( R ) ≤ 1 e(R)\le1 e ( R ) ≤ 1 ,
q − n ≤ 2 ( k − 1 ) − ρ + r ∣ L ∣ ≤ 2 ( k − 1 ) − 1 2 ∣ L ∣ + 16 a 0 ∣ L ∣ n 2 . q-n\le2(k-1)-\rho+r|L|\le2(k-1)-\frac{1}{2|L|}+\frac{16a_0|L|}{n^2}. q − n ≤ 2 ( k − 1 ) − ρ + r ∣ L ∣ ≤ 2 ( k − 1 ) − 2∣ L ∣ 1 + n 2 16 a 0 ∣ L ∣ .
Together with (6) , this implies
1 2 < 2 k ( k − 1 ) ∣ L ∣ n + 16 a 0 ∣ L ∣ 2 n 2 , (20) \frac{1}{2}<2k(k-1)\frac{|L|}{n}+16a_0\frac{|L|^2}{n^2}, \tag*{(20)} 2 1 < 2 k ( k − 1 ) n ∣ L ∣ + 16 a 0 n 2 ∣ L ∣ 2 , (20)
which is impossible for ∣ L ∣ = o ( n ) |L| = o(n) ∣ L ∣ = o ( n ) . Note that every σ v \sigma_v σ v is a nonnegative integer, and so is D D D . Thus D = 0 D = 0 D = 0 , which immediately implies σ v = 0 \sigma_v = 0 σ v = 0 for every v ∈ L v \in L v ∈ L . Therefore, d L ( v ) = k − 1 d_L(v) = k - 1 d L ( v ) = k − 1 and δ R ( v ) = 0 \delta_R(v) = 0 δ R ( v ) = 0 for every v ∈ L v \in L v ∈ L . □ \square □
Proof of Theorem 3.1 . Write ℓ = ∣ L ∣ \ell= |L| ℓ = ∣ L ∣ . By Claim 5, ℓ ≥ k \ell\ge k ℓ ≥ k . By Claim 6, e ( R ) ≤ 1 e(R) \le1 e ( R ) ≤ 1 . Let G + = G G^+ = G G + = G if e ( R ) = 1 e(R) = 1 e ( R ) = 1 and G + G^+ G + is obtained from R R R by adding an edge in R R R if e ( R ) = 0 e(R) = 0 e ( R ) = 0 . Hence
G + = G [ L ] ∨ ( K 2 ∪ ( n − ℓ − 2 ) K 1 ) G^+ = G[L] \vee(K_2 \cup(n-\ell-2)K_1) G + = G [ L ] ∨ ( K 2 ∪ ( n − ℓ − 2 ) K 1 )
with q ( G ) ≤ q ( G + ) q(G) \le q(G^+) q ( G ) ≤ q ( G + ) . As G [ L ] G[L] G [ L ] is ( k − 1 ) (k-1) ( k − 1 ) -regular by Claim 6, the partition of V ( G ) V(G) V ( G ) into L L L , the two endpoints of the edge, and the remaining vertices is equitable for Q ( G + ) Q(G^+) Q ( G + ) , with quotient
B ℓ = ( n − ℓ + 2 k − 2 2 n − ℓ − 2 ℓ ℓ + 2 0 ℓ 0 ℓ ) . B_\ell=
\begin{pmatrix}
n-\ell+2k-2 & 2 & n-\ell-2 \\
\ell& \ell+2 & 0 \\
\ell& 0 & \ell
\end{pmatrix}. B ℓ = n − ℓ + 2 k − 2 ℓ ℓ 2 ℓ + 2 0 n − ℓ − 2 0 ℓ .
The largest eigenvalue of B ℓ B_\ell B ℓ is q ( G + ) q(G^+) q ( G + ) . Moreover, G + G^+ G + contains the connected spanning graph K ℓ , n − ℓ K_{\ell,n-\ell} K ℓ , n − ℓ , which has Q Q Q -index n n n . Strict edge monotonicity therefore gives q ( G + ) > n q(G^+) > n q ( G + ) > n . Let x = q ( G + ) > n > ℓ + 2 x = q(G^+) > n > \ell+2 x = q ( G + ) > n > ℓ + 2 , we have det ( x I − B ℓ ) = 0 \det(xI-B_\ell) = 0 det ( x I − B ℓ ) = 0 , thus
f ℓ ( x ) : = x 3 − ( n + ℓ + 2 k ) x 2 + ( ( ℓ + 2 ) n + 4 ( k − 1 ) ( ℓ + 1 ) ) x − 2 ℓ ( ( ℓ + 2 ) k − ℓ ) = 0. f_\ell(x) := x^3-(n+\ell+2k)x^2+((\ell+2)n+4(k-1)(\ell+1))x-2\ell((\ell+2)k-\ell) = 0. f ℓ ( x ) := x 3 − ( n + ℓ + 2 k ) x 2 + (( ℓ + 2 ) n + 4 ( k − 1 ) ( ℓ + 1 )) x − 2 ℓ (( ℓ + 2 ) k − ℓ ) = 0.
For sufficiently large n n n , one can check that f ℓ f_\ell f ℓ is increasing on [ n , ∞ ) [n,\infty) [ n , ∞ ) and f ℓ ( n ) < 0 f_\ell(n) < 0 f ℓ ( n ) < 0 . Thus its unique root on [ n , ∞ ) [n,\infty) [ n , ∞ ) is exactly x = q ( G + ) x = q(G^+) x = q ( G + ) .
For ℓ = k \ell= k ℓ = k , G [ L ] G[L] G [ L ] is necessarily K k K_k K k and G + = S n , k + G^+ = S^+_{n,k} G + = S n , k + . Hence f k ( q F ) = 0 f_k(q_F) = 0 f k ( q F ) = 0 , where q F = q ( S n , k + ) q_F = q(S^+_{n,k}) q F = q ( S n , k + ) . By simple calculations,
f ℓ ( q F ) − f k ( q F ) = ( ℓ − k ) [ ( n + 4 k − 4 − q F ) q F − 2 ( ( k − 1 ) ℓ + k ( k + 1 ) ) ] . f_\ell(q_F)-f_k(q_F) = (\ell-k)[(n+4k-4-q_F)q_F-2((k-1)\ell+k(k+1))]. f ℓ ( q F ) − f k ( q F ) = ( ℓ − k ) [( n + 4 k − 4 − q F ) q F − 2 (( k − 1 ) ℓ + k ( k + 1 ))] .
Since n < q F < n + 2 k n < q_F < n+2k n < q F < n + 2 k by Lemma 2.1 , we have ( n + 4 k − 4 − q F ) q F > ( 2 k − 4 ) n (n+4k-4-q_F)q_F > (2k-4)n ( n + 4 k − 4 − q F ) q F > ( 2 k − 4 ) n and 2 ( ( k − 1 ) ℓ + k ( k + 1 ) ) = o ( n ) 2((k-1)\ell+k(k+1)) = o(n) 2 (( k − 1 ) ℓ + k ( k + 1 )) = o ( n ) . If ℓ > k \ell> k ℓ > k , then f ℓ ( q F ) = f ℓ ( q F ) − f k ( q F ) > 0 f_\ell(q_F) = f_\ell(q_F)-f_k(q_F) > 0 f ℓ ( q F ) = f ℓ ( q F ) − f k ( q F ) > 0 . Since f ℓ f_\ell f ℓ is increasing on [ n , ∞ ) [n,\infty) [ n , ∞ ) , it holds q ( G ) ≤ q ( G + ) < q F q(G) \le q(G^+) < q_F q ( G ) ≤ q ( G + ) < q F , which is a contradiction. Therefore, ℓ = k \ell= k ℓ = k and G [ L ] = K k G[L] = K_k G [ L ] = K k . Finally, if e ( R ) = 0 e(R) = 0 e ( R ) = 0 then G = S n , k G = S_{n,k} G = S n , k , whose Q Q Q -index is strictly smaller than q F q_F q F by Lemma 2.1 . Thus, e ( R ) = 1 e(R) = 1 e ( R ) = 1 and G ≅ S n , k + G \cong S^+_{n,k} G ≅ S n , k + . The proof is done. □ \square □
A spectral stability theorem
For any graph H H H , we call a partition of its vertex set V(H)=A\mathbin{\mathaccent\cdot\cup}B a maximum cut of H H H , if e(A,B)=\max_{V(H)=A'\mathbin{\mathaccent\cdot\cup}B'}e(A',B') . Let V_1\mathbin{\mathaccent\cdot\cup}V_2 be a cut of some graph H H H , then for i = 1 , 2 i=1,2 i = 1 , 2 and some vertex v ∈ V i v\in V_i v ∈ V i , every vertex in N V i ( v ) N_{V_i}(v) N V i ( v ) is called an internal neighbor of v v v and every vertex in N V 3 − i ( v ) N_{V_{3-i}}(v) N V 3 − i ( v ) is called a crossing neighbor of v v v . We call edges in E ( H [ V 1 ] ) ∪ E ( H [ V 2 ] ) E(H[V_1])\cup E(H[V_2]) E ( H [ V 1 ]) ∪ E ( H [ V 2 ]) internal edges and edges in E ( H [ V 1 , V 2 ] ) E(H[V_1,V_2]) E ( H [ V 1 , V 2 ]) crossing edges . We define internal nonneighbors, crossing nonneighbors, internal nonedges and crossing nonedges similarly.
Lemma 4.1. Fix k ≥ 3 k\ge3 k ≥ 3 and 0 < τ < 1 / 2 0<\tau<1/2 0 < τ < 1/2 . Let G G G be a W 2 k + 1 W_{2k+1} W 2 k + 1 -free graph on n n n vertices with q ( G ) ≥ n q(G)\ge n q ( G ) ≥ n and Δ ( G ) ≤ ( 1 − τ ) n \Delta(G)\le(1-\tau)n Δ ( G ) ≤ ( 1 − τ ) n . Then there is a maximum cut A\mathbin{\mathaccent\cdot\cup}B of G G G with ∣ A ∣ , ∣ B ∣ ≥ τ n / 2 |A|,|B|\ge\tau n/2 ∣ A ∣ , ∣ B ∣ ≥ τ n /2 and
∣ A ∣ ∣ B ∣ − e ( A , B ) = O k , τ ( n 1 + 1 / k ) , e ( A ) + e ( B ) = O k , τ ( n 1 + 1 / k ) . |A||B|-e(A,B)=O_{k,\tau}(n^{1+1/k}),\qquad e(A)+e(B)=O_{k,\tau}(n^{1+1/k}). ∣ A ∣∣ B ∣ − e ( A , B ) = O k , τ ( n 1 + 1/ k ) , e ( A ) + e ( B ) = O k , τ ( n 1 + 1/ k ) . Moreover, d B ( v a ) ≥ d A ( v a ) d_B(v_a)\ge d_A(v_a) d B ( v a ) ≥ d A ( v a ) and d A ( v b ) ≥ d B ( v b ) d_A(v_b)\ge d_B(v_b) d A ( v b ) ≥ d B ( v b ) for every vertex v a ∈ A v_a\in A v a ∈ A and v b ∈ B v_b\in B v b ∈ B .
Proof. Without loss of generality, we only consider G G G without isolated vertices. By the maximum-row-sum inequality of D ( G ) − 1 Q ( G ) D ( G ) D(G)^{-1}Q(G)D(G) D ( G ) − 1 Q ( G ) D ( G ) (see also [14 , 10 ] ), there is a vertex u ∈ V ( G ) u\in V(G) u ∈ V ( G ) with
q ( G ) ≤ d G ( u ) + 1 d G ( u ) ∑ v ∈ N ( u ) d G ( v ) . q(G)\le d_G(u)+\frac{1}{d_G(u)}\sum_{v\in N(u)}d_G(v). q ( G ) ≤ d G ( u ) + d G ( u ) 1 v ∈ N ( u ) ∑ d G ( v ) .
Set A = N ( u ) A=N(u) A = N ( u ) , B = V ( G ) ∖ A B=V(G)\setminus A B = V ( G ) ∖ A , a = ∣ A ∣ = d G ( u ) a=|A|=d_G(u) a = ∣ A ∣ = d G ( u ) and b = ∣ B ∣ b=|B| b = ∣ B ∣ . Since the right side of the inequation above is at most a + Δ ( G ) a+\Delta(G) a + Δ ( G ) , we have a ≥ q ( G ) − Δ ( G ) ≥ τ n ≥ k a\ge q(G)-\Delta(G)\ge\tau n\ge k a ≥ q ( G ) − Δ ( G ) ≥ τ n ≥ k . Also, b ≥ n − Δ ( G ) ≥ τ n b\ge n-\Delta(G)\ge\tau n b ≥ n − Δ ( G ) ≥ τ n . Apparently,
n ≤ q ( G ) ≤ a + 1 a ∑ v ∈ A d ( v ) = n + 2 e ( A ) + e ( A , B ) − a b a . n\le q(G)\le a+\frac{1}{a}\sum_{v\in A}d(v)=n+\frac{2e(A)+e(A,B)-ab}{a}. n ≤ q ( G ) ≤ a + a 1 v ∈ A ∑ d ( v ) = n + a 2 e ( A ) + e ( A , B ) − ab .
This gives
M : = ∑ a ∈ A ∣ B ∖ N ( a ) ∣ = a b − e ( A , B ) ≤ 2 e ( A ) = O k ( n 1 + 1 / k ) , M:=\sum_{a\in A}|B\setminus N(a)|=ab-e(A,B)\le2e(A)=O_k(n^{1+1/k}), M := a ∈ A ∑ ∣ B ∖ N ( a ) ∣ = ab − e ( A , B ) ≤ 2 e ( A ) = O k ( n 1 + 1/ k ) ,
recalling that G [ A ] G[A] G [ A ] is C 2 k C_{2k} C 2 k -free, so e ( A ) ≤ O ( n 1 + 1 / k ) e(A)\le O(n^{1+1/k}) e ( A ) ≤ O ( n 1 + 1/ k ) . Now applying Lemma 2.3 to A , B A,B A , B , we have
e ( B ) ≤ ( k − 1 2 + k M a ) b = O k , τ ( n 1 + 1 / k ) . e(B)\le\left(\frac{k-1}{2}+\frac{kM}{a}\right)b=O_{k,\tau}(n^{1+1/k}). e ( B ) ≤ ( 2 k − 1 + a k M ) b = O k , τ ( n 1 + 1/ k ) .
Choose a maximum cut A ′ ⊔ B ′ A^{\prime} \sqcup B^{\prime} A ′ ⊔ B ′ . Let a 1 = ∣ A ∩ B ′ ∣ a_1 = |A \cap B^{\prime}| a 1 = ∣ A ∩ B ′ ∣ and b 1 = ∣ B ∩ A ′ ∣ b_1 = |B \cap A^{\prime}| b 1 = ∣ B ∩ A ′ ∣ . We assume a 1 a + b 1 b ≤ 1 \frac{a_1}{a}+\frac{b_1}{b} \le1 a a 1 + b b 1 ≤ 1 since otherwise we can exchange A ′ A^{\prime} A ′ and B ′ B^{\prime} B ′ . Clearly, e ( A ′ , B ′ ) ≤ e ( K [ A , B ] ) − L 0 + e ( A ) + e ( B ) e(A^{\prime},B^{\prime}) \le e(K[A,B]) - L_0 + e(A) + e(B) e ( A ′ , B ′ ) ≤ e ( K [ A , B ]) − L 0 + e ( A ) + e ( B ) , where L 0 = ∣ E ( K [ A , B ] ) ∖ E ( K [ A ′ , B ′ ] ) ∣ L_0 = |E(K[A,B]) \setminus E(K[A^{\prime},B^{\prime}])| L 0 = ∣ E ( K [ A , B ]) ∖ E ( K [ A ′ , B ′ ]) ∣ . Also, e ( K [ A , B ] ) = a b e(K[A,B]) = ab e ( K [ A , B ]) = ab and
L 0 = a 1 ( b − b 1 ) + b 1 ( a − a 1 ) ≥ 1 2 ( b a 1 + a b 1 ) ≥ τ n 2 ( a 1 + b 1 ) . L_0 = a_1(b-b_1)+b_1(a-a_1) \ge\frac{1}{2}(ba_1+ab_1) \ge\frac{\tau n}{2}(a_1+b_1). L 0 = a 1 ( b − b 1 ) + b 1 ( a − a 1 ) ≥ 2 1 ( b a 1 + a b 1 ) ≥ 2 τ n ( a 1 + b 1 ) .
On the other hand, e ( A ′ , B ′ ) ≥ e ( A , B ) = a b − M e(A^{\prime},B^{\prime}) \ge e(A,B) = ab-M e ( A ′ , B ′ ) ≥ e ( A , B ) = ab − M . Hence a b − M ≤ a b − L 0 + e ( A ) + e ( B ) ab-M \le ab-L_0+e(A)+e(B) ab − M ≤ ab − L 0 + e ( A ) + e ( B ) . Therefore,
a 1 + b 1 ≤ 2 τ n L 0 ≤ 2 τ n ( M + e ( A ) + e ( B ) ) = O k , τ ( n 1 k ) . a_1+b_1 \le\frac{2}{\tau n}L_0 \le\frac{2}{\tau n}(M+e(A)+e(B))=O_{k,\tau}\left(n^{\frac{1}{k}}\right). a 1 + b 1 ≤ τ n 2 L 0 ≤ τ n 2 ( M + e ( A ) + e ( B )) = O k , τ ( n k 1 ) .
So to obtain A ′ ⊔ B ′ A^{\prime} \sqcup B^{\prime} A ′ ⊔ B ′ from A ⊔ B A \sqcup B A ⊔ B , we only need to move O k , τ ( n 1 k ) O_{k,\tau}\left(n^{\frac{1}{k}}\right) O k , τ ( n k 1 ) vertices from their partition set to the other one. So we still have ∣ A ′ ∣ , ∣ B ′ ∣ ≥ τ n / 2 |A^{\prime}|,|B^{\prime}| \ge\tau n/2 ∣ A ′ ∣ , ∣ B ′ ∣ ≥ τ n /2 . The change of the vertices will cause the change of e ( A , B ) e(A,B) e ( A , B ) , e ( A ) e(A) e ( A ) and e ( B ) e(B) e ( B ) for at most O k , τ ( n 1 + 1 k ) O_{k,\tau}\left(n^{1+\frac{1}{k}}\right) O k , τ ( n 1 + k 1 ) . So the new cut A ′ ⊔ B ′ A^{\prime} \sqcup B^{\prime} A ′ ⊔ B ′ still satisfies ∣ A ′ ∣ ∣ B ′ ∣ − e ( A ′ , B ′ ) = O k , τ ( n 1 + 1 k ) |A^{\prime}||B^{\prime}|-e(A^{\prime},B^{\prime})=O_{k,\tau}\left(n^{1+\frac{1}{k}}\right) ∣ A ′ ∣∣ B ′ ∣ − e ( A ′ , B ′ ) = O k , τ ( n 1 + k 1 ) and e ( A ′ ) + e ( B ′ ) = O k , τ ( n 1 + 1 k ) e(A^{\prime})+e(B^{\prime})=O_{k,\tau}\left(n^{1+\frac{1}{k}}\right) e ( A ′ ) + e ( B ′ ) = O k , τ ( n 1 + k 1 ) . The "moreover" part is trivial due to the maximality of A ′ ⊔ B ′ A^{\prime} \sqcup B^{\prime} A ′ ⊔ B ′ .
The following theorem can be considered as a stability result, which guarantees a nearly dominating vertex of a W 2 k + 1 W_{2k+1} W 2 k + 1 -free graph if its Q Q Q -index is close to the Q Q Q -index of the extremal construction.
Theorem 4.2. For every fixed integer k ≥ 3 k \ge3 k ≥ 3 and 0 < τ < 1 / 2 0 < \tau< 1/2 0 < τ < 1/2 , there are constants ξ = ξ ( k , τ ) > 0 \xi=\xi(k,\tau)>0 ξ = ξ ( k , τ ) > 0 and N = N ( k , τ ) N=N(k,\tau) N = N ( k , τ ) such that every n n n -vertex W 2 k + 1 W_{2k+1} W 2 k + 1 -free graph G G G with n ≥ N n \ge N n ≥ N and Δ ( G ) ≤ ( 1 − τ ) n \Delta(G) \le(1-\tau)n Δ ( G ) ≤ ( 1 − τ ) n satisfies
q ( G ) ≤ n + 2 ( k − 1 ) − ξ . q(G) \le n+2(k-1)-\xi. q ( G ) ≤ n + 2 ( k − 1 ) − ξ .
We prove the theorem by several claims. Throughout the proof, we consider n n n -vertex W 2 k + 1 W_{2k+1} W 2 k + 1 -free graph G G G with n ≥ N n \ge N n ≥ N and Δ ( G ) ≤ ( 1 − τ ) n \Delta(G) \le(1-\tau)n Δ ( G ) ≤ ( 1 − τ ) n . We will take
c 1 = τ 2 192 , β = c 1 2 τ 16 , c_1=\frac{\tau^2}{192}, \qquad\beta=\frac{c_1^2\tau}{16}, c 1 = 192 τ 2 , β = 16 c 1 2 τ ,
and fix a positive constant γ \gamma γ such that
γ = c 1 2 τ 3 24 k = min { τ 8 , τ 2 96 , β 4 k , c 1 2 τ 3 24 k } . (21) \gamma=\frac{c_1^2\tau^3}{24k}=\min\left\{\frac{\tau}{8},\frac{\tau^2}{96},\frac{\beta}{4k},\frac{c_1^2\tau^3}{24k}\right\}. \tag*{(21)} γ = 24 k c 1 2 τ 3 = min { 8 τ , 96 τ 2 , 4 k β , 24 k c 1 2 τ 3 } . (21)
All three constants depend only on k k k and τ \tau τ , and are independent of n n n . We shall obtain a gap with ξ = c 1 2 τ / 2 \xi=c_1^2\tau/2 ξ = c 1 2 τ /2 . This constant is less than 1. In the following lemmas we first assume q ( G ) ≥ n q(G) \ge n q ( G ) ≥ n and choose a maximum cut A ⊔ B A \sqcup B A ⊔ B as in Lemma 4.1. In particular,
∣ A ∣ , ∣ B ∣ ≥ τ n 2 , M : = ∣ A ∣ ∣ B ∣ − e ( A , B ) = O k , τ ( n 1 + 1 / k ) , (22) |A|, |B| \ge\frac{\tau n}{2}, \qquad M := |A||B| - e(A,B) = O_{k,\tau}(n^{1+1/k}), \tag*{(22)} ∣ A ∣ , ∣ B ∣ ≥ 2 τ n , M := ∣ A ∣∣ B ∣ − e ( A , B ) = O k , τ ( n 1 + 1/ k ) , (22)
and d B ( v a ) ≥ d A ( v a ) d_B(v_a) \ge d_A(v_a) d B ( v a ) ≥ d A ( v a ) and d A ( v b ) ≥ d B ( v b ) d_A(v_b) \ge d_B(v_b) d A ( v b ) ≥ d B ( v b ) for every vertex v a ∈ A v_a \in A v a ∈ A and v b ∈ B v_b \in B v b ∈ B .
Put A 0 = { v ∈ A : ∣ B ∖ N ( v ) ∣ ≤ γ n } A_0 = \{v \in A : |B \setminus N(v)| \le\gamma n\} A 0 = { v ∈ A : ∣ B ∖ N ( v ) ∣ ≤ γ n } , B 0 = { v ∈ B : ∣ A ∖ N ( v ) ∣ ≤ γ n } B_0 = \{v \in B : |A \setminus N(v)| \le\gamma n\} B 0 = { v ∈ B : ∣ A ∖ N ( v ) ∣ ≤ γ n } , Z = V ( G ) ∖ ( A 0 ∪ B 0 ) Z = V(G) \setminus(A_0 \cup B_0) Z = V ( G ) ∖ ( A 0 ∪ B 0 ) , z = ∣ Z ∣ z = |Z| z = ∣ Z ∣ . We also call vertices in A 0 ∪ B 0 A_0 \cup B_0 A 0 ∪ B 0 good vertices. Note that
2 M = ∑ v ∈ A ∣ B ∖ N ( v ) ∣ + ∑ v ∈ B ∣ A ∖ N ( v ) ∣ , 2M = \sum_{v \in A} |B \setminus N(v)| + \sum_{v \in B} |A \setminus N(v)|, 2 M = v ∈ A ∑ ∣ B ∖ N ( v ) ∣ + v ∈ B ∑ ∣ A ∖ N ( v ) ∣ ,
and every vertex in Z Z Z contributes more than γ n \gamma n γ n to this sum. Hence
z ≤ 2 M γ n = O k , τ ( n 1 / k ) . (23) z \le\frac{2M}{\gamma n} = O_{k,\tau}(n^{1/k}). \tag*{(23)} z ≤ γ n 2 M = O k , τ ( n 1/ k ) . (23)
Since z = o ( n ) z = o(n) z = o ( n ) and k ≥ 3 k \ge3 k ≥ 3 , for sufficiently large n n n , we have
∣ A 0 ∣ , ∣ B 0 ∣ ≥ τ n 3 , z 2 = O k , τ ( n 2 / k ) = o ( n ) . (24) |A_0|, |B_0| \ge\frac{\tau n}{3}, \qquad z^2 = O_{k,\tau}(n^{2/k}) = o(n). \tag*{(24)} ∣ A 0 ∣ , ∣ B 0 ∣ ≥ 3 τ n , z 2 = O k , τ ( n 2/ k ) = o ( n ) . (24)
Every good vertex has at least τ n / 2 − γ n \tau n/2 - \gamma n τ n /2 − γ n crossing neighbors, and hence has degree at least β n \beta n β n for all large n n n .
Claim 7. If d G ( v ) ≥ β n d_G(v) \ge\beta n d G ( v ) ≥ β n for some v ∈ V ( G ) v \in V(G) v ∈ V ( G ) , then
d A 0 ( v ) ≤ k − 1 if v ∈ A , d B 0 ( v ) ≤ k − 1 if v ∈ B . d_{A_0}(v) \le k - 1 \quad\text{if } v \in A, \qquad d_{B_0}(v) \le k - 1 \quad\text{if } v \in B. d A 0 ( v ) ≤ k − 1 if v ∈ A , d B 0 ( v ) ≤ k − 1 if v ∈ B . In particular,
Δ ( G [ A 0 ] ) , Δ ( G [ B 0 ] ) ≤ k − 1. \Delta(G[A_0]), \Delta(G[B_0]) \le k - 1. Δ ( G [ A 0 ]) , Δ ( G [ B 0 ]) ≤ k − 1. Proof. We need to prove that every vertex v v v with d G ( v ) ≥ β n d_G(v) \ge\beta n d G ( v ) ≥ β n has at most k − 1 k - 1 k − 1 good internal neighbors. Indeed, since the cut is maximum, v v v has at least d G ( v ) / 2 ≥ β n / 2 d_G(v)/2 \ge\beta n/2 d G ( v ) /2 ≥ β n /2 crossing neighbors. If v v v had k k k good internal neighbors s 1 , … , s k s_1, \ldots, s_k s 1 , … , s k , then v , s 1 , … , s k v, s_1, \ldots, s_k v , s 1 , … , s k would have at least
β n 2 − k γ n ≥ β n 4 > k \frac{\beta n}{2} - k\gamma n \ge\frac{\beta n}{4} > k 2 β n − k γ n ≥ 4 β n > k common crossing neighbors. Choosing any k k k of them and alternating them with s 1 , … , s k s_1, \ldots, s_k s 1 , … , s k gives a C 2 k C_{2k} C 2 k in G [ N ( v ) ] G[N(v)] G [ N ( v )] , which is impossible.
Let x x x be a nonnegative eigenvector of Q ( G ) Q(G) Q ( G ) for q ( G ) q(G) q ( G ) , normalized by max v x v = 1 \max_v x_v = 1 max v x v = 1 . For i = 1 , 2 i = 1, 2 i = 1 , 2 , set X i = ∑ v x v i X_i = \sum_v x_v^i X i = ∑ v x v i .
Claim 8. X 1 ≥ τ n X_1 \ge\tau n X 1 ≥ τ n and τ 2 n ≤ X 2 ≤ n \tau^2 n \le X_2 \le n τ 2 n ≤ X 2 ≤ n .
Proof. Let x u = 1 x_u=1 x u = 1 . The eigenvalue equation at u u u gives
X 1 = ∑ v ∈ V ( G ) x v ≥ ∑ v ∈ N ( u ) x v = q ( G ) − d G ( u ) ≥ n − Δ ( G ) ≥ τ n . X_1=\sum_{v\in V(G)}x_v\ge\sum_{v\in N(u)}x_v=q(G)-d_G(u)\ge n-\Delta(G)\ge\tau n. X 1 = v ∈ V ( G ) ∑ x v ≥ v ∈ N ( u ) ∑ x v = q ( G ) − d G ( u ) ≥ n − Δ ( G ) ≥ τ n . By Cauchy–Schwarz inequality,
X 2 = ∑ v ∈ V ( G ) x v 2 ≥ 1 n ( ∑ v ∈ V ( G ) x v ) 2 ≥ τ 2 n . X_2=\sum_{v\in V(G)}x_v^2\ge\frac{1}{n}\left(\sum_{v\in V(G)}x_v\right)^2\ge\tau^2n. X 2 = v ∈ V ( G ) ∑ x v 2 ≥ n 1 v ∈ V ( G ) ∑ x v 2 ≥ τ 2 n . On the other hand, since x v ≤ 1 x_v\le1 x v ≤ 1 for v ∈ V ( G ) v\in V(G) v ∈ V ( G ) , it holds X 2 = ∑ v x v 2 ≤ ∑ v 1 = n X_2=\sum_v x_v^2\le\sum_v1=n X 2 = ∑ v x v 2 ≤ ∑ v 1 = n . The claim is done. □ \square □
Claim 9. For v ∈ A 0 ∪ B 0 v\in A_0\cup B_0 v ∈ A 0 ∪ B 0 , x v ≥ c 1 x_v\ge c_1 x v ≥ c 1 .
Proof. Since z = o ( n ) z=o(n) z = o ( n ) and x v ≤ 1 x_v\le1 x v ≤ 1 for v ∈ V ( G ) v\in V(G) v ∈ V ( G ) , by Claim 8, for large n n n ,
∑ v ∈ A 0 ∪ B 0 x v ≥ τ n − z ≥ τ n 2 . \sum_{v\in A_0\cup B_0}x_v\ge\tau n-z\ge\frac{\tau n}{2}. v ∈ A 0 ∪ B 0 ∑ x v ≥ τ n − z ≥ 2 τ n . By symmetry we may suppose ∑ v ∈ A 0 x v ≥ τ n / 4 \sum_{v\in A_0}x_v\ge\tau n/4 ∑ v ∈ A 0 x v ≥ τ n /4 . For any v ∈ B 0 v\in B_0 v ∈ B 0 , at most γ n \gamma n γ n vertices of A A A are nonneighbors of v v v . The eigenvalue equation gives
( q ( G ) − d G ( v ) ) x v = ∑ w ∈ N ( v ) x w ≥ ∑ w ∈ A 0 x w − γ n ≥ ( τ 4 − γ ) n . (q(G)-d_G(v))x_v=\sum_{w\in N(v)}x_w\ge\sum_{w\in A_0}x_w-\gamma n\ge\left(\frac{\tau}{4}-\gamma\right)n. ( q ( G ) − d G ( v )) x v = w ∈ N ( v ) ∑ x w ≥ w ∈ A 0 ∑ x w − γ n ≥ ( 4 τ − γ ) n . Consequently, by (21) and q ( G ) ≤ 2 Δ ( G ) < 2 n q(G)\le2\Delta(G)<2n q ( G ) ≤ 2Δ ( G ) < 2 n , for v ∈ B 0 v\in B_0 v ∈ B 0 ,
x v ≥ τ / 4 − γ 2 ≥ τ 16 . x_v\ge\frac{\tau/4-\gamma}{2}\ge\frac{\tau}{16}. x v ≥ 2 τ /4 − γ ≥ 16 τ . Using ∣ B 0 ∣ ≥ τ n / 3 |B_0|\ge\tau n/3 ∣ B 0 ∣ ≥ τ n /3 yields ∑ v ∈ B 0 x v ≥ τ 2 n / 48 \sum_{v\in B_0}x_v\ge\tau^2n/48 ∑ v ∈ B 0 x v ≥ τ 2 n /48 . Applying the same eigenvalue estimate to each v ∈ A 0 v\in A_0 v ∈ A 0 gives
x v ≥ τ 2 / 48 − γ 2 ≥ τ 2 192 . x_v\ge\frac{\tau^2/48-\gamma}{2}\ge\frac{\tau^2}{192}. x v ≥ 2 τ 2 /48 − γ ≥ 192 τ 2 . Since c 1 = τ 2 / 192 c_1=\tau^2/192 c 1 = τ 2 /192 , we have proved that for v ∈ A 0 ∪ B 0 v\in A_0\cup B_0 v ∈ A 0 ∪ B 0 , x v ≥ c 1 x_v\ge c_1 x v ≥ c 1 . □ \square □
Let I 0 = ∑ u v ∈ E ( G [ A 0 ] ) ∪ E ( G [ B 0 ] ) ( x u + x v ) 2 I_0=\sum_{uv\in E(G[A_0])\cup E(G[B_0])}(x_u+x_v)^2 I 0 = ∑ uv ∈ E ( G [ A 0 ]) ∪ E ( G [ B 0 ]) ( x u + x v ) 2 .
Claim 10. q ( G ) ≤ n + I 0 X 2 + o k , τ ( 1 ) q(G)\le n+\frac{I_0}{X_2}+o_{k,\tau}(1) q ( G ) ≤ n + X 2 I 0 + o k , τ ( 1 ) .
Proof. Using the identity
x T Q ( J ) x = ∑ u v ∈ E ( J ) ( x u + x v ) 2 x^{\mathsf{T}}Q(J)x=\sum_{uv\in E(J)}(x_u+x_v)^2 x T Q ( J ) x = uv ∈ E ( J ) ∑ ( x u + x v ) 2
for any graph J J J , we have
x T Q ( G ) x = x T Q ( K [ A , B ] ) x + ∑ u v ∈ E ( G [ A ] ) ∪ E ( G [ B ] ) ( x u + x v ) 2 − ∑ u ∈ A , v ∈ B u v ∉ E ( G ) ( x u + x v ) 2 . (25) \begin{aligned}
x^{\mathsf{T}}Q(G)x={}&x^{\mathsf{T}}Q(K[A,B])x+
\sum_{uv\in E(G[A])\cup E(G[B])}(x_u+x_v)^2\\
&-\sum_{\substack{u\in A,\ v\in B\\uv\notin E(G)}}(x_u+x_v)^2. \tag*{(25)}
\end{aligned} x T Q ( G ) x = x T Q ( K [ A , B ]) x + uv ∈ E ( G [ A ]) ∪ E ( G [ B ]) ∑ ( x u + x v ) 2 − u ∈ A , v ∈ B uv ∈ / E ( G ) ∑ ( x u + x v ) 2 . (25)
Note that x T Q ( K [ A , B ] ) x ≤ n X 2 x^{\mathsf{T}}Q(K[A,B])x\le nX_2 x T Q ( K [ A , B ]) x ≤ n X 2 as Q ( K [ A , B ] ) Q(K[A,B]) Q ( K [ A , B ]) has largest eigenvalue n n n . Let Z l o w = { v ∈ Z : d G ( v ) < β n } Z_{\mathrm{low}}=\{v\in Z:d_G(v)<\beta n\} Z low = { v ∈ Z : d G ( v ) < β n } , z 0 = ∣ Z l o w ∣ z_0=|Z_{\mathrm{low}}| z 0 = ∣ Z low ∣ . We now consider the terms in (24).
Since ( x u + x v ) 2 ≤ 4 (x_u+x_v)^2\le4 ( x u + x v ) 2 ≤ 4 , all internal edges with one endpoint in Z l o w Z_{\mathrm{low}} Z low and the other in A 0 ∪ B 0 A_0\cup B_0 A 0 ∪ B 0 contribute at most 4 β n z 0 4\beta nz_0 4 β n z 0 . For any v ∈ Z l o w v\in Z_{\mathrm{low}} v ∈ Z low , at least
τ n 3 − d G ( v ) ≥ ( τ 3 − β ) n ≥ τ n 4 \frac{\tau n}{3}-d_G(v)\ge\left(\frac{\tau}{3}-\beta\right)n\ge\frac{\tau n}{4} 3 τ n − d G ( v ) ≥ ( 3 τ − β ) n ≥ 4 τ n
good vertices are crossing nonneighbors of v v v . Each of these missing edges contributes at least c 1 2 c_1^2 c 1 2 to the negative sum by Claim 9. Thus the total negative contribution of all crossing nonedges with one endpoint in Z l o w Z_{\mathrm{low}} Z low and the other in A 0 ∪ B 0 A_0\cup B_0 A 0 ∪ B 0 is at least c 1 2 τ n z 0 / 4 = 4 β n z 0 c_1^2\tau nz_0/4=4\beta nz_0 c 1 2 τ n z 0 /4 = 4 β n z 0 . Together with the positive contribution of the internal edges with one endpoint in Z l o w Z_{\mathrm{low}} Z low and the other in A 0 ∪ B 0 A_0\cup B_0 A 0 ∪ B 0 we counted before, we now have the total contribution at most 4 β n z 0 − 4 β n z 0 = 0 4\beta nz_0-4\beta nz_0=0 4 β n z 0 − 4 β n z 0 = 0 .
The remaining internal edges not counted by I 0 I_0 I 0 but by (24) are of two types. Those with one endpoint in A 0 ∪ B 0 A_0\cup B_0 A 0 ∪ B 0 and the other in Z ∖ Z l o w Z\setminus Z_{\mathrm{low}} Z ∖ Z low contribute at most 4 ( k − 1 ) z 4(k-1)z 4 ( k − 1 ) z by Claim 7. Those with both endpoints in Z Z Z contribute at most 4 ( z 2 ) ≤ 2 z 2 4\binom{z}{2}\le2z^2 4 ( 2 z ) ≤ 2 z 2 . All other terms from missing crossing edges are nonpositive. Consequently (24) yields
q ( G ) X 2 ≤ n X 2 + I 0 + 4 ( k − 1 ) z + 2 z 2 . q(G)X_2\le nX_2+I_0+4(k-1)z+2z^2. q ( G ) X 2 ≤ n X 2 + I 0 + 4 ( k − 1 ) z + 2 z 2 .
Using (22), (23) and Claim 8, we conclude
q ( G ) ≤ n + I 0 X 2 + o ( 1 ) . (26) q(G)\le n+\frac{I_0}{X_2}+o(1). \tag*{(26)} q ( G ) ≤ n + X 2 I 0 + o ( 1 ) . (26)
Indeed the omitted error is bounded by
4 ( k − 1 ) z + 2 z 2 X 2 = O k , τ ( n 1 / k − 1 + n 2 / k − 1 ) = o k , τ ( 1 ) . \frac{4(k-1)z+2z^2}{X_2}
=O_{k,\tau}\left(n^{1/k-1}+n^{2/k-1}\right)=o_{k,\tau}(1). X 2 4 ( k − 1 ) z + 2 z 2 = O k , τ ( n 1/ k − 1 + n 2/ k − 1 ) = o k , τ ( 1 ) .
Proof of Theorem 4.2. If q ( G ) < n q(G)<n q ( G ) < n , the desired inequality is immediate. Assume q ( G ) ≥ n q(G)\ge n q ( G ) ≥ n . Suppose first that Δ ( G [ A 0 ] ) , Δ ( G [ B 0 ] ) ≤ k − 2 \Delta(G[A_0]),\Delta(G[B_0])\le k-2 Δ ( G [ A 0 ]) , Δ ( G [ B 0 ]) ≤ k − 2 . Since ( x u + x v ) 2 ≤ 2 ( x u 2 + x v 2 ) (x_u+x_v)^2\le2(x_u^2+x_v^2) ( x u + x v ) 2 ≤ 2 ( x u 2 + x v 2 ) ,
I 0 ≤ 2 ( k − 2 ) ∑ v ∈ A 0 ∪ B 0 x v 2 ≤ 2 ( k − 2 ) X 2 . I_0\le2(k-2)\sum_{v\in A_0\cup B_0}x_v^2\le2(k-2)X_2. I 0 ≤ 2 ( k − 2 ) v ∈ A 0 ∪ B 0 ∑ x v 2 ≤ 2 ( k − 2 ) X 2 .
By Claim 10,
q ( G ) ≤ n + 2 ( k − 2 ) + o ( 1 ) = n + 2 ( k − 1 ) − 2 + o ( 1 ) , q(G)\le n+2(k-2)+o(1)=n+2(k-1)-2+o(1), q ( G ) ≤ n + 2 ( k − 2 ) + o ( 1 ) = n + 2 ( k − 1 ) − 2 + o ( 1 ) ,
which gives the required fixed gap for large n n n . Otherwise, by symmetry and Claim 7, there is a vertex u ∈ A 0 u\in A_0 u ∈ A 0 with exactly k − 1 k-1 k − 1 neighbors in A 0 A_0 A 0 . Put
T = B 0 ∩ N ( u ) ∩ ⋂ v ∈ N A 0 ( u ) N ( v ) . T=B_0\cap N(u)\cap\bigcap_{v\in N_{A_0}(u)}N(v). T = B 0 ∩ N ( u ) ∩ v ∈ N A 0 ( u ) ⋂ N ( v ) .
Both u u u and all vertices in N A 0 ( u ) N_{A_0}(u) N A 0 ( u ) are good, so
∣ B 0 ∖ T ∣ ≤ k γ n . (27) |B_0\setminus T|\le k\gamma n. \tag*{(27)} ∣ B 0 ∖ T ∣ ≤ k γ n . (27)
Since ∣ B 0 ∣ ≥ τ n / 3 |B_0|\ge\tau n/3 ∣ B 0 ∣ ≥ τ n /3 and k γ ≤ β / 4 < τ / 12 k\gamma\le\beta/4<\tau/12 k γ ≤ β /4 < τ /12 , we have ∣ T ∣ ≥ τ n / 4 ≥ k + 1 |T|\ge\tau n/4\ge k+1 ∣ T ∣ ≥ τ n /4 ≥ k + 1 for all large n n n . The sets N A 0 ( u ) N_{A_0}(u) N A 0 ( u ) , T T T and the vertex u u u therefore satisfy the hypotheses of Lemma 2.2 (1). It follows that e ( T ) ≤ 1 e(T)\le1 e ( T ) ≤ 1 . By Claim 7 and (26),
e ( B 0 ) ≤ e ( T ) + ( k − 1 ) ∣ B 0 ∖ T ∣ ≤ 1 + k ( k − 1 ) γ n . e(B_0)\le e(T)+(k-1)|B_0\setminus T|\le1+k(k-1)\gamma n. e ( B 0 ) ≤ e ( T ) + ( k − 1 ) ∣ B 0 ∖ T ∣ ≤ 1 + k ( k − 1 ) γ n .
Using the degree bound in G [ A 0 ] G[A_0] G [ A 0 ] and ( x u + x v ) 2 ≤ 2 ( x u 2 + x v 2 ) (x_u+x_v)^2\le2(x_u^2+x_v^2) ( x u + x v ) 2 ≤ 2 ( x u 2 + x v 2 ) , we have
I 0 ≤ 2 ( k − 1 ) ∑ v ∈ A 0 x v 2 + 4 e ( B 0 ) ≤ 2 ( k − 1 ) X 2 − 2 ( k − 1 ) ∑ v ∈ B 0 x v 2 + 4 + 4 k ( k − 1 ) γ n . (28) \begin{aligned}
I_0&\le2(k-1)\sum_{v\in A_0}x_v^2+4e(B_0)\\
&\le2(k-1)X_2-2(k-1)\sum_{v\in B_0}x_v^2+4+4k(k-1)\gamma n. \tag*{(28)}
\end{aligned} I 0 ≤ 2 ( k − 1 ) v ∈ A 0 ∑ x v 2 + 4 e ( B 0 ) ≤ 2 ( k − 1 ) X 2 − 2 ( k − 1 ) v ∈ B 0 ∑ x v 2 + 4 + 4 k ( k − 1 ) γ n . (28)
On the other hand, Claim 9 and (23) imply
∑ v ∈ B 0 x v 2 ≥ c 1 2 ∣ B 0 ∣ ≥ c 1 2 τ n 3 . \sum_{v\in B_0}x_v^2\ge c_1^2|B_0|\ge\frac{c_1^2\tau n}{3}. v ∈ B 0 ∑ x v 2 ≥ c 1 2 ∣ B 0 ∣ ≥ 3 c 1 2 τ n .
Combining this with (27), Claim 8 and Claim 10, we obtain
q ( G ) ≤ n + 2 ( k − 1 ) − 2 ( k − 1 ) c 1 2 τ 3 + 4 k ( k − 1 ) γ τ 2 + o ( 1 ) = n + 2 ( k − 1 ) − ( k − 1 ) c 1 2 τ 2 + o ( 1 ) , \begin{aligned}
q(G)\le n+2(k-1)-\frac{2(k-1)c_1^2\tau}{3}+\frac{4k(k-1)\gamma}{\tau^2}+o(1) \\
&= n + 2(k-1) - \frac{(k-1)c_1^2\tau}{2} + o(1),
\end{aligned} q ( G ) ≤ n + 2 ( k − 1 ) − 3 2 ( k − 1 ) c 1 2 τ + τ 2 4 k ( k − 1 ) γ + o ( 1 ) = n + 2 ( k − 1 ) − 2 ( k − 1 ) c 1 2 τ + o ( 1 ) ,
where the last equality uses γ = c 1 2 τ 3 / ( 24 k ) \gamma= c_1^2\tau^3/(24k) γ = c 1 2 τ 3 / ( 24 k ) . Since k k k , τ \tau τ and all constants have been fixed before n → ∞ n \to\infty n → ∞ , by increasing N ( k , τ ) N(k,\tau) N ( k , τ ) if necessary we obtain in either case
q ( G ) ≤ n + 2 ( k − 1 ) − ξ , ξ = c 1 2 τ 2 > 0. q(G) \le n + 2(k-1) - \xi, \qquad\xi= \frac{c_1^2\tau}{2} > 0. q ( G ) ≤ n + 2 ( k − 1 ) − ξ , ξ = 2 c 1 2 τ > 0.
This proves the theorem.
Proof of Theorem 1.1
Proof of Theorem 1.1. Assume that Theorem 1.1 is false. Since S n , k + S^+_{n,k} S n , k + is W 2 k + 1 W_{2k+1} W 2 k + 1 -free, by Lemma 2.1 , there are arbitrarily large integers n n n and n n n -vertex W 2 k + 1 W_{2k+1} W 2 k + 1 -free graphs G ≇ S n , k + G \not\cong S^+_{n,k} G ≅ S n , k + such that
n + 2 ( k − 1 ) − 2 k ( k − 1 ) n < q ( S n , k + ) ≤ q ( G ) . n + 2(k-1) - \frac{2k(k-1)}{n} < q(S^+_{n,k}) \le q(G). n + 2 ( k − 1 ) − n 2 k ( k − 1 ) < q ( S n , k + ) ≤ q ( G ) .
We first show that
n − 1 − Δ ( G ) n ⟶ 0. (29) \frac{n-1-\Delta(G)}{n} \longrightarrow0. \tag*{(29)} n n − 1 − Δ ( G ) ⟶ 0. (29)
Indeed, fix any 0 < τ < 1 / 2 0 < \tau< 1/2 0 < τ < 1/2 . By Theorem 4.2 , for all sufficiently large n n n , if Δ ( G ) ≤ ( 1 − τ ) n \Delta(G) \le(1-\tau)n Δ ( G ) ≤ ( 1 − τ ) n , q ( G ) ≤ n + 2 ( k − 1 ) − ξ ( k , τ ) q(G) \le n + 2(k-1) - \xi(k,\tau) q ( G ) ≤ n + 2 ( k − 1 ) − ξ ( k , τ ) , where ξ ( k , τ ) > 0 \xi(k,\tau)>0 ξ ( k , τ ) > 0 does not depend on n n n . This contradicts the preceding lower bound on q ( G ) q(G) q ( G ) when n n n is sufficiently large. Thus Δ ( G ) > ( 1 − τ ) n \Delta(G)>(1-\tau)n Δ ( G ) > ( 1 − τ ) n for every fixed τ > 0 \tau>0 τ > 0 small enough. Since Δ ( G ) ≤ n − 1 \Delta(G)\le n-1 Δ ( G ) ≤ n − 1 , this proves (28).
Now fix ε = 1 / 4 \varepsilon=1/4 ε = 1/4 and use the notations before:
α = ε 2 k , L = L G ( ε n ) , U = L G ( n − 1 − α n ) , δ ( v ) = n − 1 − d G ( v ) . \alpha=\frac{\varepsilon}{2k}, \qquad L=L_G(\varepsilon n), \qquad U=L_G(n-1-\alpha n), \qquad\delta(v)=n-1-d_G(v). α = 2 k ε , L = L G ( ε n ) , U = L G ( n − 1 − α n ) , δ ( v ) = n − 1 − d G ( v ) .
Choose a vertex u u u of maximum degree in G G G . Equation (28) gives
δ ( u ) = n − 1 − Δ ( G ) = o ( n ) . \delta(u)=n-1-\Delta(G)=o(n). δ ( u ) = n − 1 − Δ ( G ) = o ( n ) .
Since α > 0 \alpha>0 α > 0 is fixed, for all sufficiently large n n n we have δ ( u ) ≤ α n \delta(u)\le\alpha n δ ( u ) ≤ α n , that is, u ∈ U u\in U u ∈ U . We may also require n ≥ N 0 ( k , ε ) n\ge N_0(k,\varepsilon) n ≥ N 0 ( k , ε ) . All hypotheses of Lemma 2.4 (3) are therefore satisfied, which gives
d L ( u ) ≤ D 0 = ⌈ ( k − 1 ) ( 4 / ε ) k ⌉ . d_L(u)\le D_0=\left\lceil(k-1)(4/\varepsilon)^k\right\rceil. d L ( u ) ≤ D 0 = ⌈ ( k − 1 ) ( 4/ ε ) k ⌉ .
Every vertex of L L L is either u u u , a neighbor of u u u in L L L , or a nonneighbor of u u u . The number of nonneighbors of u u u is at most δ ( u ) \delta(u) δ ( u ) . Therefore,
∣ L ∣ ≤ 1 + d L ( u ) + δ ( u ) ≤ 1 + D 0 + o ( n ) = o ( n ) . |L| \le1 + d_L(u) + \delta(u) \le1 + D_0 + o(n) = o(n). ∣ L ∣ ≤ 1 + d L ( u ) + δ ( u ) ≤ 1 + D 0 + o ( n ) = o ( n ) .
We can now apply Theorem 3.1 to G G G with this fixed ε \varepsilon ε . It follows that G ≅ S n , k + G \cong S^+_{n,k} G ≅ S n , k + for all sufficiently large n n n , contradicting our choice of G G G . Thus q ( G ) ≤ q ( S n , k + ) q(G) \le q(S^+_{n,k}) q ( G ) ≤ q ( S n , k + ) for every sufficiently large n n n -vertex W 2 k + 1 W_{2k+1} W 2 k + 1 -free graph G G G , and the equality case follows from Theorem 3.1 by the same argument.
Concluding remarks
In this paper, we show that q ( G ) ≤ q ( S n , k + ) q(G) \le q(S^+_{n,k}) q ( G ) ≤ q ( S n , k + ) , with equality if and only if G ≅ S n , k + G \cong S^+_{n,k} G ≅ S n , k + , for any n n n -vertex W 2 k + 1 W_{2k+1} W 2 k + 1 -free graph G G G when n n n is large enough and k ≥ 3 k \ge3 k ≥ 3 . However, for k = 2 k = 2 k = 2 , the problem is still open. Our proof does not work because Lemma 2.2 fails for k = 2 k = 2 k = 2 and the extremal construction is totally different.
For integers a , b ≥ 2 a,b \ge2 a , b ≥ 2 , let H a , b H_{a,b} H a , b be the graph obtained from K a , b K_{a,b} K a , b by adding a maximum matching to each of its partition sets. To be more specific,
H a , b : = ( ⌊ a 2 ⌋ K 2 ∪ ( a − 2 ⌊ a 2 ⌋ ) K 1 ) ∨ ( ⌊ b 2 ⌋ K 2 ∪ ( b − 2 ⌊ b 2 ⌋ ) K 1 ) . H_{a,b}:=\left(\left\lfloor\frac{a}{2}\right\rfloor K_2\cup\left(a-2\left\lfloor\frac{a}{2}\right\rfloor\right)K_1\right)\vee\left(\left\lfloor\frac{b}{2}\right\rfloor K_2\cup\left(b-2\left\lfloor\frac{b}{2}\right\rfloor\right)K_1\right). H a , b := ( ⌊ 2 a ⌋ K 2 ∪ ( a − 2 ⌊ 2 a ⌋ ) K 1 ) ∨ ( ⌊ 2 b ⌋ K 2 ∪ ( b − 2 ⌊ 2 b ⌋ ) K 1 ) .
If a a a and b b b are both even numbers, H a , b = a 2 K 2 ∨ b 2 K 2 H_{a,b}=\frac{a}{2}K_2\vee\frac{b}{2}K_2 H a , b = 2 a K 2 ∨ 2 b K 2 . One can check that q ( H a , b ) = a + b + 2 q(H_{a,b})=a+b+2 q ( H a , b ) = a + b + 2 in this case. We give the following conjecture.
Conjecture 6.1. There is a constant N N N such that, for any n ≥ N n\ge N n ≥ N , every n n n -vertex W 5 W_5 W 5 -free graph G G G satisfies q ( G ) ≤ q ( H 2 , n − 2 ) q(G)\le q(H_{2,n-2}) q ( G ) ≤ q ( H 2 , n − 2 ) . For odd n n n , the equality holds if and only if G ≅ H 2 , n − 2 G\cong H_{2,n-2} G ≅ H 2 , n − 2 . For even n n n , the equality holds if and only if G ≅ H a , b G\cong H_{a,b} G ≅ H a , b for some positive even numbers a a a and b b b with a + b = n a+b=n a + b = n .
Declaration of generative AI use
During the research and preparation of this manuscript, the authors used ChatGPT (OpenAI) to explore possible proof strategies, check mathematical arguments and calculations, and improve the organization and language of the manuscript. The authors critically reviewed and revised the AI-assisted material and take full responsibility for the mathematical correctness and content of the paper.
Acknowledgements
This work was supported by National Natural Science Foundation of China (Grant No. 12401455, 12571369) and the Stability Support Program for Basic Research (Grant No. WZJC202601001).