On the maximal number of certain subgraphs inK
r
-free graphs |
| |
Authors: | Ervin Györi János Pach Miklós Simonovits |
| |
Institution: | (1) Mathematical Institute of the Hungarian Academy of Sciences, P.O.B. 127, 1364 Budapest, Hungary |
| |
Abstract: | Given two graphsH andG, letH(G) denote the number of subgraphs ofG isomorphic toH. We prove that ifH is a bipartite graph with a one-factor, then for every triangle-free graphG withn verticesH(G) H(T
2(n)), whereT
2(n) denotes the complete bipartite graph ofn vertices whose colour classes are as equal as possible. We also prove that ifK is a completet-partite graph ofm vertices,r > t, n max(m, r – 1), then there exists a complete (r – 1)-partite graphG* withn vertices such thatK(G) K(G*) holds for everyK
r
-free graphG withn vertices. In particular, in the class of allK
r
-free graphs withn vertices the complete balanced (r – 1)-partite graphT
r–1(n) has the largest number of subgraphs isomorphic toK
t
(t < r),C
4,K
2,3. These generalize some theorems of Turán, Erdös and Sauer.Dedicated to Paul Turán on his 80th Birthday |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|