论文部分内容阅读
在图论中,与圈相关的问题一直是图论学者研究的重点之一.近年来,有关于哈密尔顿圈的问题更是受到大量科研工作者的广泛关注,而随着图论学者I.Fabrici,E.Hexel和S.Jendrol提出哈密尔顿图的H-强迫集和H-强迫数的概念后,有关于哈密尔顿图的H-强迫集和H-强迫数问题也成为了学者们研究的热点.本文将主要研究某些笛卡尔积图的H-强迫集和H-强迫数.研究这些图的H-强迫集和H-强迫数,一方面将加深我们对这些哈密尔顿图的结构认识,另一方面将有助于改进在这些图类中寻找哈密尔顿圈的算法.除此之外,本文还探讨了强连通的圆的局部竞赛图的哈密尔顿分解问题.本文共分为四章.第一章,绪论.介绍了研究背景和基本概念.第二章,在无向图中,讨论了圈和路的笛卡尔积图的H-强迫集和H-强迫数.本章由笛卡尔积的定义,得到了圈和路作笛卡尔积后的图,并以此研究了所得图的H-强迫集与H-强迫数,利用寻找非哈密尔顿圈的方法证明了主要结论：设图G=Ck×Pl,其中k≥2,1≥1.则有(i)当k=2时,h(G)=2.(ii)当k≥3时,第三章,在有向图中,讨论有向圈和有向路的笛卡尔积图的H-强迫集和H-强迫数.并通过证明得到如下结论：设Cn和Ckn是两个有向圈,其中n为正整数且n≥2,k=1,2,3,…,则(i)有向图Cn×Ckn为哈密尔顿图.第四章,研究了强连通的圆的局部竞赛图的哈密尔顿分解问题,并得到了几个有关哈密尔顿分解的简单结论：1.3-弧强的圆局部竞赛图D有两个弧不相交的哈密尔顿圈.2.设D是一个局部半完全有向图,它是通过在C2k2上增加一个新顶点x且增加至少两条从x到V(C2k2)的弧和至少两条从V(C2k2)到x的弧得到的有向图.则D有两个弧不相交的哈密尔顿圈.3.2-弧强的圆的局部竞赛图D有弧不交的哈密尔顿圈和哈密尔顿路当且仅当D不是偶圈的2次幂.