Non-Separating Paths in 4-Connected Graphs |
| |
| Authors: | Ken-ichi Kawarabayashi Orlando Lee Xingxing Yu |
| |
| Institution: | (1) Mathematics Department, Princeton University, Fine Hall, Washington Road, Princeton, NJ 08544, USA;(2) Instituto de Computação, Universidade Estadual de Campinas, Caixa Postal 6176, 13083–971 Campinas - SP, Brazil;(3) School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia 30332, USA;(4) Center for Combinatorics, LPMC, Nankai University, Tianjin, 300071, P. R. China |
| |
| Abstract: | In 1975, Lovász conjectured that for any positive integer k, there exists a minimum positive integer f(k) such that, for any two vertices x, y in any f(k)-connected graph G, there is a path P from x to y in G such that G–V(P) is k-connected. A result of Tutte implies f(1) = 3. Recently, f(2) = 5 was shown by Chen et al. and, independently, by Kriesell. In this paper, we show that f(2) = 4 except for double wheels.Received October 17, 2003 |
| |
| Keywords: | 05C38 05C40 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
