Motivated by the well-known conjecture by Lovasz (1975) [6] on the connectivity after the path removal, we study the following problem: There exists a function f = f (k, l) such that the following holds. For every f (k, l)-connected graph G and two distinct vertices s and t in G. there are k internally disjoint paths P-1,...,P-k with endpoints s and t such that G - boolean OR(k)(i=1) V(Pi) is l-connected. When k = 1, this problem corresponds to Lovasz conjecture, and it is open for all the cases l >= 3. We show that f (k, 1) = 2k+1 and f (k, 2) <= 3k + 2. The connectivity "2k+1" for f (k, 1) is best possible. Thus our result generalizes the result by Tutte (1963)[8] for the case k = 1 and I = 1 (the first settled case of Lovasz conjecture), and the result by Chen, Gould and Yu (2003) [1], Kriesell (2001) [4], Kawarabayashi, Lee, and Yu (2005)[2], independently, for the case k = 1 and l = 2 (the second settled case of Lovasz conjecture). When l = 1, our result also improves the connectivity bound "22k + 2" given by Chen. Gould and Yu (2003) [1].
展开▼
