Graphic Sequences with a Realization Containing a Union of Cliques

摘要

An integer sequence π is said to be graphic if it is the degree sequence of some simple graph G. In this case we say that G is a realization of π. Given a graph H, and a graphic sequence π we say that π is potentially H-graphic if there is some realization of π that contains H as a subgraph. We define σ(H,n) to be the minimum even integer such that every graphic sequence with sum at least σ(H,n) is potentially H-graphic. In this paper, we determine σ(H,n) for the graph H = K m1∪ K m2∪...∪ K m k when n is a sufficiently large integer. This is accomplished by determining σ(K j + kK 2,n) where j and k are arbitrary positive integers, and considering the case where j = m ? 2k and m = ∑ m i .