Smallest Sets of Longest Paths with Empty Intersection
Zdzisław Skupień · Combinatorics Probability Computing · 1996
It is shown that, for every integer v < 7, there is a connected graph in which some v longest paths have empty intersection, but any v – 1 longest paths have a vertex in common. Moreover, connected graphs having seven or five minimal sets of longest paths (longest cycles) with empty intersection are presented. A 26-vertex 2-connected graph whose longest paths have empty intersection is exhibited.