Three-arc graphs: Characterization and domination

Abstract

An arc of a graph is an oriented edge and a 3-arc is a 4-tuple (v, u, x, y) of vertices such that both (v, u, x) and (u, x, y) are paths of length two. The 3-arc graph of a graph G is defined to have vertices the arcs of G such that two arcs uv, xy are adjacent if and only if (v, u, x, y) is a 3-arc of G. In this paper we give a characterization of 3-arc graphs and obtain sharp upper bounds on the domination number of the 3-arc graph of a graph G in terms that of G.