On Potentially K_r+1-E(G)-graphic Sequences

Let G be a subgraph of the complete graph Kr+1 on r+1 vertices and Kr+1-E(G) be the graph obtained from Kr+1 by deleting all edges of G. A non-increasing sequenceπ= (d1,d2,…,dn) of nonnegative integers is said to be potentially Kr+1-E(G)-graphic if it is realizable by a graph on n vertices containing Kr+1-E(G) as a subgraph. In this paper, we give characterizations forπ= (d1,d2,…,dn) to be potentially Kr+1-E(G)-graphic for G=K2,2K2,P2,3K2,K3,P3,K1,3 and K2 U P2, which are analogous to Erdos-Gallai char-acterization using a system of inequalities. Moreover, we also characterize the potentially K2,s (that is Ks+2-E(K2∪Ks))-graphic sequences, where Kr,s is the r×s complete bipar-tite graph. These characterizations partially answer two problems, one by Lai (Czechoslovak Math. J.,59(2009),1059-1075), find a characterization for a sequenceπ∈NSn to be poten-tially Kr+1- E(G)-graphic. And the other by Li and Yin (Adv. Math.,33(2004),273-283),find a characterization for a sequenceπ∈GSn to be potentially Kr,s-graphic for s≥r≥1.