Potentially K_m-e graphical degree sequences
Qin Huang · 2002
In this paper we consider a variation of the classical extremal problems. Let S be an n-element graphical sequence,and σ(S) be the sum of the terms in S.Let G be a graph.The problem is to determine the smallest m such that any n-term graphical sequence S having σ(S)≥m has a realization containing G as a subgraph.Denote this value m by σ(G,n).We showσ(Km-e,n) ≥ n (2m-5)- (m-2)2+2 for m+n is even and n≥m≥4; when m+n is even, σ(Km-e,n) ≥ n (2m-5)- (m-3)(m-1) +2 for m+n is odd and n≥m≥4. By Lai[10], the equality holds for n≥m=4.