Abstract
Catlin in 1988 indicated that there exist graph families F such that if every edge e in a connected graph G lies in a subgraph He of G isomorphic to a member in F, then G is supereulerian. In particular, if every edge of a connected graph G lies in a 3-cycle, then G is supereulerian. The purpose of this research is to investigate how Catlin's theorem can be extended to digraphs. A strong digraph D is supereulerian if D contains a spanning eulerian subdigraph. We show that there exists an infinite family of non-supereulerian strong digraphs each arc of which lies in a directed 3-cycle. We also show that there exist digraph families H such that a strong digraph D is supereulerian if every arc a of D lies in a subdigraph Ha isomorphic to a member of H. A digraph D is symmetric if (x,y)∈A(D) implies (y,x)∈A(D); and is symmetrically connected if every pair of vertices of D are joined by a symmetric dipath. A digraph D is partially symmetric if the digraph obtained from D by contracting all symmetrically connected components is symmetrically connected. It is known that a partially symmetric digraph may not be symmetrically connected. We show that symmetrically connected digraphs and partially symmetric digraphs are such families. Sharpness of these results is discussed.
•Jaeger-Catlin Theorem that every 4-edge-connected graph is supereulerian cannot be extended to digraphs.•Catlin Theorem that every connected triangular graph is supereulerian cannot be extended to digraphs.•There exist nontrivial digraph families such that if every arc of a strong digraph D lies in a member in the family, then D is supereulerian.