科研之友
微信
新浪微博
Facebook
分享链接
摘要
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 pi be an n-element graphic sequence and sigma(pi) be the sum of the terms in pi, that is, the degree sum. Let H be a graph. We wish to determine the smallest m such that any n-term graphic sequence pi having sigma(pi) >= m has some realization containing H as a subgraph. Denote this value m by sigma(H, n). For an arbitrarily chosen H, we construct a graphic sequence pi*(H, n) such that sigma(pi*(H, n)) 2 <= sigma(H, n). Furthermore, we conjecture that equality holds in general, as this is the case for all choices of H where sigma(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.
- 出版日期2009
