Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650096 | Discrete Mathematics | 2008 | 10 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Kim A.S. Factor, Larry J. Langley,