极小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中的一条边收缩之后仍然得到一个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中有κ-可收缩边。