{"ID":23629740,"CreatedAt":"2026-09-18T07:04:54.147703138Z","UpdatedAt":"2026-09-18T07:04:54.147703138Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.20724","arxiv_id":"2609.20724","title":"Longest cycles intersect linearly in highly connected graphs","abstract":"A longstanding conjecture attributed to Smith (1984) asserts that for every $k\\ge2$, any two longest cycles in a $k$-connected graph share at least $k$ vertices. In this paper, we prove the first linear lower bound, showing that any two longest cycles in a $k$-connected graph share at least $k/600$ vertices. Departing from previous Turán-type extremal arguments, we develop a novel structural approach that also yields applications to related problems on longest cycles and paths.","short_abstract":"A longstanding conjecture attributed to Smith (1984) asserts that for every $k\\ge2$, any two longest cycles in a $k$-connected graph share at least $k$ vertices. In this paper, we prove the first linear lower bound, showing that any two longest cycles in a $k$-connected graph share at least $k/600$ vertices. Departing...","url_abs":"https://arxiv.org/abs/2609.20724","url_pdf":"https://arxiv.org/pdf/2609.20724v1","authors":"[\"Jie Ma\",\"Bo Ning\",\"Ziyuan Zhao\"]","published":"2026-09-17T17:16:51Z","proceeding":"math.CO","tasks":"[\"math.CO\"]","methods":"[]","has_code":false}