Universität zu Köln

Eigenschaften kleinster dominierender Mengen und Dominanzzahlen von Damengraphen

Neuhaus, Stefan (2009) Eigenschaften kleinster dominierender Mengen und Dominanzzahlen von Damengraphen. PhD thesis, Universität zu Köln.

[img]
Preview
PDF
Download (1338Kb) | Preview

    Abstract

    Motiviert durch ein klassisches Schachproblem wird die Frage nach der Mächtigkeit einer kleinsten dominierenden Menge bzw. kleinsten unabhängigen dominierenden Menge des Damengraphen Q_n untersucht. Im Damengraph korrespondiert jeder Knoten zu einem Feld auf dem (n x n)-Schachbrett und zwei Knoten sind genau dann benachbart, wenn die zugehörigen Felder in derselben Zeile, Spalte oder Diagonale liegen. Im Detail wird gezeigt, dass jede p-Überdeckung von Q_n mit n>=19 beide langen Diagonalen durch zwei Eckfelder besetzt und daher diese Voraussetzung in der bekannten Charakterisierung mittels besetzter Diagonalen nicht einschränkend ist. Die Klasse der p-Überdeckungen wird zu orthodoxen Überdeckungen verallgemeinert und deren Relevanz durch Angabe entsprechender kleinster dominierender Mengen nachgewiesen. Für n=6(mod 8) mit n>=96 wird gezeigt, dass keine nicht-orthodoxe Überdeckung D von Q_n mit |D|=n/2 existiert. Zusammen mit einer hergeleiteten notwendigen Bedingung für die Existenz einer orthodoxen Überdeckung der Größe n/2 wird so in vielen Fällen die untere Schranke auf n/2 + 1 verschärft, was den Beweis einiger neuer Dominanzzahlen ermöglicht. Durch Angabe konkreter dominierender Mengen der Mächtigkeit (n+1)/2 werden Dominanzzahlen für folgende Instanzen bewiesen: n=43, 55, 83, 99, 107, 133, 137, 141, 143, 145, 149, 153, 157, 161, 163, 165, 169, 173, 177, 181, 183, 185, 189, 193, 197, 213 und 221. Durch Angabe konkreter unabhängiger dominierender Mengen der Mächtigkeit (n+1)/2 werden Dominanzzahlen für folgende Instanzen bewiesen: n=117, 121, 129, 141, 145, 157, 161, 165, 177, 185 und 189. Weiter wird ein Computerbeweis dafür erbracht, dass die Dominanzzahl folgender Instanzen n/2 + 1 beträgt: n=102, 110, 118, 126, 134, 142, 150, 158, 166, 174, 182, 190, 198, 214 und 222.

    Item Type: Thesis (PhD thesis)
    Translated abstract:
    AbstractLanguage
    We consider the problem of determining the size of a minimum dominating set and the size of an independent minimum dominating set of the queens graph Q_n. Every vertex of the graph Q_n corresponds to a square of the (n x n) chessboard and two squares are adjacent if and only if they are in the same row, column, or diagonal. We show that every p-cover of Q_n, n>=19, occupies both long diagonals that go through two corner squares and thus this condition in an alternative characterization of p-covers is nonrestrictive. We introduce a generalization of p-covers, namely orthodox covers, and show their relevance by stating some corresponding minimum dominating sets. For n=6(mod 8), n>=96, we show that there is no non-orthodox cover D of Q_n of size |D|=n/2. In conjunction with a necessary condition for the existence of an orthodox cover of size n/2, in many cases the lower bound is raised to n/2 +1, proving new domination numbers. Specifying appropriate dominating sets of size (n+1)/2 we show domination numbers for the following boards: n=43, 55, 83, 99, 107, 133, 137, 141, 143, 145, 149, 153, 157, 161, 163, 165, 169, 173, 177, 181, 183, 185, 189, 193, 197, 213, and 221. Specifying appropriate independent dominating sets of size (n+1)/2 we show domination numbers for the following boards: n=117, 121, 129, 141, 145, 157, 161, 165, 177, 185, and 189. We provide a computer proof for the fact, that the domination number is n/2 + 1 for the following boards: n=102, 110, 118, 126, 134, 142, 150, 158, 166, 174, 182, 190, 198, 214, and 222.English
    Creators:
    CreatorsEmail
    Neuhaus, Stefansneuhaus@zpr.uni-koeln.de
    URN: urn:nbn:de:hbz:38-29164
    Subjects: Data processing Computer science
    Uncontrolled Keywords:
    KeywordsLanguage
    Damen-Überdeckungsproblem , Damengraph , kleinste dominierende Menge , Dominanzzahl , orthodoxe ÜberdeckungGerman
    queens domination , queens graph , minimum dominating set , domination number , orthodox coverEnglish
    Faculty: Mathematisch-Naturwissenschaftliche Fakultät
    Divisions: Mathematisch-Naturwissenschaftliche Fakultät > Institut für Informatik
    Language: German
    Date: 2009
    Date Type: Completion
    Date of oral exam: 20 October 2009
    Full Text Status: Public
    Date Deposited: 12 Jan 2010 10:30:22
    Referee
    NameAcademic Title
    Schrader, RainerProf. Dr.
    URI: http://kups.ub.uni-koeln.de/id/eprint/2916

    Actions (login required)

    View Item