k-连通图的可收缩边(英文)

证明了对k-连通图G,若G的任意一个断片满足当N(F)中含有边就有|F|>k/4,则G至少有2条可收缩边.

极小k-连通图中的k-可收缩边

Ando证明了如果G是极小的k-连通图,且G中不含有K1+C4,若对于V(G)中的任意一个k度点x,与x关联的边中都存在一条不在三边形中的边,那么G中含有k-可收缩边.改进这个结果得出结论:如果G是极小的k-连通图,且不含图P,若G中任一k度点x,都存在与x关联的不在三边形中的边,那么G中有k-可收缩边.

极大临界k-连通图的可收缩边

对极大临界k-连通图G的局部结构进行了讨论,证明了G中存在可收缩边e,使得G/e还是临界k-连通图.

k-树图的收缩边

Narayanaswamy,Sadagopan和Sunil Chandran证明了k-树图G可收缩边数目的下界为V(G)+k-2,并指出这个界是紧的.该文给出了k-树图G可收缩边数目更一般的下界,由该文的结果可以推出Narayanaswamy等人的结果,进一步证明了可收缩边数目恰好为V(G)+k-2的图的特征.

不含某类子图的k-连通图中的一个结果

如果将k-连通图G中的一条边收缩之后仍然得到一个k-连通图,则称这条边是G的一条k-可收缩边(简称可收缩边)。一个不含任何可收缩边的非完全k-连通图称为收缩临界k-连通图。2000年,Ando等证明了如下结论:设k≥4是一个整数,G是一个不含K-4的收缩临界k-连通图,则k是一个偶数,并且G中的每一个顶点都至少含在2个三角形中。文章进一步加强Ando等的结论,证明:设k≥3是一个整数,G是一个不含K-4的k-连通图,若G中存在至多含在一个三角形上的顶点,则每一个这样的顶点都关联一条k-可收缩边。

不含禁用子图的极小κ-连通图

本文得到:如果G是极小的κ-连通图,且不合图F,若对于G中任一κ度点力,都存在与力关联的不在三边形中的边,那么G中有κ-可收缩边。

k-连通图中生成树和完美匹配上的可收缩边

给出了k-连通图生成树和完美匹配上的可收缩边数目,得到如下结果:任意断片的阶都大于「k/2■的k-连通图中生成树上至少有4条可收缩边;若该k-连通图中存在完美匹配,则完美匹配上至少有「k/2■+1条可收缩边。

k-连通图中最长圈上可收缩边的数目

给出了k-连通图中最长圈上的可收缩边的数目,得到如下结果:任意断片的阶至少为「k/2」+1的k-连通图中最长圈上至少有3条可收缩边;更进一步,若该k-连通图中存在哈密顿圈,则哈密顿圈上至少有6条可收缩边。

断片及其应用

断片在图的连通性的研究中,尤其是在研究k-连通图中的可收缩边(子图)中,发挥重要的作用,本文给出了断片的定义及其一些简单的性质,并给出了断片的一个简单应用。

不含某些子图的k连通图中的k可收缩边

最近Ando等证明了在一个k(k≥5是一个整数)连通图G中,如果δ(G)≥k+1,并且G中既不含K_5^-,也不含5K_1+P_3,则G中含有一条k可收缩边.对此进行了推广,证明了在一个k连通图G中,如果δ(G)≥k+1,并且G中既不含K_2+([k-1/2]K_1∪P_3),也不含tK_1+P_3(k,t都是整数,且t≥3),则当k≥4t-7时,G中含有一条k可收缩边.