2015/03/04 by Shinya Fujita, Michitaka Furuya, Fujita, Shinya +5
Computer Science · Engineering · Mathematics · #05C38 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems #math.CO #msc:05C38
paper · pdf · doi:10.48550/arxiv.1503.01219
11pages, 5figures
openalex publication_date 2015/03/04 · arxiv created 2015/07/27 · arxiv updated 2015/07/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In 1966, T. Gallai asked whether every connected graph has a vertex that appears in all longest paths. Since then this question has attracted much attention and many work has been done in this topic. One important open question in this area is to ask whether any three longest paths contains a common vertex in a connected graph. It was conjectured that the answer to this question is positive. In this paper, we propose a new approach in view of distances among longest paths in a connected graph, and give a substantial progress towards the conjecture along the idea.