Pebble exchange on graphs

Let GG and HH be graphs with the same number of vertices. We introduce a graph puzzle (G,H)(G,H) in which GG is a board graph   and the set of vertices of HH is the set of pebbles. A configuration   of HH on GG is defined as a bijection from the set of vertices of GG to that of HH. A move   of pebbles is defined as exchanging two pebbles which are adjacent on both GG and HH. For a pair of configurations ff and gg, we say that gg is equivalent   to ff if ff can be transformed into gg by a sequence of finite moves. If GG is a 4×44×4 grid graph and HH is a star, then the puzzle (G,H)(G,H) corresponds to the well-known 1515-puzzle. A puzzle (G,H)(G,H) is called feasible   if all the configurations of HH on GG are mutually equivalent. In this paper, we study the feasibility of the puzzle under various conditions. Among other results, for the case where one of the two graphs GG and HH is a cycle, a necessary and sufficient condition for the feasibility of the puzzle (G,H)(G,H) is shown.