A CHVATAL-ERDOS TYPE THEOREM FOR PATH-CONNECTIVITY

摘要

For a graph G, let kappa(G) and alpha(G) be the connectivity and independence number of G, respectively. A well-known theorem of Chvatal and Erdos says that if G is a graph of order n with kappa(G) > alpha(G), then G is Hamilton connected. In this paper, we prove the following Chvatal-Erdos type theorem: if G is a k-connected graph, k >= 2, of order n with independence number alpha, then each pair of distinct vertices of G is joined by a Hamiltonian path or a path of length at least (k - 1) max {n+alpha-k/alpha, [n+2 alpha-2k+1]}. Examples show that this result is best possible. We also strength it in terms of subgraphs.

关键词