A generalization of Turán's theorem |
| |
| Authors: | Benny Sudakov Tibor Szab H Van Vu |
| |
| Institution: | Benny Sudakov,Tibor Szabó,H. Van Vu |
| |
| Abstract: | In this paper, we obtain an asymptotic generalization of Turán's theorem. We prove that if all the non‐trivial eigenvalues of a d‐regular graph G on n vertices are sufficiently small, then the largest Kt‐free subgraph of G contains approximately (t ? 2)/(t ? 1)‐fraction of its edges. Turán's theorem corresponds to the case d = n ? 1. © 2005 Wiley Periodicals, Inc. J Graph Theory |
| |
| Keywords: | extremal graph theory Turá n's theorem spectra of graphs |
|
|
