# 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.

Download: |
PDF
- Published Version
Download (1MB) | Preview |
---|---|

Editorial actions: |
View Item (Login required) |

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 |