{"id":"arxiv/2604.24137","url":"https://arxiv.org/abs/2604.24137","tags":["math.CO"],"score":0,"title":"The minimum number of detours in a connected graph of minimum degree three","domain":"math.CO","source":"arxiv","authors":["Xining Liu","Pu Qiao","Xingzhi Zhan"],"reviews":0,"subject":"math.CO","summary":"A longest path in a graph is called a detour. Denote by $a(k,n)$ the minimum number of detours in a connected graph with minimum degree $k$ and order $n,$ and denote by $b(k,n)$ the minimum odd number of detours in such a graph. X. Zhan has posed the problem of determining $a(k,n)$ and $b(k,n).$ It is known that $a(2,n)=4$ for $n\\ge 4$ and $b(2,n)=9$ for $n\\ge 9.$ In this paper we prove that $a(3,n)=36$ for $n\\ge 18,$ $a(k,n)\\le (k!)^2$ for $n\\ge k^2+2k+3$ and $b(3,n)\\le 225$ for $n\\ge 11.$ We also pose several related unsolved problems.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-27","reactions":{}}