An extremal problem for a graphic sequence to have a realization containing every 2-tree with prescribed size

作者：Zeng, De-Yan; Yin, Jian-Hua^*

来源：Discrete Mathematics and Theoretical Computer Science, 2016, 17(3): 315-326.

• degree sequences
• graphic sequences
• realization
• 2-trees

A graph G is a 2-tree if G = K-3, or G has a vertex v of degree 2, whose neighbors are adjacent, and G v is a 2-tree. Clearly, if G is a 2-tree on n vertices, then vertical bar E(G)vertical bar = 2n - 3. A non- increasing sequence pi = (d(1),...,d(n)) of nonnegative integers is a graphic sequence if it is realizable by a simple graph G on n vertices. Yin and Li (Acta Mathematica Sinica, English Series, 25(2009) 795- 802) proved that if k >= 2, n >= 9/2k(2) + 19/2 k and pi = (d(1),... d(n)) is a graphic sequence with Sigma(n)(i=1) d(i) > (k - 2)n, then pi has a realization containing every tree on k vertices as a subgraph. Moreover, the lower bound (k 2) n is the best possible. This is a variation of a conjecture due to Erdos and Sos. In this paper, we investigate an analogue extremal problem for 2-trees and prove that if k >= 3, n >= 2 k(2) - k and pi = (d(1),..., d(n)) is a graphic sequence with Sigma(n)(i=1) d(i) > 4kn/3 - 5n/3, then pi has a realization containing every 2-tree on k vertices as a subgraph. We also show that the lower bound 4kn/3 - 5n/3 is almost the best possible.

• 出版日期2016
• 单位海南大学