Eigenschaften kleinster dominierender Mengen und Dominanzzahlen von Damengraphen

Neuhaus, Stefan (2009) Eigenschaften kleinster dominierender Mengen und Dominanzzahlen von Damengraphen. PhD thesis.

Abstract

We consider the problem of determining the size gamma (Q_n) of a minimum dominating set and the size i(Q_n) of an independent minimum dominating set of the queens graph Q_n . Every vertex v in V(Q_n) of the graph Q_n corresponds to a square of the (nxn) 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 we show: gamma (Q_n) = (n+1)/2 for 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, 221, and i(Q_n) = (n+1)/2 for n = 117, 121, 129, 141, 145, 157, 161, 165, 177, 185, 189. We provide a computer proof of gamma (Q_n) = i(Q_n) = n/2 + 1 for n = 20, 22, 24, 26, 28, 32, 34, 36, 38, 40, 42, 44, 46, 102, 110, 118, i(Q_n) = (n+1)/2 + 1 for n = 19, 23, 27, 31, and gamma (Q_n) = n/2 + 1 for n = 26, 134, 142, 150, 158, 166, 174, 182, 190, 198, 214, and 222.


Actions:
Download: [img] PDF - Published Version
Download (1342Kb) | Preview
Export as:
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2009-593
Depositing User: Stefan Neuhaus
Date Deposited: 03 Dec 2009 00:00
Last Modified: 19 Dec 2011 09:44
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/593