Digraphs with isomorphic underlying and domination graphs: 4-cycles and pairs of paths

Authors

Kim A. S. Factor, Marquette UniversityFollow
Larry L. Langley, University of the PacificFollow

Document Type

Article

Publication Title

Australasian Journal of Combinatorics

Department

Mathematics

ISSN

1034-4942

Volume

48

First Page

25

Last Page

41

Publication Date

1-1-2010

Abstract

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 UG^c (D) = C₄ ∪ P_i ∪ P_j .

Recommended Citation

Factor, K. A., & Langley, L. L. (2010). Digraphs with isomorphic underlying and domination graphs: 4-cycles and pairs of paths. Australasian Journal of Combinatorics, 48, 25–41.
https://scholarlycommons.pacific.edu/cop-facarticles/640