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

作者：Zeng, De-Yan; Yin, Jian-Hua^*

来源：Applied Mathematics and Computation, 2018, 337: 487-493.

DOI：10.1016/j.amc.2018.05.055

• Degree sequences
• Graphic sequences
• Realization
• l-trees

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.

• 出版日期2018-11-15
• 单位海南大学