Universität zu Köln

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

Preview

PDF diss__stefan_neuhaus.pdf Download (1MB)

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.