Connectivity keeping edges in graphs with large minimum degree
Connectivity keeping edges in graphs with large minimum degree
复制标题
DOI：
10.1016/j.jctb.2007.11.001
复制
发表时间：
2008-07-01
影响因子：
1.4
通讯作者：
Kawarabayashi, Ken-ichi
中科院分区：
文献类型：
--
作者：
Fujita, Shinya;Kawarabayashi, Ken-ichi
Chartrand、Kaugars 和 Lick 的著名结果表明，每个最小度至少为 3k/2 的 k 连通图 G 都有一个顶点 v，使得 G - v 仍然是 k 连通的。在本文中，我们考虑上述结果的推广[G. Chartrand, A. Kaigars, D.R. Lick，临界 n 连通图，Proc。阿米尔。数学。苏克。 32（1972）63-68]。我们证明以下结果：假设G是一个k连通图，最小度至少为[3k/2] + 2。那么G有一条边e，使得G - V(e)仍然是k连通的。最小度的界限本质上是最好的可能。 (c) 2007 Elsevier Inc. 保留所有权利。
The old well-known result of Chartrand, Kaugars and Lick says that every k-connected graph G with minimum degree at least 3k/2 has a vertex v such that G - v is still k-connected. In this paper, we consider a generalization of the above result [G. Chartrand, A. Kaigars, D.R. Lick, Critically n-connected graphs, Proc. Amer. Math. Soc. 32 (1972) 63-68]. We prove the following result:Suppose G is a k-connected graph with minimum degree at least [3k/2] + 2. Then G has an edge e such that G - V(e) is still k-connected.The bound on the minimum degree is essentially best possible. (c) 2007 Elsevier Inc. All rights reserved.