3-ARC-DOMINATED DIGRAPHS

An oriented simple digraph D = (V, A) with the minimum outdegree d is called d-arc-dominated if for every arc (x, y) is an element of A there is a vertex u is an element of V with the outdegree d such that both (u, x) is an element of A and (u, y) is an element of A hold. At the 20th British combinatorial conference, Lichiardopol posed the problem of characterizing d-arc-dominated digraphs. He also has posed the conjecture that a d-arc-dominated digraph with d >= 2k - 1 contains k vertex-disjoint directed cycles. In this paper, we give a characterization for 3-arc-dominated digraphs. Based on this characterization, we classify all 3-arc-dominated digraphs and show that the above conjecture is true when d = 3.