Abstract
A longest path in a graph is called a detour. It is not difficult to see that a connected graph of minimum degree at least 2 and order at least 4 has at least four 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 nine, and this lower bound can be attained for every order. Thus the possibilities three, five and seven are never attained. The reason for this interesting phenomenon does not seem obvious, in view of the fact that the numbers four, six, eight and nine can be attained. Two related problems are posed.
| Original language | English |
|---|---|
| Pages (from-to) | 85-93 |
| Number of pages | 9 |
| Journal | Australasian Journal of Combinatorics |
| Volume | 90 |
| State | Published - Oct 2024 |