论文部分内容阅读
图的控制理论是图论中一个重要的研究领域．在图中，加边或去点都能使图的控制数减少，相应的，我们就可以研究在加边或去点情形下的性质，也就是图的控制临界理论.图的控制临界和图的控制理论紧密相关，针对不同的控制数及不同的限制条件，会得到不同的临界结论，这篇文章主要研究图的加边及去点连通控制临界的匹配、因子临界和双因子临界的性质．本文主要结论如下：
一、对连通控制边临界图，得到以下主要结论：
(1)令G是一个3-连通3-连通-控制-边临界且有2n个顶点的图，其中n≥4，若对于G中任意两个不相邻的点x,y,d(x)+d(y)≥2n-2，则G是双因子临界的.
这个结果推广了Ananchuen，Ananchuen和Plummer的结果([Matching prop erties in connected domination critical graphs,Discrete Math.2008]中定理2.1).
(2)令G是3-连通3-连通-控制-边临界且有2n个点的图，其中n≥4．若G中任意两个不同的点u和v，当d(u，v)=2，有max{d(u)，d(v)}≥n（范条件），则G是双因子临界的．
(3)令G是3-连通-控制-边临界的偶阶图.若G是3-连通且K1,4-free的，则G是双因子临界的.
这个结果改进了Ananchuen，Ananchuen和Plummer的结果([Matchin prop erties in connected domination critical graphs,Discrete Math.2008]中定理2.2).
二、对连通控制点临界图，得到以下主要结论：
(1)若G是一个k1,5-free3-连通-控制-点临界的偶阶图，则G含有完美匹配．
(2)若G是一个k1,5-free3-连通-控制-点临界奇阶图，则G是因子临界的．
(3)若G是一个k1,4-free4-连通-控制-点临界偶阶图，则G含有完美匹配．
(4)若G是一个k1,4-free4-连通-控制-点临界奇阶图，则G是因子临界的．
(5)若G是一个k1,4-free5-连通-控制-点临界偶阶图，则G含有完美匹配．
完美匹配，因子临界，或双因子临界性质对任意图在匹配方面的分解理论中，起着重要的作用．
最后我们总结本文所做的工作，并提出一些值得继续研究的问题.