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

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 UGc (D) = C4 ∪ Pi ∪ Pj .

Share

COinS