论文部分内容阅读
假定G是简单图，其顶点集V={v1,v2,…,vn},其中vi的度为di,i=1,2,…,n，则G以π=(d1,d2,…,dn)为其度序列。若非增非负整数序列π是某个简单图G的度序列，则称π为可图序列，且图G为π的一个实现。给定简单图H，如果存在简单图G其度序列为π，且H为G的子图，则称π蕴含H可图。对给定简单图Ck和Pt，Ck∪E(Pt)表示在不增加顶点的情况下，在Ck圈中添加一条Pt路；Ck∪E(Cl)表示在不增加顶点前提下，在Ck圈中添加一个Cl圈，且最终所得图Ck∪E(Pt)和Ck∪E(Cl)依旧是简单图。 本文研究了蕴含C6∪E(C4)可图序列的刻划问题和蕴含C6∪E(P3)可图序列的刻划问题。