On the intersection of two longest paths in k-connected graphs

Abstract

We show that every pair of longest paths in a k-connected graph on n vertices intersect each other in at least min{n, (8k ? n + 2)/5} vertices. We also show that, in a 4-connected graph, every pair of longest paths intersect each other in at least four vertices. This confirms a conjecture of Hippchen for k-connected graphs when k 4 or k (n ? 2)/3.