An extremal problem on graphic sequences with a realization containing every l-tree on k vertices

摘要

A graph G is a l-tree if G = Kl+1, or G has a vertex v whose neighborhood is a clique of order t, and G - v is a l-tree. 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 (2009) proved that if k = 2, n = 9/2 k(2) + 19/2k 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 1-tree (the usual tree) on k vertices. Moreover, the lower bound (k - 2)n is the best possible. This is a variation of a conjecture due to Erdos and Sos. Recently, Zeng and Yin (2016) investigated an analogue extremal problem for 2-trees and prove that if k = 3, n = 2k(2) - k and pi = (d(1 ), . . . , d(n)) is a graphic sequence with Sigma(n)(i=1) d(i ) 4k-5/3 n, then pi has a realization containing every 2-tree on k vertices. Moreover, the lower bound 4k-5/3 n is almost the best possible. In this paper, we consider the most general case l = 3 and prove that if l = 3, k = l + 1, n = 2k(2) - lk + k and pi = (d(1 ), . . . , d(n)) is a graphic sequence with Sigma(n )(i=1)d(i) 2lk-l-3/l+1 n, then pi has a realization containing every l-tree on k vertices. We also show that the lower bound 2lk-l-3/l+1 n is almost the best possible. (C) 2018 Elsevier Inc. All rights reserved.