کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656751 1632976 2016 21 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Non-separating subgraphs in highly connected graphs
ترجمه فارسی عنوان
زیرگرافی های غیر جدایی در گرافهای بسیار متصل
کلمات کلیدی
تجزیه، زیرگرافی بسیار متصل، لبه های قابل تعویض، چرخه ناشی از جداسازی، مثلثها، چرخه
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

A well-known conjecture of Thomassen says that every (a+b+1)(a+b+1)-connected graph with a≥ba≥b can be decomposed into two parts A and B such that A is a-connected and B is b  -connected. The case b=2b=2 is settled by Thomassen himself, but the conjecture is still open for b≥3b≥3.Motivated by this, we prove that every k-connected graph G   (with k≥4k≥4) has a subgraph M such that either1.M   is 3-connected with at most 5 vertices (thus G−V(M)G−V(M) is (k−5)(k−5)-connected), or2.M   is an induced cycle such that G−V(C)G−V(C) is (k−2)(k−2)-connected.This result improves previous known results by Egawa and Kawarabayashi, respectively.Our result is also related to results and questions of Mader concerning critically k-connected graphs. We partially answer the question of Mader in 1988.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 117, March 2016, Pages 1–21
نویسندگان
, ,