On the potential number of Kr+1 - E(H)

摘要

A graphic sequence pi = (d(1),d(2), ..., d(n)) is potentially K-m - E(H)-graphic if there exists a realization of pi containing K-m - E(H) as a subgraph, where H is a subgraph of K-m and K-m - E(H) refers to the graph obtained from K-m by removing the edge set E(H). Let sigma(K-m - E(H), n) be the smallest even integer such that every n-term graphic sequence it with sigma(pi) >= sigma(K-m - E(H), n) is potentially Km - E(H)-graphic, where sigma( pi) = d(1)+d(2)+...+ d(n). In this paper, we determine the value sigma(Kr+1 - E(H), n) for n >= 3r + 7, r +1 >= k >= 7 and j >= 6, where H is a graph on k vertices and j edges which contains a graph K-3 boolean OR K-1(,3) but contains none of C-4, Z(4) or P-3 (P-k is a path of length k and Z(4) is referred to as K-4 E(P-2)), which solves an open problem due to Lai and Hu (7).