A dynamic survey of graph labeling. (English) Zbl 0953.05067

Gallian, Joseph A.

Electron. J. Comb. DS6, Dynamic Survey, 43 p. (1998).

Summary: A vertex labeling of a graph \(G\) is an assignment \(f\) of labels to the vertices of \(G\) that induces for 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,\ldots,q\}\) such that, when each edge \(xy\) is assigned the label \({\mid}{f(x) - f(y)}{\mid}\), 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 known about the various methods.

MSC:

05C78	Graph labelling (graceful graphs, bandwidth, etc.)
05-02	Research exposition (monographs, survey articles) pertaining to combinatorics

Keywords:

graceful labeling; harmonious labelings; graph labeling