An Erdős-Stone Type Conjecture for Graphic Sequences

We consider a variation of the classical Turán-type extremal problem as introduced by Erdős, Jacobson and Lehel in [Erdős, P., M. Jacobson, and J. Lehel, Graphs realizing the same degree sequence and their respective clique numbers, Graph Theory, Combinatorics and Applications, 1, 1991, ed. Alavi, Chartrand, Oellerman and Schwenk, 439–449]. Let π be an n-element graphic sequence and let H be a graph. We wish to determine the smallest even integer m such that any n-term graphic sequence π having degree sum at least 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 ) whose degree sum plus two is at least σ ( 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.