Gallai’s question and constructions of almost hypotraceable graphs

Consider a graph G G in which the longest path has order |V(G)|−1 | V ( G ) | − 1 . We denote the number of vertices v v in G G such that G−v G − v is non-traceable with  t G t G . Gallai asked in 1966 whether, in a connected graph, the intersection of all longest paths is non-empty. Walther showed that, in general, this is not true. In a graph G G in which the longest path has |V(G)|−1 | V ( G ) | − 1 vertices, the answer to Gallai’s question is positive iff t G ≠0 t G ≠ 0 . In this article we study almost hypotraceable graphs, which constitute the extremal case t G =1 t G = 1 . We give structural properties of these graphs, establish construction methods for connectivities 1 through 4, show that there exists a cubic 3-connected such graph of order 28, and draw connections to works of Thomassen and Gargano et al.