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)|=2 n-3.A non-increasing sequence π=(d1,...,dn) o...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)|=2 n-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≥9/2 k^22+19/2 k and π=(d1,...,dn) is a graphic sequence with∑i=1^n di>(k-2)n,then π 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.In this paper,we investigate an analogue problem for 2-trees and prove that if k≥3 is an integer with k≡i(mod 3),n≥ 20[k/3] 2+31[k/3]+12 and π=(d1,...,dn) is a graphic sequence with ∑i=1^n di>max{k-1)(n-1), 2 [2 k/3] n-2 n-[2 k/3] 2+[2 k/3]+1-(-1)i}, then π has a realization containing every 2-tree on k vertices.Moreover,the lower bound max{(k-1)(n-1), 2[2 k/3]n-2 n-[2 k/3] 2+[2 k/3]+1-(-1)i}is the best possible.This result implies a conjecture due to [Discrete Math.Theor.Comput.Sci.,17(3),315-326(2016)].展开更多
基金Supported by Hainan Provincial Natural Science Foundation(Grant No.118QN252)National Natural Science Foundation of China(Grant No.11961019)。
文摘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)|=2 n-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≥9/2 k^22+19/2 k and π=(d1,...,dn) is a graphic sequence with∑i=1^n di>(k-2)n,then π 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.In this paper,we investigate an analogue problem for 2-trees and prove that if k≥3 is an integer with k≡i(mod 3),n≥ 20[k/3] 2+31[k/3]+12 and π=(d1,...,dn) is a graphic sequence with ∑i=1^n di>max{k-1)(n-1), 2 [2 k/3] n-2 n-[2 k/3] 2+[2 k/3]+1-(-1)i}, then π has a realization containing every 2-tree on k vertices.Moreover,the lower bound max{(k-1)(n-1), 2[2 k/3]n-2 n-[2 k/3] 2+[2 k/3]+1-(-1)i}is the best possible.This result implies a conjecture due to [Discrete Math.Theor.Comput.Sci.,17(3),315-326(2016)].
