Discrete Mathematics & Theoretical Computer Science, Vol 17, No 3 (2016)

Font Size:  Small  Medium  Large

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=K3, 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 π=(d1,…,dn) 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 / 2k2+19 / 2k and π=(d1,…,dn) is a graphic sequence with ∑i=1n di>(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≥2k2-k and π=(d1,…,dn) is a graphic sequence with ∑i=1n di> 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