4 documents found

Dissertation
2010-06-14

Über die Dominanzzahl in Graphen unter Nutzung verschiedener Konzepte

Die Dominanzzahl in Graphen ist die minimale Mächtigkeit einer Knotenpunktmenge D, für die jeder Knoten entweder in D enthalten ist oder einen Nachbarn in D besitzt. Da das zugehörige Entscheidungsproblem NP-vollständig ist, versucht man obere Schranken für die Dominanzzahl in verschiedenen Graphenklassen...
Article / Chapter
CC BY-NC-ND 3.0
2010

Random procedures for dominating sets in bipartite graphs

Using multilinear functions and random procedures, new upper bounds on the domination number of a bipartite graph in terms of the cardinalities and the minimum degrees of the two colour classes are established.
Warsaw: De Gruyter Open, 2010
Article / Chapter
All rights reserved
2009-12-23

Constructing a dominating set for bipartite graphs in several rounds

Using the probabilistic method, new upper bounds on the domination number of a bipartite graph in terms of the cardinalities and the minimum degrees of the two colour classes are established.
Article / Chapter
All rights reserved
2008-04-16

Random procedures for dominating sets in graphs

We present and analyze some random procedures for the construction of small dominating sets in graphs. Several upper bounds for the domination number of a graph are derived from these procedures.