Characterization of digraphs with equal domination graphs and underlying graphs
| Autor: | Kim A. S. Factor, Larry J. Langley |
|---|---|
| Jazyk: | angličtina |
| Předmět: |
Discrete mathematics
Vertex (graph theory) Mathematics::Combinatorics Two-step graph Domination graph Digraph Directed graph Underlying graph Graph Theoretical Computer Science Combinatorics Computer Science::Discrete Mathematics Biorientation Discrete Mathematics and Combinatorics Neighborhood graph Computer Science::Data Structures and Algorithms Mathematics |
| Zdroj: | Discrete Mathematics. (1):34-43 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2007.03.042 |
| Popis: | A domination graph of a digraph D, dom(D), is created using the vertex set of D and edge {u,v}@?E[dom(D)] whenever (u,z)@?A(D) or (v,z)@?A(D) for every other vertex [email protected]?V(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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|