Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Degree powers in graphs with forbidden subgraphs. | Degree powers in graphs with forbidden subgraphs Bela Bollobás and Vladimir Nikiforov Submitted Jan 27 2004 Accepted Jun 10 2004 Published Jun 25 2004 MR Subject Classifications 05C35 Abstract For every real p 0 and simple graph G set f p G X d u uEV G and let d r p n be the maximum of f p G taken over all Kr 1 -free graphs G of order n. We prove that if 0 p r then d r p n f p Tr n where Tr n is the r-partite Turan graph of order n. For every p r vVr and n large we show that d p n r 1 e f p Tr n for some e e r 0. Our results settle two conjectures of Caro and Yuster. 1 Introduction Our notation and terminology are standard see . 1 . Caro and Yuster 3 introduced and investigated the function f p G X dP u u V G where p 1 is integer and G is a graph. Writing d r p n for the maximum value of f p G taken over all Kr. 1-free graphs G of order n Caro and Yuster stated that for every p 1 d r p n f p Tr n 1 Department of Mathematical Sciences University of Memphis Memphis TN 38152 USA Trinity College Cambridge CB2 1TQ UK Research supported in part by DARPA grant F33615-01-C-1900. THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 R42 1 where Tr n is the r-partite Turan graph of order n. Although true for p 2 r 2 simple examples show that 1 fails for every fixed r 2 and all sufficiently large p and n this was observed by Schelp 4 . A natural problem arises given r 2 determine those real values p 0 for which equality 1 holds. Furthermore determine the asymptotic value of ộ r p n for large n. In this note we essentially answer these questions. In Section 2 we prove that 1 holds whenever 0 p r and n is large. Next in Section 3 we describe the asymptotic structure of Kr 1-free graphs G of order n such that f p G ộ r p n . We deduce that if p r V2 and n is large then ộ r p n 1 e f p Tr n for some E E r 0. This disproves Conjecture in 3 . In particular r ộ r p n r 1 pe np 1 _ p 1 e holds for large n and therefore for any fixed r 2 ộ r p n rỉí . f p Tr n grows exponentially in
