Jiong Sheng LI, Jian Hua YIN
Let
σ(
k,n) be the smallest even integer such that each
n-term positive graphic sequence with term sum at least
σ(
k,n) can be realized by a graph containing a clique of
k+1 vertices.Erd?s et al.(Graph Theory,1991,439-449) conjectured that
σ(
k,n)=(
k-1)(2
n-
k)+2.Li et al.(Science in China,1998,510-520) proved that the conjecture is true for
k≥5 and
n ≥ (
?k/2) + 3,and raised the problem of determining the smallest integer
N(
k) such that the conjecture holds for
n≥
N(
k).They also determined the values of
N(
k) for 2≤
k≤7,and proved that for
k≥8.In this paper,we determine the exact values of
σ(
k,n) for
n≥2
k+3 and
k≥6.Therefore,the problem of determining
σ(
k,n) is completely solved.In addition,we prove as a corollary that
for
k≥6.