Connectivity keeping paths in k-connected graphs
Connectivity keeping paths in k-connected graphs
复制标题
DOI：
10.1002/jgt.v65:1
复制
发表时间：
2010-09
影响因子：
0.9
通讯作者：
M. Cropper;Anthony J. W. Hilton;Peter D. Johnson;J. Lehel
中科院分区：
文献类型：
--
作者：
M. Cropper;Anthony J. W. Hilton;Peter D. Johnson;J. Lehel
G.Chartrand，A.Kugars和D.R.Lick[Proc Amer Math Soc32(1972)，63-68]的一个结果指出，每个最小度至少为⌊3k-2⌋的有限k连通图G包含一个顶点x，使得G-x仍然是k连通的。我们证明了对正整数m，每个最小度的有限k连通图G至少⌊3k-2⌋+m-1包含长度为m-1的路P，使得G-V(P)仍然是k-连通的，从而推广了这一结果。这已被S.Fujita和K.K.Kawa abayashi以较弱的形式猜想[J Combin理论系列B 98(2008)，805-811]。《图论》杂志65：61-69,2010。
A result of G. Chartrand, A. Kaugars, and D. R. Lick [Proc Amer Math Soc 32 (1972), 63–68] says that every finite, k-connected graph G of minimum degree at least ⌊3k-2⌋ contains a vertex x such that G-x is still k-connected. We generalize this result by proving that every finite, k-connected graph G of minimum degree at least ⌊3k-2⌋+m-1 for a positive integer m contains a path P of length m-1 such that G-V(P) is still k-connected. This has been conjectured in a weaker form by S. Fujita and K. Kawarabayashi [J Combin Theory Ser B 98 (2008), 805–811]. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 61–69, 2010.