Colored pebble motion on graphs

Let r , n and n 1 , … , n r be positive integers with n = n 1 + ⋯ + n r . Let X be a connected graph with n vertices. For 1 ≤ i ≤ r , let P i be the i -th color class of n i distinct pebbles. A configuration of the set of pebbles P = P 1 ∪ ⋯ ∪ P r on X is defined as a bijection from the set of vertices of X to P . A move of pebbles is defined as exchanging two pebbles with distinct colors on the two endvertices of a common edge. For a pair of configurations f and g , we write f ∼ g if f can be transformed into g by a sequence of finite moves. The relation ∼ is an equivalence relation on the set of all the configurations of P on X . We study the number c ( X , n 1 , … , n r ) of the equivalence classes. A tuple ( X , n 1 , … , n r ) is called transitive if for any configuration f and for any vertex u , a pebble f ( u ) can be moved to any other vertex by a sequence of finite moves. We determine c ( X , n 1 , … , n r ) for an arbitrary transitive tuple ( X , n 1 , … , n r ) .