On a characterization for a graphic sequence to be potentially Kr+1 - E(G)-graphic

摘要

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 pi = (d(1), d(2),.., d(n),) 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 pi = (d(1), d(2),...,d(n)) to be potentially Kr+1 E(G)-graphic for G = 3K(2), K-3, P-3, K-1,3 and K-2 U P-2, which are analogous to Erdos-Gallai characterization using a system of inequalities. These characterizations partially answer one problem due to Lai and Hu [10].