On a class of degenerate extremal graph problems |
| |
Authors: | Ralph J Faudree Miklós Simonovits |
| |
Institution: | 1. Mathematical Institute of the Hungarian Academy of Sciences, Hungary 2. Department of Mathematics, Memphis State University, 38152, Memphis, Tennessee, USA 3. Department of Analysis I, E?tv?s University, H-1088, Budapest, Hungary
|
| |
Abstract: | Given a class ? of (so called “forbidden”) graphs, ex (n, ?) denotes the maximum number of edges a graphG n of ordern can have without containing subgraphs from ?. If ? contains bipartite graphs, then ex (n, ?)=O(n 2?c ) for somec>0, and the above problem is calleddegenerate. One important degenerate extremal problem is the case whenC 2k , a cycle of 2k vertices, is forbidden. According to a theorem of P. Erd?s, generalized by A. J. Bondy and M. Simonovits 32, ex (n, {C 2k })=O(n 1+1/k ). In this paper we shall generalize this result and investigate some related questions. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|