【作者】 胡黎莉；

【导师】 赖春晖；

【作者基本信息】 漳州师范学院 ， 基础数学， 2008， 硕士

【摘要】 设G是简单图,其顶点集为V（G）={v₁,v₂,…,v_n},d_i为v_i的度,i=1,2,…,n.则π=（d₁,…,d_n）称为图G的度序列.设π=（d₁,…,d_n）是一非增的非负整数序列,若π是某个图G的度序列,则π称为可图的,G称为π的一个实现.对于给定的图H,称序列π=（d₁,…,d_n）是蕴含H可图的,如果π存在一个实现包含子图H.K_k,C_k,P_k分别表示k阶完全图,圈长为k的圈和路长为k的路.K_Υ-1—H(H是K_Υ+1的子图)表示从Υ+1阶完全图中删去H的边集.本文主要研究度序列中蕴含H可图序列的刻划问题,得到了以下结果:1、完全解决了蕴含K₅—E₃可图序列的刻划问题,E₃表示5个顶点3条边的图.2、刻划了蕴含K₅—C₄,K₅—P₄,K₅—Y₄和K₅—Z₄-可图序列,其中,Z₄表示K₄—P₂,Y₄表示5个顶点3个叶子的树.3、刻划了蕴含R₃⁶可图序列,R_kⁿ表示n个顶点的k正则图.更多还原

【Abstract】 Given a simple graph G,let V（G）= {v₁,v₂,...,v_n} be the vertex set of G, and let d_i be the degree of v_i,i = 1,2,...,n.Thenπ=（d₁,...,d_n）is called the degree sequence of G.Letπ=（d₁,...,d_n）be a non-increasing nonnegative integer sequence,πis said to be graphic if it is the degree sequence of a simple graph G and G is called a realization ofπ.For given a graph H,a graphic sequenceπ=（d₁,d₂,...,d_n）is said to be potentially H-graphic if there exists a realization ofπcontaining H as a subgraph.Let K_k,C_k and P_k denote a complete graph on k vertices,a cycle on k vertices and a path on k + 1 vertices,respectively.K_r+1- H is the graph obtained from K_r+1by removing the edges set E（H）where H is a subgraph of K_r+1.In this thesis,we focus on considering the characterizations on potentially H-graphic sequences in degree sequences,and get the following results:1、The characterizations on the potentially K₅- E₃-graphic sequences is given, where E₃ denotes graphs on 5 vertices and 3 edges.2、We characterize the potentially K₅ - C₄,K₅ - P₄,K₅ -Y₄ and K₅ - Z₄-graphic sequences where Z₄ is K₄ - P₂ and Y₄ is a tree on 5 vertices and 3 leaves.3、We also characterize the potentially R₃⁶-graphic sequences where R_kⁿ denotes a k-regular graph of order n.更多还原