کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6423904 1632593 2011 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
High connectivity keeping connected subgraph
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
High connectivity keeping connected subgraph
چکیده انگلیسی

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 which says that every k-connected graph G of sufficiently large order (k⩾4) has a connected subgraph H of order exactly four such that G−H is (k−3)-connected.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 38, 1 December 2011, Pages 355-360
نویسندگان
, ,