Improvements on Hippchen's Conjecture

2020/11/18 by Cho, Eun-Kyung, Choi, Ilkyoo, Park, Boram
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2011.09061

Abstract

Let G be a k-connected graph on n vertices. Hippchen's Conjecture states that two longest paths in G share at least k vertices. Gutiérrez recently proved the conjecture when k≤ 4 or k≥ (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 k≥ (n+2)/(5). This completely resolves two conjectures of Gutiérrez in the affirmative.

Related

• On the intersection of two longest paths in k-connected graphs
• On two conjectures about the intersection of longest paths and cycles
• A New Approach Towards a Conjecture on Intersecting Three Longest Paths
• Bi-traceable graphs, the intersection of three longest paths and Hippchen's conjecture
• Bounding the distance among longest paths in a connected graph