On the Graceful Game - Frickes, Luisa; Dantas, Simone; Luiz, Atílio G. (Anais do Concurso de Trabalhos de Iniciação Científica da SBC (CTIC-SBC); 2020: Anais do XXXIX Concurso de Trabalhos de Iniciação Científica da SBC, 2020)
Uma rotulação graciosa de um grafo G com m arestas é uma atribuição de inteiros distintos de 0 a m aos vértices de G de modo que, quando a cada aresta é atribuída a diferença absoluta dos rótulos de seus extremos, todos os rótulos de arestas são distintos. Alexander Rosa estabeleceu duas conjeturas bem conhecidas: todas as árvores são graciosas (1966) e todos os cactos triangulares são graciosos (1988). A fim de contribuir com essas duas conjeturas, investigamos a rotulação graciosa no contexto de jogos em grafos. O jogo gracioso foi introduzido por Tuza em 2017 como um jogo para dois jogadores em um grafo conexo no qual os jogadores, Alice e Bob, se revezam rotulando os vértices com números inteiros distintos de 0 a m. O objetivo de Alice é obter uma rotulação graciosa do grafo, enquanto o objetivo de Bob é impedir que isso aconteça. Neste trabalho, apresentamos os primeiros resultados nesta área, mostrando estratégias vencedoras para Alice e Bob em classes de grafos tais como os grafos completos, caminhos, ciclos, grafos bipartidos completos, caterpillars, prismas, rodas, grafos leme, grafos teia, grafos engrenagem, hipercubos e algumas potências de caminhos.