节点文献
关于蕴含H可图序列的刻划
On Potentially H-graphic Sequences
【作者】 胡黎莉;
【导师】 赖春晖;
【作者基本信息】 漳州师范学院 , 基础数学, 2008, 硕士
【摘要】 设G是简单图,其顶点集为V(G)={v1,v2,…,vn},di为vi的度,i=1,2,…,n.则π=(d1,…,dn)称为图G的度序列.设π=(d1,…,dn)是一非增的非负整数序列,若π是某个图G的度序列,则π称为可图的,G称为π的一个实现.对于给定的图H,称序列π=(d1,…,dn)是蕴含H可图的,如果π存在一个实现包含子图H.Kk,Ck,Pk分别表示k阶完全图,圈长为k的圈和路长为k的路.KΥ-1—H(H是KΥ+1的子图)表示从Υ+1阶完全图中删去H的边集.本文主要研究度序列中蕴含H可图序列的刻划问题,得到了以下结果:1、完全解决了蕴含K5—E3可图序列的刻划问题,E3表示5个顶点3条边的图.2、刻划了蕴含K5—C4,K5—P4,K5—Y4和K5—Z4-可图序列,其中,Z4表示K4—P2,Y4表示5个顶点3个叶子的树.3、刻划了蕴含R36可图序列,Rkn表示n个顶点的k正则图.
【Abstract】 Given a simple graph G,let V(G)= {v1,v2,...,vn} be the vertex set of G, and let di be the degree of vi,i = 1,2,...,n.Thenπ=(d1,...,dn)is called the degree sequence of G.Letπ=(d1,...,dn)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π=(d1,d2,...,dn)is said to be potentially H-graphic if there exists a realization ofπcontaining H as a subgraph.Let Kk,Ck and Pk denote a complete graph on k vertices,a cycle on k vertices and a path on k + 1 vertices,respectively.Kr+1- H is the graph obtained from Kr+1by removing the edges set E(H)where H is a subgraph of Kr+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 K5- E3-graphic sequences is given, where E3 denotes graphs on 5 vertices and 3 edges.2、We characterize the potentially K5 - C4,K5 - P4,K5 -Y4 and K5 - Z4-graphic sequences where Z4 is K4 - P2 and Y4 is a tree on 5 vertices and 3 leaves.3、We also characterize the potentially R36-graphic sequences where Rkn denotes a k-regular graph of order n.
- 【网络出版投稿人】 漳州师范学院 【网络出版年期】2008年 12期
- 【分类号】O157.5
- 【下载频次】15