On the Graph Relabeling Problem

Geir Agnarsson, Raymond Greenlaw, Sanpawat Kantabutra

Abstract

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.