Produto Generalizado de Grafos e suas Aplicações na Geração de Soluções para o Problema Milenar das n-Damas

Autores

  • Oliver Kolossoski Universidade Federal do Paraná (UFPR), Programa de Pós-Graduação em Matemática, Curitiba, PR, Brasil https://orcid.org/0000-0003-2543-9346
  • Luiz Carlos Matioli Universidade Federal do Paraná (UFPR), Programa de Pós-Graduação em Métodos Numéricos em Engenharia, Curitiba, PR, Brasil https://orcid.org/0000-0002-6506-3550
  • Elvis Manuel Rodriguez Torrealba Universidade Federal do Paraná (UFPR), Programa de Pós-Graduação em Matemática, Curitiba, PR, Brasil https://orcid.org/0000-0001-7161-4083
  • Juliana Gomes da Silva Universidade Federal do Paraná (UFPR), Programa de Pós-Graduação em Matemática, Curitiba, PR, Brasil https://orcid.org/0000-0002-8715-914X

DOI:

https://doi.org/10.35819/remat2022v8i1id5379

Palavras-chave:

Problema (Modular) das n-Damas, Grafos, Teoria de Grafos, Produto de Grafos

Resumo

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

Não há dados estatísticos.

Biografia do Autor

Oliver Kolossoski, Universidade Federal do Paraná (UFPR), Programa de Pós-Graduação em Matemática, Curitiba, PR, Brasil

Luiz Carlos Matioli, Universidade Federal do Paraná (UFPR), Programa de Pós-Graduação em Métodos Numéricos em Engenharia, Curitiba, PR, Brasil

Elvis Manuel Rodriguez Torrealba, Universidade Federal do Paraná (UFPR), Programa de Pós-Graduação em Matemática, Curitiba, PR, Brasil

Juliana Gomes da Silva, Universidade Federal do Paraná (UFPR), Programa de Pós-Graduação em Matemática, Curitiba, PR, Brasil

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

2022-05-31

Como Citar

KOLOSSOSKI, O.; MATIOLI, L. C.; TORREALBA, E. M. R.; SILVA, J. G. da. Produto Generalizado de Grafos e suas Aplicações na Geração de Soluções para o Problema Milenar das n-Damas. REMAT: Revista Eletrônica da Matemática, Bento Gonçalves, RS, v. 8, n. 1, p. e3006, 2022. DOI: 10.35819/remat2022v8i1id5379. Disponível em: https://periodicos.ifrs.edu.br/index.php/REMAT/article/view/5379. Acesso em: 2 jul. 2022.

Edição

Seção

Matemática