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

作者：杨迎球; 令狐荣涛

来源：安顺学院学报, 2018, 20(04): 126-129.

• k-连通图
• 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-可收缩边。

• 单位
  数理学院; 安顺学院