A vertex labeling of a graph G is an assignment f of labels to the vertices of G that induces the each edge xy a label depending on the vertex labels f(x) and f(y). The two best known labeling methods are called graceful and harmonious labelings. A function f is called a graceful labeling of a graph G with q edges if f is an injection from the vertices of G to the set {0, 1, …, q} such that, when each edge xy is assigned the label |f(x) – f(y)|, the resulting edge labels are distinct. A function f is called harmonious if it is an injection from the vertices of G to the group of integers modulo q such that when each edge xy is assigned the label f(x) + f(y) (mod q), the resulting edge labels are distinct. When G is a tree, exactly one label may be used on two vertices. Over the past three decades many variations of graceful and harmonious labelings have evolved and about 200 papers have been on the subject of graph labeling. In this article we survey what is known about the various methods.
