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 $(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\le 4$ or $k\ge (n-2)/3$.

8 pages, 2 figures