Graphic Sequences And M-trees

A graph G is a m-ttee if either G is the complete graph on m+1vertices,or G has a vertex v whose neighborhood is a clique of order m and the graph obtained by removing v from G is a k-tree.Clearly,1-tree is the usual tree.A graph G has the property Pkm if it contains every m-tree on k vertices. 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 and G is a realization of π.A graphic sequence π is potentially Pkm-grapic if it has a realization having the property Pkm.An extremal problem on potentially Pkm-graphic sequences is considered as follows:determine the minimum positive integer p such that for each graphic sequence π=(d1,..,,dn),ifn∑i=1>p, then π is potentially Pkm-graphic.This p is denoted by σ(Pkm,n).This kind of extremal problems was firstly introduced by Erdos et al and Gould et al,which is a variattion of the classical Turan numbers of extremal graph theory in the degree sequences of graphs.For m-1,Yin and Li (Acta Mathematica Sinica, English Series,25(2009)795-802)proved that if k≥2,n≥9/2k2+19/2k, then σ(Pk1,n)=(k-2)n.This is also a variattion of a conjecture due to Erdos and Sos.In this paper,we investigate the problem for the case of m:2.In this thesis,we obtain the following results:1.Give a characterize of m-trees.2.Prove that if k≥3and n≥20[k/3]2+31[k/3]+12,then σ(Pk2,n)=max[(k-1)(n-1),2[2k/3]n-2n][2k/3]2+[2k/3]+1-(-1)i},where k≡i(mod3).