Characterization of Digraphs with Equal Domination Graphs and Underlying Graphs

Authors

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

Document Type

Article

Language

eng

Format of Original

10 p.

Publication Date

1-2008

Publisher

Elsevier

Source Publication

Discrete Mathematics

Source ISSN

0012-365X

Original Item ID

doi: 10.1016/j.disc.2007.03.042

Abstract

A domination graph of a digraph D , dom(D)dom(D), is created using the vertex set of D and edge {u,v}∈E[dom(D)]{u,v}∈E[dom(D)] whenever (u,z)∈A(D)(u,z)∈A(D) or (v,z)∈A(D)(v,z)∈A(D) for every other vertex z∈V(D)z∈V(D). The underlying graph of a digraph DD, UG(D)UG(D), is the graph for which D is a biorientation. We completely characterize digraphs whose underlying graphs are identical to their domination graphs, UG(D)=dom(D)UG(D)=dom(D). The maximum and minimum number of single arcs in these digraphs, and their characteristics, is given.

Comments

Accepted version. Discrete Mathematics, Vol. 308, No. 1 (January 2008): 34-43. DOI. © 2008 Elsevier. Used with permission.

Recommended Citation

Factor, Kim A. S. and Langley, Larry J., "Characterization of Digraphs with Equal Domination Graphs and Underlying Graphs" (2008). Mathematics, Statistics and Computer Science Faculty Research and Publications. 310.
https://epublications.marquette.edu/mscs_fac/310