Graceful Labeling of Graphs
Autores
|
6136 |
2803,257,612
|
|
|
6137 |
2803,257,612
|
|
|
6138 |
2803,257,612
|
Informações:
Publicações do PESC
Em 1966, A. Rosa propôs uma nova coloração de grafos chamada coloração-B em que os vértices são coloridos com números distintos entre 0 a m, onde m é o número de arestas, tal que cada aresta é rotulada com o módulo da diferença das cores dos seus vértices extremos e cada um é único no grafo. Alguns anos depois, S. W. Golomb renomeou essa coloração de coloração graciosa, como é conhecida hoje em dia.
Esta definição permitiu que Rosa mostrasse que se toda árvore admitisse uma coloração graciosa, então uma conjectura de G. Ringel seria verdadeira. A partir disso, foi conjecturado que toda árvore fosse graciosa, a Conjectura das Árvores Graciosas.
Este trabalho apresenta alguns dos principais resultados em coloração graciosa de grafos e também apresenta esforços computacionais na direção da Conjectura das Árvores Graciosas. Inspirado por isso, nós também tomamos a abordagem computacional para estender a graciosidade de grafos cones generalizados.
In 1966, A. Rosa introduced a new graph labeling called B-labeling in which the vertices are labeled with distinct numbers chosen from 0 to m, where m is the number of edges, such that each edge is labeled with the absolute difference of the labels of its end vertices and it is unique in the graph. A few years later, S. W. Golomb renamed B-labeling as graceful labeling as it is known today.
This definition allowed Rosa to show that if every tree admits a graceful labeling, then a conjecture from G. Ringel would hold, from which it was conjectured that every tree is graceful, the Graceful Tree Conjecture.
This work presents some of the main results on graceful labeling of graphs and also presents computational efforts in the direction of the Graceful Tree Conjecture. Inspired by that, we also took the computational approach to extend the gracefulness of generalized cone graphs.