The Complexity of the Evolution of Graph Labelings

Geir Agnarsson, Raymond Greenlaw, Sanpawat Kantabutra

We study the {\sc Graph Relabeling Problem}--given an undirected, connected, simple graph $G=(V,E)$, two labelings $L$ and $L^{\prime }$ of $G$, and label {\em flip} or {\em mutation} fun…