In the complement of a dominating set [Elektronische Ressource] / eingereicht von Christian Löwenstein

TECHNISCHE UNIVERSITAT ILMENAU FAKULTAT FUR MATHEMATIK UND NATURWISSENSCHAFTENINSTITUT FUR MATHEMATIKIn the Complement of a Dominating SetDissertationzur Erlangung des akademischen GradesDr. rer. nat.eingereicht vonDipl.-Math. Christian L owensteinInstitut fur MathematikTU IlmenauApril 2010Betreuender Hochschullehrer: Univ.-Prof. Dr. rer. nat. habil. Dieter Rautenbach(Technische Universit at Ilmenau)urn:nbn:de:gbv:ilm1-2010000233PrefaceMany authors have written on dominating sets (for references we refer to [29, 30]). Thedistribution of legions in the Roman empire or the placement of queens on chessboards areusually cited as the origins of domination theory. But only a few authors have written onthe complement of a dominating set, e.g. [18, 21, 41, 48]. They studied the minimum sizeof a dominating set whose complement contains a minimum dominating set. In this thesiswe study diverse sets that are contained in the complement of a suitable dominating set.It seems that in real life a set in the complement of a dominating set does not in uencethe dominating set. However, in this thesis the dominating set must usually cooperatewith the set in its complement, in order to reach a common goal, e.g. existence or smallcommon size.The set in the complement that is studied in Chapter 2 is a dominating set, too. Forgraphs without isolated vertices, Ore observed in 1962 (Theorem 2.1) that the complementof a minimal dominating set is also a dominating set.