The graph relabeling problem and its variants
Geir Agnarsson, Raymond Greenlaw, Sanpawat Kantabutra · 2008
Graph labeling is a classic problem in mathematics and computing. In this paper we study an interesting set of graph labeling problems which were first introduced by Kantabutra (2007). The general problem, here called the graph relabeling problem, is to take an undirected graph G=(V, E), two labelings l1and l2of G, and a label switching function f and then to determine the complexity of transforming the labeling l1into l2using f. We define several variants of the problem and discuss their complexity. We give tight bounds for one version of the problem on chains, and show another version is NP-complete. These problems have applications in areas such as bioinformatics, networks, and VLSI.