کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647867 1342381 2013 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Non-separating subgraphs
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Non-separating subgraphs
چکیده انگلیسی

Lovász conjectured that there is a smallest integer f(l)f(l) such that for every f(l)f(l)-connected graph GG and every two vertices s,ts,t of GG there is a path PP connecting ss and tt such that G−V(P)G−V(P) is ll-connected. This conjecture is still open for l≥3l≥3. In this paper, we generalize this conjecture to a kk-vertex version: is there a smallest integer f(k,l)f(k,l) such that for every f(k,l)f(k,l)-connected graph and every subset XX with kk vertices, there is a tree TT connecting XX such that G−V(T)G−V(T) is ll-connected? We prove that f(k,1)=k+1f(k,1)=k+1 and f(k,2)≤2k+1f(k,2)≤2k+1.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 313, Issue 4, 28 February 2013, Pages 391–396
نویسندگان
, ,