2025/10/30 by Darbinyan, Samvel Kh.
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2510.26273
Let D be a digraph of order p≥5 with minimum degree at least p-1 and with minimum semi-degree at least p/2-1. In his excellent and renowned paper, ``Long Cycles in Digraphs" (Proc. London Mathematical Society (3), 42 (1981), Thomassen fully characterized the following for p=2n+1: (i) D has a cycle of length at least 2n; and (ii) D is Hamiltonian. Motivated by this result, and building on some of the ideas in Thomassen's paper, we investigated the Hamiltonicity (when p is even) and pancyclcity (when p is arbitrary) such digraphs. We have given a complete description of whether such digraphs are Hamiltonian (p is even), are pancyclic (p is arbitrary). Since the proof is very long, we have divided it into three parts. In this paper, we provide a full description of the following: (iii) for k=3 and k=4, the digraph D contains a cycle of length k; and (iv) the digraph D contains a pre-Hamiltonian cycle, i.e. a cycle of length p-1.