论文部分内容阅读
设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的路.Kr+1-H(H是Kr+1的子图)表示从r+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、刻划了蕴含R63可图序列,Rnk表示n个顶点的k正则图.