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

Descripción completa

Autor Principal: Piza Volio, Eduardo
Formato: Artículo
Idioma: Español
Publicado: 2015
Acceso en línea: http://revistas.ucr.ac.cr/index.php/matematica/article/view/243
http://hdl.handle.net/10669/12888
Sumario: 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.