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

Described within is the problem of finding near-minimum dominating subsets of agiven graph by rook domains. Specifically, we study the graphs of the kind ZnpandZn3?Zm2and introduce a simulated annealing algorithm to compute upper bounds ofthe size of minimum dominating subsets.We demonstrate the eff...

Full description

Main Author: Piza Volio, Eduardo
Format: Artículo
Language: Español
Published: 2015
Online Access: http://revistas.ucr.ac.cr/index.php/matematica/article/view/243
http://hdl.handle.net/10669/12888
Summary: Described within is the problem of finding near-minimum dominating subsets of agiven graph by rook domains. Specifically, we study the graphs of the kind ZnpandZn3?Zm2and introduce a simulated annealing algorithm to compute upper bounds ofthe size of minimum dominating subsets.We demonstrate the effectiveness of the algorithm by comparing the results with apreviously studied class of graphs, including the so-called ?football pool? graphs andothers. We give some new upper bounds for graphs of the kind Znp, with p 4. Thecodes of some dominating subsets are given in an appendix.Keywords: Graph domination, simulated annealing, football pool problem, combinatorics.