On two conjectures about the intersection of longest paths and cycles

2023/10/05 by Gutiérrez, Juan, Valqui, Christian · 1 citation
#05C38 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2

paper · doi:10.48550/arxiv.2310.03849

Abstract

A conjecture attributed to Smith states that every pair of longest cycles in a k-connected graph intersect each other in at least k vertices. In this paper, we show that every pair of longest cycles in a~k-connected graph on n vertices intersect each other in at least~min\n,8k-n-16\ vertices, which confirms Smith's conjecture when k≥ (n+16)/7. An analog conjecture for paths instead of cycles was stated by Hippchen. By a simple reduction, we relate both conjectures, showing that Hippchen's conjecture is valid when either k ≤ 6 or k ≥ (n+9)/7.

Cited by

• Intersections of longest cycles in vertex-transitive and highly connected graphs

Related

• On the intersection of two longest paths in k-connected graphs
• Longest cycles in vertex-transitive and highly connected graphs
• Intersections of longest cycles in vertex-transitive and highly connected graphs
• Improvements on Hippchen's Conjecture
• Small hitting sets for longest paths and cycles