Graphic sequences that have a realization with large clique number

摘要

We prove that for k greater than or equal to 5, every (2k + 2)-element graphic sequence of positive terms with sum at least 4k(k - 1) can be realized by a graph containing Kk+1. Also, this bound is sharp. Furthermore, for 2k + 3 less than or equal to n less than or equal to k(5k - 11)/(2k - 4), we construct a graphic n-element positive sequence with sum (2k - 4)(2k 1) + 2(n - 1) that has no realization containing Kk+1 This construction partially answers a question of Erdos et al. in the negative. (C) 2000 John Wiley & Sons, Inc. [References: 12]