Stability for large forbidden subgraphs |
| |
Authors: | Vladimir Nikiforov |
| |
Affiliation: | Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152 |
| |
Abstract: | In this note we strengthen the stability theorem of Erd?s and Simonovits. Write Kr(s1, …, sr) for the complete r‐partite graph with classes of sizes s1, …, sr and Tr(n) for the r‐partite Turán graph of order n. Our main result is: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with e(G)>(1?1/r?ε)n2/2 satisfies one of the conditions: - (a) G contains a $K_{r+1} (lfloor c,mbox{ln},n rfloor,ldots,lfloor c,mbox{ln},n rfloor,lceil n^{{1}-sqrt{c}}rceil)In this note we strengthen the stability theorem of Erd?s and Simonovits. Write Kr(s1, …, sr) for the complete r‐partite graph with classes of sizes s1, …, sr and Tr(n) for the r‐partite Turán graph of order n. Our main result is: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with e(G)>(1?1/r?ε)n2/2 satisfies one of the conditions:
- (a) G contains a $K_{r+1} (lfloor c,mbox{ln},n rfloor,ldots,lfloor c,mbox{ln},n rfloor,lceil n^{{1}-sqrt{c}}rceil)$;
- (b) G differs from Tr(n) in fewer than (ε1/3+c1/(3r+3))n2 edges.
Letting µ(G) be the spectral radius of G, we prove also a spectral stability theorem: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with µ(G)>(1?1/r?ε)n satisfies one of the conditions: - (a) G contains a $K_{r+1}(lfloor c,mbox{ln},nrfloor,ldots,lfloor c,mbox{ln},nrfloor,lceil n^{1-sqrt{c}}rceil)$;
- (b) G differs from Tr(n) in fewer than (ε1/4+c1/(8r+8))n2 edges.
© 2009 Wiley Periodicals, Inc. J Graph Theory 62: 362–368, 2009 |
| |
Keywords: | stability forbidden subgraph r‐partite subgraph spectral radius |
|
|