# 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: PDF - Published Version Download (1MB) | Preview View Item (Login required)
Content information:
Item Type: Thesis (PhD) 0 (Google Scholar) | queens graph queens domination domination dominating set minimum dominating set domination number orthodox cover 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C10 Integer programming 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C05 Linear programming 68-XX Computer science > 68Rxx Discrete mathematics in relation to computer science > 68R05 Combinatorics 05-XX Combinatorics > 05Cxx Graph theory > 05C69 Dominating sets, independent sets, cliques Institute of Computer Science > Computer Science Department - Prof. Dr. SchraderMathematical Institute > Prof. Dr. Faigle Author
Deposit Information:
ZAIK Number: zaik2009-593 Stefan Neuhaus 03 Dec 2009 00:00 19 Dec 2011 09:44 http://e-archive.informatik.uni-koeln.de/id/eprint/593