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
Como Citar
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.
Este é um periódico em acesso aberto, o que significa que todo o conteúdo está disponível gratuitamente, sem custo para o usuário ou sua instituição. Os usuários têm permissão para ler, baixar, copiar, distribuir, imprimir, pesquisar ou vincular os textos completos dos artigos, ou usá-los para qualquer outra finalidade legal, sem solicitar permissão prévia da revista ou do autor. Esta declaração está de acordo com a definição da BOAI de acesso aberto.