  We study the {\sc Graph Relabeling Problem}--given an undirected, connected,
simple graph $G = (V,E)$, two labelings $L$ and $L'$ of $G$, and label {\em
flip} or {\em mutation} functions determine the complexity of transforming or
evolving the labeling $L$ into<EMAIL_ADDRESS>The transformation of $L$ into $L'$ can
be viewed as an evolutionary process governed by the types of flips or
mutations allowed. The number of applications of the function is the duration
of the evolutionary period. The labels may reside on the vertices or the edges.
We prove that vertex and edge relabelings have closely related computational
complexities. Upper and lower bounds on the number of mutations required to
evolve one labeling into another in a general graph are given. Exact bounds for
the number of mutations required to evolve paths and stars are given. This
corresponds to computing the exact distance between two vertices in the
corresponding {\em Cayley graph}. We finally explore both vertex and edge
relabeling with {\em privileged labels}, and resolve some open problems by
providing precise characterizations of when these problems are solvable. Many
of our results include algorithms for solving the problems, and in all cases
the algorithms are polynomial-time. The problems studied have applications in
areas such as bioinformatics, networks, and VLSI.
