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

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

Descripción completa

Detalles Bibliográficos
Autor principal:	Piza-Volio, Eduardo
Formato:	Online
Idioma:	spa
Publicado:	Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2004
Acceso en línea:	https://revistas.ucr.ac.cr/index.php/matematica/article/view/243

id	RMTA243
record_format	ojs
spelling	RMTA2432022-01-19T17:40:48Z Graph dominance by rook domains for Znp and Zn3 × Zm2 graphs Graph dominance by rook domains for Znp and Zn3 × Zm2 graphs Piza-Volio, Eduardo Graph domination simulated annealing football pool problem combinatorics Dominación de grafos recocido simulado problema de las apuestas en fútbol combinatoria 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. 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. Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA) 2004-08-01 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion Article application/pdf https://revistas.ucr.ac.cr/index.php/matematica/article/view/243 10.15517/rmta.v11i2.243 Revista de Matemática: Teoría y Aplicaciones; Vol. 11 No. 2 (2004): Revista de Matemática: Teoría y Aplicaciones; 55-70 Revista de Matemática: Teoría y Aplicaciones; Vol. 11 Núm. 2 (2004): Revista de Matemática: Teoría y Aplicaciones; 55-70 Revista de Matemática; Vol. 11 N.º 2 (2004): Revista de Matemática: Teoría y Aplicaciones; 55-70 2215-3373 1409-2433 spa https://revistas.ucr.ac.cr/index.php/matematica/article/view/243/223 Derechos de autor 2004 Revista de Matemática: Teoría y Aplicaciones
institution	Universidad de Costa Rica
collection	Revista de Matemática: Teoría y Aplicaciones
language	spa
format	Online
author	Piza-Volio, Eduardo
spellingShingle	Piza-Volio, Eduardo Graph dominance by rook domains for Znp and Zn3 × Zm2 graphs
author_facet	Piza-Volio, Eduardo
author_sort	Piza-Volio, Eduardo
description	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.
title	Graph dominance by rook domains for Znp and Zn3 × Zm2 graphs
title_short	Graph dominance by rook domains for Znp and Zn3 × Zm2 graphs
title_full	Graph dominance by rook domains for Znp and Zn3 × Zm2 graphs
title_fullStr	Graph dominance by rook domains for Znp and Zn3 × Zm2 graphs
title_full_unstemmed	Graph dominance by rook domains for Znp and Zn3 × Zm2 graphs
title_sort	graph dominance by rook domains for znp and zn3 × zm2 graphs
title_alt	Graph dominance by rook domains for Znp and Zn3 × Zm2 graphs
publisher	Universidad de Costa Rica, Centro de Investigación en Matemática Pura y Aplicada (CIMPA)
publishDate	2004
url	https://revistas.ucr.ac.cr/index.php/matematica/article/view/243
work_keys_str_mv	AT pizavolioeduardo graphdominancebyrookdomainsforznpandzn3zm2graphs
_version_	1811744066529918976

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

Ejemplares similares