Graph Relabeling with Privileged Edge Labels

This paper describes a new problem in graph theory called the graph relabeling with privileged edge labels problem. Given a simple and connected graph G = (V, E), two labelings L and L´ of G, a privileged label assignment P, the problem is to make a series of transformations from G(L) to G(L´), where G(L) is the graph G with a labeling L. The transformation in consideration here is a flip operation. A flip operation allows a pair of labels in two adjacent nodes to exchange places if a certain condition is met. In this paper we show that this problem in general is insolvable. For solvable instances, this problem is shown to be NP-complete. Potential applications and open problems are also discussed.