Produto Generalizado de Grafos e suas Aplicações na Geração de Soluções para o Problema Milenar das n-Damas
DOI:
https://doi.org/10.35819/remat2022v8i1id5379Palavras-chave:
Problema (Modular) das n-Damas, Grafos, Teoria de Grafos, Produto de GrafosResumo
O produto de grafos de Kronecker generalizado foi introduzido por Figueroa-Centeno et al. (2008). Posteriormente, Baca et al. (2018) usaram-o para obter soluções do problema das n-damas em tabuleiros maiores a partir de soluções de tabuleiros de tamanho inferior. Neste artigo, generalizamos o produto de grafos e os resultados recentes de Baca et al. (2018), obtendo uma classe maior de soluções conhecendo antecipadamente soluções em tabuleiros de menor tamanho. Finalizamos o artigo apresentando algumas conjecturas a respeito das condições de obtenção de soluções compostas via produto de grafos.
Downloads
Referências
BACA, M.; LOPEZ, S. C.; MUNTANER-BATLE, F. A.; SEMANICOVA-FENOVCIKOVA. The n-Queens Problem: A New Approach. Technical Report, 2018.
BELL, J.; STEVENS, B. A. Survey of Known Results and Research Areas for n-Queens. Discrete Mathematics, v. 309, n. 1, p. 1-31, Jan. 2009. DOI: https://doi.org/10.1016/j.disc.2007.12.043.
BEZZEL, M. Proposal of 8-queens problem. Berliner Schachzeitung, v. 3, p. 363, 1848.
BLOOM, G.; LAMPIS, M.; MUNTANER-BATLE, F. A.; RIUS-FONT, M.; ARUMUGAM, S. Queen Labelings, AKCE International Journal of Graphs and Combinatorics, v. 8, n. 1, 2011. Available in: https://www.tandfonline.com/doi/abs/10.1080/09728600.2011.12088927. Access at: 30 May 2022.
BOLLOBAS, B. Modern Graph Theory. New York: Springer, 2002.
FIGUEROA-CENTENO, R. M.; ICHISIMA, R.; MUNTANER-BATLE, F. A.; RIUS-FONT, M. Labeling generating matrices. Journal of Combinatorial Mathematics and Combinatorial Computing, v. 67, p. 189-216, 2008.
LIONNET, F. J. E. Question 963. Jornales Annales de Matematiques, v. 8, p. 560, 1869.
LOPEZ, S. C.; ICHISIMA, R.; MUNTANER-BATLE, F. A.; RIUS-FONT, M. The Power of Digraph Products Applied to Labelings. Discrete Mathematics, v. 312, n. 2, p. 221-228, 28 Jan. 2012. DOI: https://doi.org/10.1016/j.disc.2011.08.025.
LOPEZ, S. C.; MUNTANER-BATLE, F. A. Graceful, Harmonious and Magic Type Labelings. New York: Springer, 2017.
MIKHAILOVSKI, D. New Explicit Solution to the N-Queens Problem and its Relation to the Millenium Problem. Technical Report, 2018. Available in: https://arxiv.org/abs/1805.07329. Access at: 30 May 2022.
PAULS, E. Das maximalproblem der Damen auf dem Schachbrete II. Deutsche Schachzeitung. Organ für das Gesammte Schachleben. v. 29, n. 9, p. 257-267, 1874.
POLYA, G. Uber die doppelt-periodischen Losungen des n-Damen-Problems. Matematische Unterhaltungen und Spiele, v. 2, p. 364-374, 1918.
RIVIN, I.; VARDI, I.; ZIMMERMAN, P. The n-Queens Problem. The Americal Mathematical Monthly, v. 101, n. 7, p. 629-639, 1994. DOI: https://doi.org/10.1080/00029890.1994.11997004.
Downloads
Publicado
Edição
Seção
Licença
Copyright (c) 2022 REMAT: Revista Eletrônica da Matemática
Este trabalho está licenciado sob uma licença Creative Commons Attribution 4.0 International License.
Os autores detêm os direitos autorais dos artigos publicados e concedem à REMAT o direito de primeira publicação e distribuição de partes ou do trabalho como um todo com o objetivo de promover a revista. Os autores são autorizados a distribuir a versão publicada do artigo, como por exemplo em repositórios institucionais, desde que façam menção de publicação inicial nesta revista a partir da disponibilização do DOI do artigo.
Os artigos são publicados sob a licença Creative Commons Attribution 4.0 International License (CC BY 4.0). Isso permite que o conteúdo seja utilizado para criação de novos trabalhos, tanto para fins comerciais quanto não comerciais, desde que seja feita a devida atribuição ao autor original, conforme especificado na licença.
Como Citar
https://orcid.org/0000-0002-0893-7426
