奇正则无爪图的配对控制数

摘要

在图G中，对于点集S,如果V(G)\S中的每一个点都有一个邻点在点集S中，我们称点集S是图G的控制集.图G的配对控制集是一个点控制集且它的导出子图有一个完美匹配，而配对控制数是图G所有配对控制集中点数最少的点的个数，记为Ypr(G).本文的主要研究结果如下：
　　设图G是一个连通的3正则图，且无{k1,3，k4-e}子图.如果图G的顶点数为n且无C4子图，则Ypr(G)≤10n+6/27如果图G的顶点数为n且无{C4，C6，C10,…，C2g0}子图，其中g0≥3的奇数，则Ypr(G)≤n/3+n+6/9(「3/4(g0+1)」+1)上述两种情况的极图也被刻画出来.
　　我们还证明了如果图G是一个连通的3正则2-连通图，且无{Ki,3，K4-e}子图，则Ypr(G)=n/3.此外，如果图G是顶点数为n的(2k+1)正则连通图，且无{Ki,3，K4-e}子图，则Ypr(G)≤n/k+1,等号成立的充要条件是G=L(F),其中F兰≌K1,2k十2,或当k是一个偶数时，F也满足F≌Kk十1；k+2.

目录

封面

中文摘要

英文摘要

目录

第一章 引言

1 .1 研究背景

1.2 基本概念

1 .3 研究现状及本文主要结果

第二章主要结果

2 .1 预备知识

2.2 3正则图的配对控制数

2 .3 奇正则图的配对控制数

2.4 进一步研究

参考文献

硕士期间发表论文清单

致谢

声明