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