Journal article

Three-arc graphs: Characterization and domination

Guangjun Xu, Sanming Zhou

Discrete Applied Mathematics | Elsevier | Published : 2015

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.

University of Melbourne Researchers

Grants

Awarded by Australian Research Council


Funding Acknowledgements

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).