论文部分内容阅读
令G为一连通图，其顶点个数为v，整数0≤k≤v／2-1，若G有大小为k的对集，且G的每一个大小为k的对集都包含在G的一个完美对集中，则称G为k可扩的．若0≤n≤v-2，对于图G的任意大小为佗的顶点子集S(∪)V(G)，G—S均有完美对集，则称图G为n因子临界的．
本文主要研究k可扩图和n因子临界图．
我们注意到对集可扩理论与连通度理论之间有很多的相似的结论，这促使我们研究k可扩图和尼连通图之间的关系．在本文第2章中，我们独立地得到了k可扩二部图和k强连通有向图之间的等价关系．利用这个等价关系，我们列举说明了对集可扩理论和连通度理论的一系列相似结论，简化了k可扩二部图一个结论的证明．对于有完美对集但非1可扩的二部图，我们证明了其基本分支与有向图的强连通分支对应．从所得到的等价关系，我们还证明了k可扩二部图，k强连通有向图与组合矩阵的关系．
k可扩图和n因子临界图是两个关系密切的概念．因此有不少研究这两个图类之间关系的工作．由定义即可知一个2k因子临界图总是k可扩的．但是反过来，尼可扩图在何种条件下是2k因子临界的，这是一个还没有研究清楚的问题．Favaron和Yu在这个问题上分别得到了一些结论．Lou和Yu证明了当k≥v／4时，k可扩非二部图G的连通度k≥2k．这个连通度达到了2k因子临界图连通度的下界．这启发我们研究k≥v／4的k可扩图和2k因子临界图的关系．本文第3章给出我们的研究结果，即当k≥(v+2)／4时，尼可扩非二部图是2k因子临界的．我们还给出例子，说明这个下界是最好可能的．作为一个推广，我们还得到了(2k+1)因子临界图与k1/2可扩图之间的类似关系．对于k=v／4的情况，我们也把k可扩图和2k因子临界图的关系研究清楚，给出了一个k可扩图是2k因子临界图的充分必要条件．
基于我们关于k可扩图和n因子临界图的等价性质的研究结果，我们可以从系统的角度看待k强连通图，k可扩二部图，k可扩图和n因子临界图，这将有利于我们今后研究工作的开展．
从第4章起我们研究k可扩图和n因子临界图的性质．
第4章把Anachuen和Caccetta的关于k可扩图中独立数的一个结论推广到n因子临界图．
在第5章的研究工作中，我们试图证明k≥v／4时，k可扩图中有对集交错的Hamilton圈．我们的工作表明，对集交错的Hamilton圈的存在性可以由更弱的条件得到．我们证明了在具有完美对集M的二部图G中，当顶点最小度δ≥v／4+1时，图G有M交错的Hamilton圈．在一般图中，当G的连通度k≥v／2时，除非G属于一类例外的图类，G有M交错的Hamilton圈．由于例外图类不是k可扩的，因此从我们的结论可以推出当k≥v／4时，k可扩图中有对集交错的Hamilton圈．本章中关于一般图的结论证明有一定的难度，最终的结论具有与经典的Hamilton圈存在性条件类似的简洁形式．
在第6章中，我们首先研究了Harary图及其变种的因子临界性和可扩性，其意义在于这些图类包含了边数最少的k可扩图和n因子临界图．我们发现现有文献所构造的边数最少的k可扩图都是二部图，这促使我们研究具有最少边数的k可扩非二部图．本章完全解决了k=1，2的情况．