On the Graceful Game

• Luisa Frickes Universidade Federal Fluminense
• Simone Dantas Universidade Federal Fluminense
• Atílio G. Luiz Universidade Federal do Ceará

Resumo

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.

Palavras-chave: Jogo gracioso, rotulação graciosa, rotulação de grafos, jogos de rotulação

Referências

Abhyankar, V. J. (2002). Direct Methods of Gracefully Labeling Graphs. Ph.d. thesis, University of Mumbai.

Ayel, J. and Favaron, O. (1984). Helms are graceful. in Progress in Graph Theory (Waterloo, Ont., 1982), Academic Press, Toronto, Ont., pages 89–92.

Berlekamp, E. R., Conway, J. H., and Guy, R. K. (1982). Winning ways for your mathematical plays. Academic Press.

Frickes, L., Dantas, S., and Luiz, A. G. (2019). The graceful game. In Proceedings of 17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2019), volume 1, pages 41–44.

Frucht, R. (1979). Graceful numbering of wheels and related graphs. Annals of the New York Academy of Sciences, 319(1):219–229.

Frucht, R. and Gallian, J. A. (1988). Labeling prisms. Ars Combinatoria, 26:69–82.

Golomb, S.W. (1972). How to number a graph. In Read, R. C., editor, Graph Theory and Computing, pages 23–37. Academic Press, New York.

Harary, F., Hayes, J. P., andWu, H.-J. (1988). A survey of the theory of hypercube graphs. Computers & Mathematics with Applications, 15(4):277–289.

Hoede, C. and Kuiper, H. (1987). All wheels are graceful. Utilitas Mathematica, 14:311.

Kang, Q., Liang, Z.-H., Gao, Y.-Z., and Yang, G.-H. (1996). On labeling of some graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 22:193–210.

Kho, K. M., Rogers, D. G., Teo, H. K., and Yap, K. Y. (1980). Graceful graphs: some further results and problems. Congressus Numerantium, 29:559–571.

Kotzig, A. (1981). Decompositions of complete graphs into isomorphic cubes. Journal of Combinatorial Theory, B 31:292–2496.

Ma, K. J. and Feng, C. J. (1984). On the gracefulness of gear graphs. Mathematics in Practice and Theory, pages 72–73.

Rosa, A. (1967). On certain valuations of the vertices of a graph. Theory of Graphs, International Symposium, Rome, July 1966, pages 349–355.

Rosa, A. (1988). Cyclic steiner triple systems and labelings of triangular cacti. Scientia, 1:87–95.

Tuza, Z. (2017). Graph labeling games. Electronic Notes in Discrete Mathematics, 60:61–68.