Improvements on Hippchens Conjecture


الملخص بالإنكليزية

Let $G$ be a $k$-connected graph on $n$ vertices. Hippchens Conjecture states that two longest paths in $G$ share at least $k$ vertices. Gutierrez recently proved the conjecture when $kleq 4$ or $kgeq frac{n-2}{3}$. We improve upon both results; namely, we show that two longest paths in $G$ share at least $k$ vertices when $k=5$ or $kgeq frac{n+2}{5}$. This completely resolves two conjectures of Gutierrez in the affirmative.

تحميل البحث