Artmann, Sarah ; Göring, Frank ; Harant, Jochen ; Rautenbach, Dieter ; Schiermeyer, Ingo : Random Procedures for Dominating Sets in Graphs
- Author(s):
-
Artmann, Sarah
Göring, Frank
Harant, Jochen
Rautenbach, Dieter
Schiermeyer, Ingo
- Title:
- Random Procedures for Dominating Sets in Graphs
- Electronic source:
-
application/pdf
- Preprint series:
- Technische Universität Chemnitz, Fakultät für Mathematik (Germany). Preprint 10, 2008
- Mathematics Subject Classification:
-
05C69 [ Dominating sets, independent sets, cliques ] 60C05 [ Combinatorial probability ] - Abstract:
- We present and analyze some random prozedures for the construction of small dominating sets in graphs. Several upper bounds for the domination number of a graph are derived from these procedures.
- Keywords:
- domination; independence; probabilistic method
- Language:
-
English
- Publication time:
- 5 / 2008
