Article ID Journal Published Year Pages File Type
4647867 Discrete Mathematics 2013 6 Pages PDF
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
, ,