کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6424196 | 1632784 | 2014 | 11 صفحه PDF | دانلود رایگان |
It was proved by Mader that, for every integer l, every k-connected graph of sufficiently large order contains a vertex set X of order precisely l such that GâX is (kâ2)-connected. This is no longer true if we require X to be connected, even for l=3.Motivated by this fact, we are trying to find an “obstruction” for k-connected graphs without such a connected subgraph. It turns out that the obstruction is an essentially 3-connected subgraph W such that GâW is still highly connected. More precisely, our main result says the following.For kâ¥7 and every k-connected graph G, either there exists a connected subgraph W of order 4 in G such that GâW is (kâ2)-connected, or else G contains an “essentially” 3-connected subgraph W, i.e., a subdivision of a 3-connected graph, such that GâW is still highly connected-actually, (kâ6)-connected.This result can be compared to Mader's result (Mader, 2002) [5] which says that every k-connected graph G of sufficiently large order (kâ¥4) has a connected subgraph H of order exactly 4 such that GâH is (kâ3)-connected.
Journal: European Journal of Combinatorics - Volume 35, January 2014, Pages 245-255