The minimum number of detours in graphs

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)85-93
Number of pages9
JournalAustralasian Journal of Combinatorics
Volume90
StatePublished - Oct 2024

Fingerprint

Dive into the research topics of 'The minimum number of detours in graphs'. Together they form a unique fingerprint.

Cite this