Resumen

En este art´?culo se describe el problema de la dominaci´on de los grafos del tipo Znp
y mezclas del tipo Zn3
×Zm2
a trav´es de subconjuntos dominantes de v´ertices de tama˜no
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´odigos de algunos subconjuntos dominantes se
incluyen en un ap´endice.
Palabras clave: Dominaci´on de grafos, recocido simulado, problema de las apuestas en
f´utbol, combinatoria.