Note on k-contractible edges in k-connected graphs
Note on k-contractible edges in k-connected graphs
复制标题
关于 k 连通图中的 k 收缩边的注意事项
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
K. Kawarabayashi
中科院分区：
文献类型：
--
作者：
K. Kawarabayashi
证明如果G是一个不包含K的K连通图；；当k为奇数时，则G有一条边e，使得由G缩并e得到的图仍然是k连通的。当k是偶数时，同样的结论不成立。这个结果是对著名的Thomassen定理的推广[J]。图论5(1981)，351—354]当k为奇数时。
It is proved that if G is a k-connected graph which does not contain K;; with k being odd, then G has an edge e such that the graph obtained from G by contracting e is still k-connected. The same conclusion does not hold when k is even. This result is a generalization of the famous theorem of Thomassen [J. Graph Theory 5 (1981), 351--354] when k is odd.