Study On Potentially Complete N-partite Graphic Sequences And Its Algorithm

Define G is a simple graph,the vertex set is V?G?= {v₁,v₂,…,v_n},the degree of v_i is d_i,i = 1,2,…,n,and ?=?d₁,d₂,…,d_n?is defined as the degree sequences of G.The set of all sequences ? =?d₁,d₂,…,d_n?of non-negative,non-increasing integers is denoted by NS_n.A sequence ?? NS_n is said to be graphic if it is the degree sequence of a simple graph G on n vertices,and the graph G is called a realization of ?.The set of all positive graphic sequences in NS_n is denoted,by GS_n.Given a graph H,a graphic sequence ?is said to be potentially H-graphic,if there is a realization of ? containing H as a subgraph.For ? ? NS_n,denote ????= d₁ + d₂ + … + d_n,the symbol ??H,n?is the smallest even integer that everv positive sequence ? ? GS_n with????? ??H,n?is potentially H-graphic.In the following,K₁r,s is the k₁×k₂×…×k_r+1 complete?r + 1?-partite graph,which k₁ = k₂ = …= k_r =1,k_r+1= s,xy means y cnsecutive terms,each equal to x.This thesis mainly studied:1.On potentially F_1³,4,graphic sequences,proposed the condition that ?is potentially K_1³,4,graphic sequences when n? 7,??GS_n,then made a short proof of the corresponding extremum problem with the conclusion,next designed and implemented a visualization judging system which can check whether a degree sequence is graphic and potentially K_1³,4 graphic sequences.2?On potentially K_1³,s graphic sequences,proposed the sufficient condition that ? is potentially K_1⁴,s graphic sequences when s ? 1,n ? 13s-4,? ? GS_n.Through the two lemma,we get the codition that ? is potentially K1⁴,s graphic sequences when d_4s+6 ? 3 and a broad that ? is potentially K_1r,s,graphic sequences,finally we get a sufficient condition that ? is potentially K_1⁴,s graphic sequences.