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

*De-Yan Zeng, Jian-Hua Yin*

#### Abstract

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 |E(G)|=2n-3. A non-increasing sequence π=(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 13;802) proved that if k≥2, n≥ 9 / 2k^{2}+19 / 2k and π=(d_{1},…,d_{n}) is a graphic sequence with ∑_{i=1}^{n}d_{i}>(k-2)n, then π 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 Erdős and Sós. In this paper, we investigate an analogue extremal problem for 2-trees and prove that if k≥3, n≥2k^{2}-k and π=(d_{1},…,d_{n}) is a graphic sequence with ∑_{i=1}^{n}d_{i}> 4kn / 3 -5n / 3, then π 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.Full Text: PDF PostScript