Search

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×Zm2and 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. En este artículo se describe el problema de la dominación de los grafos del tipo Znp y mezclas del tipo Zn3×Zm2 a través de subconjuntos dominantes de vértices de tamaño mínimo. Se introduce un algoritmo del tipo de recocido simulado para calcular cotas superiores de la cardinalidad de estos subconjuntos dominantes minimales. Se demuestra la eficiencia del algoritmo al comparar los resultados obtenidos con los ya conocidos correspondientes a algunas clases de grafos, entre ellos los llamados grafos del “football pool problem”. Se establecen cotas superiores en algunos de los grafos del tipo Znp,con p ≥ 4. Los códigos de algunos subconjuntos dominantes se incluyen en un apéndice.