Title

Characterization of Digraphs with Equal Domination Graphs and Underlying Graphs

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

Discrete Mathematics, Vol. 308, No. 1 (January 2008): 34-43. DOI.