几乎正则多部竞赛图的Hamilton性和有向图中几个计数问题

论文摘要

本文的研究内容涉及有向图的三个方面:几乎正则多部竞赛图的Hamilton性,竞赛图的Hamilton-路数的下界及几种特殊有向图控制集的计数问题。 多部或n-部竞赛图是完全n-部图的一个定向。竞赛图是恰有n个顶点的n-部竞赛图。设x是有向图D的一个顶点,dD+（x）和dD-（x）分别表示x的出度和入度。有向图D=（V,A）的非正则度I（D）=（?）{|d+（x）-d-（y）|)。称有向图D是正则的,若D的非正则度I（D）=0。称有向图D是几乎正则的,若D的非正则度I（D）≤1。 有向图的Hamilton性,由于其本身极具挑战性和其广泛的应用,一直是图论中的热点话题之一。至今已有相当丰硕的研究成果。在有向图方面,1966年Moon[16]首先证明了强连通竞赛图是顶点泛圈的。1976年,Bondy[3]证明了强连通n-部竞赛图包含一个m-圈,其中m∈{3,4,…,n}。Yeo[18]证明了正则的多部竞赛图是Hamiltonian。1999年,周国飞和张克民在文[21]中证明了几乎正则的n-部（n≥7）竞赛图是Hamiltonian。本文2.1节推广了上述结果,得到: 几乎正则的n-部（n≥6）竞赛图是Hamiltonian。 在对有向图的研究中,大量文献关注图中Hamilton-路的存在性,涉及Hamilton-路数的文献极少。本文的2.2节基于对竞赛图强连通分支的讨论,得到了: 设T为一个竞赛图,T1,T2,…,Ts为T的强连通分支（设当T强连通时,s=1）。m表示T中Hamilton路的条数,则m≥∏i=1s|V（Ti）|。等式成立当且仅当对于每个i∈{1,2,…,s},Ti≌C3或Ti≌K1。这个定理给出了竞赛图中Hamilton路数的一个下界,并且这个界是紧的。 子集D（?）V（H）称为有向图H的控制集,如果对于任意的y∈V（H）-D,存在x∈D,使得xy∈A（H）。设d（H）表示有向图H的控制集数。本文2.3节给出了有向路Pn和有向圈Cn的控制集数的递推关系; 对于n≥3,d（Pn）=d(Pn-1)+d(Pn-2)。 对于n≥5,d（Cn）=d(Cn-1)+d(Cn-2)。以它们为基础,得到了有向路和有向圈的分裂控制集数、强控制集数和弱控制集数的递推关系。并且注意到它们的显性表达式可以很容易地求出。

论文目录

• 引言
• 第一章 预备知识
• §1.1 术语和记号
• §1.2 相关结论
• 第二章 主要结果
• §2.1 几乎正则多部竞赛图的Hamilton性
• §2.2 竞赛图Hamilton路数的一个下界
• §2.3 有向路和有向圈的几种控制集数
• 总结
• 参考文献
• 致谢
• 附录
• 承诺书