5
$\begingroup$

Is there for every $k$ a $k$-connected graph whose longest paths do not have a vertex in common?

This is known to be true for $k\le 3$, see
Ayesha Shabbir, Carol T. Zamfirescu., Tudor I. Zamfirescu: Intersecting longest paths and longest cycles: A survey.
Surprisingly, nothing is mentioned about $k\ge 4$, though the question kind of appears on p. 232 of
Tudor I. Zamfirescu: On longest paths and circuits in graphs.

Some related questions include Hippchen's conjecture (any two longest paths intersect in at least $k$ vertices in a $k$-connected graph) and the problem of determining the minimum size of a hitting point set for longest paths, about which there is a recent MathOverflow question.

$\endgroup$
0

1 Answer 1

6
$\begingroup$

According to Gallai’s question and constructions of almost hypotraceable graphs by Wiener and Zamfirescu, this is an open problem (see the beginning of Section 4). Note that a graph is $G$ hypotraceable if $G$ is not Hamiltonian, but $G-v$ is Hamiltonian for every $v \in V(G)$. Thus, the existence of a $4$-connected hypotraceable graph would give a negative answer to the question in your title. However, as also noted at the beginning of Section 4, it is unknown if there are $4$-connected hypotraceable graphs. Indeed, it is not even known if there are hypotraceable graphs with minimum degree $4$.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .