On the potentially Pk-graphic sequences

A nonincreasing sequence π of n nonnegative integers is said to be graphic if it is the degree sequence of a simple graph G of order n and G is called a realization of π. A graph G of order n is said to have property Pk if it contains a clique of size k as a subgraph. An n-term graphic sequence π is said to be potentially (res. forcibly)Pk-graphic if it has a realization having (res. all its realizations have) property Pk. It is well known that, if tk−1 (n) is the Turán number, then tk−1 (n) is the smallest number such that each graph G of order n with edge number ε(G) ⩾ tk−1(n) + 1 has property Pk. The Turán theorem states that tk−1(n) = (2n) − t(n − k + 1 − r)/2, where n = t(k − 1) + r, 0 ⩽ r < k − 1. In terms of graphic sequences, 2(tk − 1 (n) + 1) is the smallest even number such that each graphic sequence π = (d1,d2,…,dn) with σ(π) = d1, + d2 + … + dn ⩾ 2(tk−1(n) + 1) is forcibly Pk-graphic. In 1991, Erdös et al. [1] considered a variation of this classical extremal problem: determine the smallest even number σ(k, n) such that each graphic sequence π = (d1, d2, …, dn) with d1 ⩾ d2 ⩾ … ⩾ dn ⩾ 1 and σ(π) ⩾ σ (k, n) is potentially Pk- graphic. They gave a lower bound of σ(k, n), i.e., σ(k, n) ⩾ (k − 2)(2n − k + 1) + 2 and conjectured that the lower bound is the exact value of σ(k, n). In this paper, we prove the upper bound σ(k, n) ⩽ 2n(k − 2) + 2 for n ⩾ 2k − 1.