Abelian Group Labels on Hamiltonian Cycles

Abstract

We consider labeling edges of graphs with elements from abelian groups. Particular attention is given to graphs where the labels on any two Hamiltonian cycles sum to the same value. We find several characterizations for such labelings for cubes, complete graphs, and complete bipartite graphs. This extends work of [1, 8, 9, 10]. We also consider the computational complexity of testing if a labeled graph has this property and show it is NP-complete even when restricted to integer labelings of 3-connected, cubic, planar graphs with face girth at least five.