子式极小的Super-5连通图

On the Minor Minimal Super 5-Connected Graphs

如果图G可以经过去边,或者去点,或者收缩子图得到子图H,则称H是G的子式。若G是k-连通图且G中不包含另外一个k-连通图作为子式,则称G是子式极小的k-连通图。M. Krisesell证明了子式极小的hyper-5连通图的顶点数至多是12。本文将这个结论推广到Super-5连通图。

A graph H is called a minor of a graph G if H can be formed from G by deleting edges and vertices and by contracting edges. Let G be a k-connected graph such that G contains no other k-connected graph as its minor, then we call G a minor minimal k-connected graph. M. Kriesell showed that every minor hyper-5 connected graph has at most 12 vertices. In this paper, we show that every minor super-5 connected graph has at most 12 vertices.