Domination parameters and their unique realizations

Fischermann, Miranca; Volkmann, Lutz

doi:HT013342361

Domination parameters and their unique realizations

Fischermann, Miranca (Author)

2002

Verantwortlichkeitsangabevorgelegt von Miranca Fischermann

ImpressumAachen : Publikationsserver der RWTH Aachen University 2002

UmfangVIII, 120 S.

Aachen, Techn. Hochsch., Diss., 2002

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Volkmann, Lutz (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2002-02-06

Online
URN: urn:nbn:de:hbz:82-opus-3186
URL: https://publications.rwth-aachen.de/record/59635/files/Fischermann_Miranca.pdf

Einrichtungen

Fakultät für Mathematik, Informatik und Naturwissenschaften (100000)

Inhaltliche Beschreibung (Schlagwörter)
Informatik (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Die vorliegende Arbeit beschäftigt sich mit der eindeutigen Realisierung verschiedener Dominanzparameter in Graphen und mit oberen Schranken dieser Parameter. Dominanzparameter geben minimale oder maximale Kardinalitäten bestimmter Teilmengen der Eckenmenge eines Graphen an. Zum Beispiel bestimmt die Dominanzzahl eines Graphen die minimale Kardinalität einer Menge, welche mindestens einen Nachbarn von jeder Ecke außerhalb der Menge enthält. Weitere in dieser Arbeit untersuchte Parameter sind Irredundanzzahl, unabhängige Dominanzzahl, Unabhängigkeitszahl, obere Dominanz- und obere Irredundanzzahl, Abstandsdominanzzahl, totale Dominanzzahl und Kantendominanzzahl. Wir sagen, dass ein Dominanzparameter in einem Graphen eine eindeutige Realisierung hat, falls die Menge, deren Kardinalität der Parameter wiedergibt, eindeutig ist. Nach einer Einleitung im ersten Kapitel wird in den Kapiteln 2 bis 5 für bestimmte Graphenklassen untersucht, unter welchen Bedingungen obige Dominanzparameter in einem gegeben Graphen eine eindeutige Realisierung haben. Diese Charakterisierungen führen teilweise zu effizienten Algorithmen, mit deren Hilfe man entscheiden kann, ob ein Parameter für einen Graphen aus der betrachteten Klasse eine eindeutige Realisierung hat.In den Kapiteln 6 bis 8 wird analysiert, welchen Einfluss die eindeutige Realisierung eines Parameters auf die obere Schranke des Parameters selbst und auf die obere Schranke der Kantenanzahl des Graphen hat. Außerdem werden in den letzten 3 Kapiteln für einige Parameter die Graphen charakterisiert, für die der Parameter seine obere Schranke annimmt. In diesem Zusammenhang werden sowohl die Schranken der Parameter mit eindeutiger Realisierung als auch die Schranken der Parameter ohne eindeutiger Realisierung betrachtet.

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.

OpenAccess:
PDF
(additional files)