On d-arc-dominated Oriented Graphs

We consider only digraphs that are oriented graphs, meaning orientations of simple finite graphs. An oriented graph D = (V, A) with minimum outdegree d is called d-arc-dominated if for every arc (x, y) ∈ A there is a vertex u ∈ V with outdegree d such that both (u, x) ∈ A and (u, y) ∈ A hold. In this paper, we show that for any integer d ≥ 3 the girth of a d-arc-dominated oriented graph is less than or equal to d. Moreover, for every integer t with 3 ≤ t ≤ d there is a d-arc-dominated oriented graph with girth t. We also give a characterization for oriented graphs with both minimum outdegree and girth d to be d-arc-dominated and classify all d-arc-dominated d-circular oriented graphs with girth d. © 2013 Springer Japan.