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: A Tur´n Type Problem Concerning the Powers of the a Degrees of a Graph. | A Turán Type Problem Concerning the Powers of the Degrees of a Graph Yair Caro and Raphael Yuster 1 Department of Mathematics University of Haifa-ORANIM Tivon 36006 Israel. AMS Subject Classification 05C35 05C07 primary . Submitted April 18 2000 Accepted August 30 2000 Abstract For a graph G whose degree sequence is d1 . dn and for a positive integer p let ep G 72 1 dp. For a fixed graph H let tp n H denote the maximum value of ep G taken over all graphs with n vertices that do not contain H as a subgraph. Clearly t1 n H is twice the Turan number of H. In this paper we consider the case p 1. For some graphs H we obtain exact results for some others we can obtain asymptotically tight upper and lower bounds and many interesting cases remain open. 1 Introduction All graphs considered here are finite undirected and have no loops or multiple edges. For the standard graph-theoretic notations the reader is referred to 1 . For a graph G whose degree sequence is d1 . dn let ep G A 1 dp. Clearly e1 G 2e G . Recently several papers were published concerning the problem of maximizing e2 G over all graphs having n vertices and m edges. See . 2 3 9 4 10 . In this line of research no restriction is imposed on the structure of G. Along the spirit of Turán Theory we consider the problem of finding the maximum of ep G over the class of graphs which contain no copy of prescribed forbidden e-mail yairc@ le-mail raphy@ 1 THE ELECTRONIC .JOURNAL OF COMBINATORICS 7 2000 R47 2 subgraphs. For a fixed graph H let tp n H denote the maximum value of ep G taken over all graphs with n vertices that do not contain H as a subgraph. Clearly t1 n H 2t n H where t n H is the Turan Number of H. The Turan number t n H is one of the most studied parameters in Graph Theory. Many interesting and non-trivial results give either exact values or asymptotically tight upper and lower bounds for t n H . For example the classic result of Turan from which Turán Theory has emerged .
