Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647867 | Discrete Mathematics | 2013 | 6 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Yanmei Hong, Hong-Jian Lai,