no. 16 · Tuesday 17 November 2026
A Chvátal–Erdős type condition for supereulerian digraphs with $α_{2}=4$
Abstract
A digraph is \textbf{supereulerian} if it contains a spanning closed trail. Let $α_2(D)$ denote the maximum cardinality of a vertex set inducing no 2-cycle. In this paper, we study the supereulerianity of digraphs with arc-strong connectivity at least 2. We identify a family $\mathcal H$ of nonsupereulerian 2-arc-strong digraphs and prove that every 2-arc-strong digraph $D$ with $α_2(D)\leq 4$ is supereulerian if and only if $D\notin\mathcal H$. In particular, every digraph $D$ satisfying $α_2(D) \le 4$ and $λ(D) \ge 3$ is supereulerian.
- comments
- 16 pages, 5 figures
- fields
- Combinatorics