On the Graceful Game

dc.creatorRicardo, Luisa de Oliveira Frickes
dc.creatorDantas, Simone
dc.creatorLuiz, Atilio G.
dc.date2020-11-15
dc.date.accessioned2022-10-04T23:27:19Z
dc.date.available2022-10-04T23:27:19Z
dc.identifierhttps://seer.ufrgs.br/index.php/reic/article/view/105665
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/3873521
dc.descriptionA graceful labeling of a graph G with m edges consists in labeling the vertices of G with distinct integers from 0 to m such that, when each edge is assigned the absolute difference of the labels of its endpoints, all induced edge labels are distinct. Rosa established two well known conjectures: all trees are graceful (1966) and all triangular cacti are graceful (1988). In order to contribute to both conjectures we study these problems in the context of graph games. The graceful game was introduced by Tuza in 2017 as a two-players game on a connected graph in which the players Alice and Bob take turns labeling the vertices with distinct integers from 0 to m. Alice’s goal is to gracefully label the graph as Bob’s goal is to prevent it from happening. In this work, we present the first results in this area by showing winning strategies for Alice and Bob in complete graphs, paths, cycles, complete bipartite graphs, caterpillars, prisms, wheels, helms, webs, gear graphs, hypercubes and some powers of paths.pt-BR
dc.formatapplication/pdf
dc.languagepor
dc.publisherRevista Eletrônica de Iniciação Científica em Computaçãopt-BR
dc.relationhttps://seer.ufrgs.br/index.php/reic/article/view/105665/59142
dc.rightsCopyright (c) 2020 Revista Eletrônica de Iniciação Científica em Computaçãopt-BR
dc.sourceRevista Eletrônica de Iniciação Científica em Computação; v. 18 n. 3 (2020): Edição Especial: Artigos do 39º Concurso de Trabalhos de Iniciação Científica (CSBC/CTIC)pt-BR
dc.source1519-8219
dc.subjectgraceful gamept-BR
dc.subjectgraceful labelingpt-BR
dc.subjectgraph labelingpt-BR
dc.subjectlabeling gamespt-BR
dc.titleOn the Graceful Gamept-BR
dc.typeinfo:eu-repo/semantics/article
dc.typeinfo:eu-repo/semantics/publishedVersion


Este ítem pertenece a la siguiente institución