Format of Original
University of Queensland Centre for Discrete Mathematics and Computing
Australasian Journal of Combinatorics
A domination graph of a digraph D, dom(D), is created using the vertex set of D, V(D). There is an edge uv in dom(D) whenever (u, z) or (v, z) is in the arc set of D, A(D), for every other vertex z ε V(D). For only some digraphs D has the structure of dom(D) been characterized. Examples of this are tournaments and regular digraphs. The authors have characterizations for the structure of digraphs D for which UG(D) = dom(D) or UG(D) ≅ dom(D). For example, when UG(D) ≅ dom(D), the only components of the complement of UG(D) are complete graphs, paths and cycles. Here, we determine values of i and j for which UG(D) ≅ dom(D) and UGC(D) = C4 υ Pi υ Pj.
Factor, Kim A. S. and Langley, Larry J., "Digraphs with Isomorphic Underlying and Domination Graphs: 4-cycles and Pairs of Paths" (2010). Mathematics, Statistics and Computer Science Faculty Research and Publications. 7.