Three-arc graphs: Characterization and domination
Guangjun Xu, Sanming Zhou
Discrete Applied Mathematics | Elsevier | Published : 2015
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.
Related Projects (1)
Awarded by Australian Research Council
The authors would like to thank an anonymous referee for helpful comments and careful reading. Guangjun Xu was partly supported by the MIFRS and SFS scholarships of the University of Melbourne. Zhou was supported by the Australian Research Council (FT110100629).