γ-Excellent, critically dominated, end-dominated, and dot-critical trees are equivalent
| Autor: | David P. Sumner, Tamara Burton |
|---|---|
| Rok vydání: | 2007 |
| Předmět: |
Discrete mathematics
Vertex (graph theory) Dot 010102 general mathematics Neighbourhood (graph theory) 0102 computer and information sciences Domination 01 natural sciences Biconnected graph Critical Theoretical Computer Science Combinatorics Excellent 010201 computation theory & mathematics Graph power End Wheel graph Discrete Mathematics and Combinatorics Bound graph Regular graph 0101 mathematics Restrained Tree Complement graph Mathematics |
| Zdroj: | Discrete Mathematics. 307:683-693 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2006.02.016 |
| Popis: | A graph is γ-excellent if every vertex of the graph is contained in some minimum dominating set of the graph. A vertex v is critical in G if the domination number of G-v is smaller than that of G. The graph G is dot-critical if contracting any edge of G produces a graph with smaller domination number. G is critically dominated if the set of critical vertices forms a dominating set for G. In this paper we show that these three properties, along with several others, are equivalent for trees on at least four vertices. We also provide a constructive characterization of these trees. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect