Digraphs with Isomorphic Underlying and Domination Graphs: Pairs of Paths

Kim A. S. Factor1, Larry J. Langley2
1Marquette University P.O. Box 1881, Milwaukee, WI 53201-1881
2University of the Pacific 3601 Pacific Avenue, Stockton, CA 95211

Abstract

The domination graph of a digraph \( D \), denoted \( \text{dom}(D) \), is created using the vertex set of \( D \) and edge \( uv \in E(\text{dom}(D)) \) whenever \( (u,z) \in A(D) \) or \( (v,z) \in A(D) \) for any other vertex \( z \in V(D) \). Specifically, we consider directed graphs whose underlying graphs are isomorphic to their domination graphs. In particular, digraphs are completely characterized where \( UG^c(D) \) is the union of two disjoint paths.