Article ID Journal Published Year Pages File Type
4650096 Discrete Mathematics 2008 10 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,