2023/12/03 by Xingzhi Zhan, Zhan, Xingzhi
Computer Science · #05C30 #05C35 #05C38 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2312.01353
openalex publication_date 2023/12/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A longest path in a graph is called a detour. It is easy to see that a connected graph of minimum degree at least 2 and order at least 4 has at least 4 detours. We prove that if the number of detours in such a graph of order at least 9 is odd, then it is at least 9, and this lower bound can be attained for every order. Thus the possibilities 3, 5 and 7 are excluded. Two open problems are posed.