Graphs with Nonempty Intersection of Longest Paths

Abstract

We prove that the intersection of longest paths in a connected graph $G$ is nonempty if and only if for every block $B$ of $G$ the longest paths in $G$ which use at least one edge of $B$ have nonempty intersection. This result is used to show that if every block of a graph $G$ is Hamilton-connected, almost-Hamilton-connected, or a cycle then all longest paths in $G$ intersect. (We call a bipartite graph almost-Hamilton-connected if every pair of vertices is connected by a path containing an entire bipartition set.) We also show that in a split graph all longest paths intersect. (A graph is split if there exists a partition of its vertex set into a stable set and a complete set.)