On the Graph Relabeling Problem

We study the Graph Relabeling Problem- given an undirected, connected, simple graph G = ( V,E ), two labelings L and L' of the vertices of G , and a label flip operation that interchanges the labels on adjacent vertices, determine the complexity in terms of the number of flips of transforming L into L' . First we review the well-known classic case when G is a simple path. We then study the case when G is the star and define a parameter that explicitly measures the complexity of transforming one labeling into another. This value corresponds to computing the exact distance between two vertices in the corresponding Cayley graph . Lastly we explore relabelings with privileged labels , and provide a precise characterizations of when these problems are solvable. This work has applications in areas such as bioinformatics, networks, and VLSI.