% Begin of file
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Encoding: ASCII
% Tex format: LaTeX
% Last modified: August 5, 2003
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
Most graph labeling\index{graph labeling} methods trace their origin to one introduced by Rosa
\cite{Ro1} in 1967, or one given by Graham and Sloane \cite{GS} in 1980.
Rosa \cite{Ro1} called a function $f$ a {\em{$\beta$-valuation}}\index{$\beta$-valuation}
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\index{label} ${\mid}{f(x) - f(y)}{\mid}$,
the resulting edge labels are distinct.
Golomb \cite{Go} subsequently called such labelings {\em graceful}
\index{graceful graph}\subindex{graph}{graceful}and this is
now the popular term.
Rosa introduced $\beta$-valuations\index{$\beta$-valuation} as well as a number of other labelings
as tools for decomposing\index{decomposition} the complete graph into isomorphic subgraphs.
In particular, $\beta$-valuations originated as a means of attacking the
conjecture of Ringel \cite{Ri} that $K_{2n+1}$ can be decomposed into $2n+1$
subgraphs that are all isomorphic to a given tree\index{tree} with $n$ edges.
Although an unpublished result of Erd\H{o}s says that most graphs are not
graceful (cf. \cite{GS}), most graphs that have some sort of regularity of
structure are graceful. Sheppard \cite{Sh} has shown that there are exactly
$q!$ gracefully labeled graphs with $q$ edges. Balakrishnan and
Sampathkumar \cite{BS} have shown that every graph is a subgraph of a graceful
graph.
Rosa \cite{Ro1} has identified essentially three reasons why a graph fails to
be
graceful: (1) $G$ has ``too many vertices" and ``not enough edges", (2) $G$
``has too many edges", and (3) $G$ ``has the wrong parity".
An infinite class of graphs that are not graceful for the second reason
is given in \cite{BG}.
As an example of the third condition Rosa \cite{Ro1} has shown that if every
vertex has
even degree and the number of edges is congruent to
1 or 2 (mod 4) then the
graph is not graceful. In particular,
the cycles\index{cycle} $C_{4n + 1}$ and $C_{4n + 2}$ are not graceful.
Harmonious graphs naturally arose in the study by Graham and Sloane \cite{GS}
of modular versions of additive bases problems stemming from error-correcting codes.
They defined a graph $G$ with $q$ edges to be {\em harmonious}
\index{harmonious graph}\subindex{graph}{harmonious}
if there is an injection $f$ 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.
Analogous to the ``parity" necessity condition for graceful graphs, Graham and
Sloane proved that if a harmonious graph has an even number $q$ of edges and
the degree of every vertex is divisible by $2^k$ then $q$ is
divisible by $2^{k+1}$.
Thus, for example, a book\index{book} with seven
pages (i.e., the cartesian product of
the complete bipartite graph $K_{1,7}$ and a path of length 1) is not
harmonious. Liu and Zhang \cite{LZ2} have generalized this condition as follows:
if a harmonious graph with $q$ edges has degree sequence
$d_1, d_2, \ldots, d_p$ then
gcd($d_1, d_2, \ldots d_p, q$) divides $q(q-1)/2$.
They have also proved that every graph is a subgraph of a harmonious graph.
Over the past three decades in excess of 600 papers have spawned a
bewildering
array of graph labeling methods. Despite the unabated procession of
papers, there are few general results on graph labelings. Indeed, the
papers focus on particular classes of graphs and methods, and feature ad
hoc arguments.
In part because many of the papers have appeared in journals not
widely available,
frequently the same classes of graphs have been done by several
authors.
In this article, we survey what is
known about numerous graph labeling methods.
The author requests that he be sent preprints and
reprints as well as corrections for inclusion in the updated versions of the survey.
Earlier surveys, restricted to one or two labeling methods, include \cite{Be},
\cite{Bl}, \cite{KRT2}, \cite{Ga2}, and \cite{Ga4}.
The extension of graceful labelings to directed graphs\subindex{graph}{directed}
arose in the
characterization of finite neofields by Hsu and Keedwell \cite{HK1}, \cite{HK2}.
The relationship between graceful digraphs and a variety of algebraic
structures including cyclic difference sets, sequenceable groups,
generalized complete mappings, near-complete mappings and neofields is
discussed in \cite{BH1}, \cite{BH2}.
The connection between graceful labelings and perfect systems of
difference sets is given in \cite{BKT}.
Labeled graphs serve as useful models for a broad range of applications such
as: coding theory, x-ray crystallography, radar, astronomy, circuit design,
communication network addressing and data base management--see \cite{BG1}, \cite{BG2} and
\cite{Sut} for details.
Terms and notation not defined below follow that used in \cite{CL} and \cite{Ga2}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% End of file