A GENERAL LOWER BOUND FOR POTENTIALLY H-GRAPHIC SEQUENCES

摘要

We consider a variation of the classical Turan-type extremal problem as introduced by Erdos, Jacobson, and Lehel in [Graphs realizing the same degree sequences and their respective clique numbers, in Graph Theory, Combinatorics, and Applications, Vol. 1, Wiley, New York, 1991, pp. 439-449]. Let π be an n-element graphic sequence and σ(π) be the sum of the terms in π, that is, the degree sum. Let H be a graph. We wish to determine the smallest m such that any n-term graphic sequence π having σ(π) ≥ m has some realization containing H as a subgraph. Denote this value m by σ(H, n). For an arbitrarily chosen H, we construct a graphic sequence π~* (H, n) such that σ(π~*(H,n)) + 2 ≤ σ(H,n). Furthermore, we conjecture that equality holds in general, as this is the case for all choices of H where σ(H, n) is currently known. We support this conjecture by examining those graphs that are the complement of triangle-free graphs and showing that the conjecture holds despite the wide variety of structure in this class. We will conclude with a brief discussion of a connection between potentially H-graphic sequences and H-saturated graphs of minimum size.