Domination parameters and their unique realizations

This thesis deals with domination parameters in graphs and in particular with their unique realization. Domination parameters measure the minimal or maximal cardinality of special subsets of the vertex set (or the edge set) of a graph. Concepts of domination considered in this thesis are irredundance, ordinary domination, independent domiantion, independence, upper domination, upper irredundance, distance domination, total domination und edge domination. We say, a domination parameter has a unique realization for a given graph if the set measured by the parameter is unique. Chapter 2 to 5 contain for several different domination parameters and special graph classes characterizations of those graphs for which the parameter has a unique realization. Some of these characterizations lead to polynomial time algorithms to decide whether a parameter has a unique realization for a given graph. In Chapter 6 to 8 the influence of the unique realization of a parameter to its upper bound and to the upper bound of the size of the graph is studied. Furthermore, in the last 3 chapters we present characterizations of those graphs for which a special domination parameter achieves its upper bound. In this context we consider parameters with unique realization as well as parameters without unique realization.

Grantor dc:publisher

Publikationsserver der RWTH Aachen University

Year dc:date

2002

Author dc:creator

• Fischermann, Miranca

Contributors dc:contributor

• Volkmann, Lutz

• info:eu-repo/classification/ddc/004
• Informatik

Statement dc:rights

• info:eu-repo/semantics/openAccess

Language dc:language

eng

Identifier

https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-121403%22

OAI identifier oai:identifier

oai:publications.rwth-aachen.de:59635