Characterization of digraphs with equal domination graphs and underlying graphs
- 作者：Kim A.S. Factor ; Larry J. Langley
- 关键词：Domination graph ; Underlying graph ; Biorientation ; Neighborhood graph ; Two-step graph
- 刊名：Discrete Mathematics
- 出版年：2008
- 期刊代码：47_0012365x
- 类别：cp
- 出版时间：6 January 2008
- 卷：308
- 期：1
- 页码：34-43
- 文件大小：209 K
摘要
A domination graph of a digraph D, dom(D), is created using the vertex set of D and edge d020712c685f3f536a4c50be9aa56a0f" title="Click to view the MathML source">{u,v}
E[dom(D)] whenever 13d811c431" title="Click to view the MathML source">(u,z)A(D) or (v,z)A(D) for every other vertex zV(D). The underlying graph of a digraph 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). The maximum and minimum number of single arcs in these digraphs, and their characteristics, is given.
E[dom(D)] whenever 13d811c431" title="Click to view the MathML source">(u,z)A(D) or (v,z)A(D) for every other vertex zV(D). The underlying graph of a digraph 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). The maximum and minimum number of single arcs in these digraphs, and their characteristics, is given.