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.

Item Type:	Thesis (PhD thesis)
Translated title:	Title Language Properties of Minimum Dominating Sets and Domination Numbers of the Queens Graph English
Translated abstract:	Abstract Language 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:	Creators Email ORCID ORCID Put Code Neuhaus, Stefan sneuhaus@zpr.uni-koeln.de UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-29164
Date:	2009
Language:	German
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Uncontrolled Keywords:	Keywords Language Damen-Überdeckungsproblem , Damengraph , kleinste dominierende Menge , Dominanzzahl , orthodoxe Überdeckung German queens domination , queens graph , minimum dominating set , domination number , orthodox cover English
Date of oral exam:	20 October 2009
Referee:	Name Academic Title Schrader, Rainer Prof. Dr.
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/2916