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.