Digraphs with Isomorphic Underlying and Domination Graphs: 4-cycles and Pairs of Paths

Authors

Kim A. S. Factor, Marquette UniversityFollow
Larry J. Langley, University of the Pacific

Document Type

Article

Language

eng

Format of Original

17 p.

Publication Date

2010

Publisher

University of Queensland Centre for Discrete Mathematics and Computing

Source Publication

Australasian Journal of Combinatorics

Source ISSN

1034-4942

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.

Comments

Published version. Australasian Journal of Combinatorics, Volume 48 (2010), Publication’s website. © 2010 University of Queensland Centre for Discrete Mathematics and Computing. Used with permission.

Recommended Citation

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.
https://epublications.marquette.edu/mscs_fac/7