子式极小的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连通图。
Abstract:
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.
参考文献
|
[1]
|
Bondy, J.A. and Murty, S.R. (1976) Graph Theory with Alications. MacMillan.
|
|
[2]
|
Kriesell, M. (2007) How to Contract an Essen-tially 6-Connected Graph to a 5-Connected Graph. Discrete Mathematics, 307, 494-510.
[Google Scholar] [CrossRef]
|
|
[3]
|
覃城阜. 收缩临界5-连通图的性质[D]: [硕士学位论文]. 桂林: 广西师范大学, 2004.
|
|
[4]
|
覃城阜. 5-连通图的可收缩子图及minors [D]: [博士学位论文]. 厦门: 厦门大学, 2010.
|
|
[5]
|
Kriesell, M. (2005) Triangle Density and Contractibility. Combinatorics, Probability and Computiny, 14, 133-146.
|
|
[6]
|
Kriesell, M. (2001) A Degree Sum Contio for the Existence of Contraciable Edge in k Connected Graph. Journal of Combinatorial Theory, Series B, 82, 81-101.
|