关于拟k-连通图的一个注释

• 作者: 林晓霞
• 来源期刊: 运筹学学报
• 关键词: 拟k-连通图 连通分支
• 年，卷（期）: 2021,（1）
• 页码范围: 137-140
• 页数: 4页
• 分类号: O157.5
• 语种: 中文
• DOI: 10.15960/j.cnki.issn.1007-6093.2021.01.014

摘要

G是一个k-连通图,T是G的一个k-点割,若G-T可被划分成两个子图G1,G2,且|G1 |≥2,|G2 |≥2,则称T是G的一个非平凡点割.假定G是一个不含非平凡(k-1)点割的(k-1)-连通图,则称G是一个拟k-连通图.证明了对任意一个k≥5且t＞k/2的整数,若G是一个不含(K2+tK1)的k-连通图,且G中任意两个不同点对v,w,有d(v)+d(w)≥3k/2+t,则对G中的任意一个点,存在一条与之关联的边收缩后可以得到一个拟k-连通图,且G中至少有|V(G)/|2条边使得收缩其中任意一条边后仍是拟k-连通的.