Graph dominance by rook domains for Znp and Zn3 × Zm2 graphs

Abstract

Described within is the problem of finding near-minimum dominating subsets of a given graph by rook domains. Specifically, we study the graphs of the kind Znp and Zn3 ×Zm2 and introduce a simulated annealing algorithm to compute upper bounds of the size of minimum dominating subsets. We demonstrate the effectiveness of the algorithm by comparing the results with a previously studied class of graphs, including the so-called “football pool” graphs and others. We give some new upper bounds for graphs of the kind Znp , with p 4. The codes of some dominating subsets are given in an appendix. Keywords: Graph domination, simulated annealing, football pool problem, combinatorics.