Sufficient conditions for a digraph to contain: a pre-Hamiltonian cycle and cycles of lengths 3 and 4
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917050289487872 |
|---|---|
| author | Darbinyan, Samvel Kh. |
| author_facet | Darbinyan, Samvel Kh. |
| contents | Let $D$ be a digraph of order $p\geq5$ 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_26273 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sufficient conditions for a digraph to contain: a pre-Hamiltonian cycle and cycles of lengths 3 and 4 Darbinyan, Samvel Kh. Combinatorics Let $D$ be a digraph of order $p\geq5$ 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$. |
| title | Sufficient conditions for a digraph to contain: a pre-Hamiltonian cycle and cycles of lengths 3 and 4 |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2510.26273 |