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

摘要

A graph G is a 2-tree ifG=K3, or G has a vertexv of degree 2, whose neighbors are adjacent, andG-v is a 2-tree. Clearly, if Gis a 2-tree on n vertices, then|E(G)|=2n-3. A non-increasing sequenceπ=(d1,…,dn) ofnonnegative integers is a graphic sequence if it is realizableby a simple graph G on n vertices. Yin andLi (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 graphicsequence with ∑i=1ndi>(k-2)n, then π has arealization containing every tree on k vertices as asubgraph. Moreover, the lower bound (k-2)n is the bestpossible. This is a variation of a conjecture due to Erd?s andSós. In this paper, we investigate an analogue extremal problemfor 2-trees and prove that if k≥3,n≥2k2-k andπ=(d1,…,dn) is a graphicsequence with ∑i=1ndi> 4kn / 3 -5n / 3, thenπ has a realization containing every 2-tree onk vertices as a subgraph. We also show that the lowerbound 4kn / 3 -5n / 3 is almostthe best possible.