Graphic Sequences with a Realization Containing a Friendship Graph.
Michael J. Ferrara, Ronald J. Gould, John R. Schmitt · 2007
Abstract. An integer sequence pi 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 pi. Given a graph H, and a graphic sequence pi we say that pi is potentially H-graphic if there is some realization of pi 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 = Km1 ∪ Km2 ∪ · · · ∪ Kmk when n is a sufficiently large integer. This is accomplished by determining σ(Kj +kK2, n) where j and k are arbitrary positive integers, and considering the case where j = m − 2k and m = mi. 1.