Exact Solution to an Extremal Problem on Graphic Sequences with a Realization Containing Every 2-Tree on k Vertices.

A simple 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. [Acta Math. Sin. Engl. Ser., 25, 795–802 (2009)] proved that if k ≥ 2, n ≥ and π = (d1,...,dn) is a graphic sequence with , then p 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 Sós. In this paper, we investigate an analogue problem for 2-trees and prove that if k ≥ 3 is an integer with k = i (mod3), π = (d1,...,dn is a graphic sequence with , then π has a realization containing every 2-tree on k vertices. Moreover, the lower bound max is the best possible. This result implies a conjecture due to [Discrete Math. Theor. Comput. Sci., 17(3), 315–326 (2016)]. [ABSTRACT FROM AUTHOR]