Non-separating subgraphs after deleting many disjoint paths

详细信息    查看全文

• 作者：Ken-ichi Kawarabayashi ; Kenta Ozeki
• 关键词：Non-separating subgraphs ; Lová ; sz conjecture
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2011
• 出版时间：January 2011
• 年：2011
• 卷：101
• 期：1
• 页码：54-59
• 全文大小：142 K

文摘

Motivated by the well-known conjecture by Lovász (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₁,…,P_k with endpoints s and t such that is l-connected.

When k=1, this problem corresponds to Lovász conjecture, and it is open for all the cases l3.

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 l=1 (the first settled case of Lovász 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 Lovász conjecture).

When l=1, our result also improves the connectivity bound “22k+2” given by Chen, Gould and Yu (2003) [1].