Colored pebble motion on graphs

Let rr, nn and n1,…,nrn1,…,nr be positive integers with n=n1+⋯+nrn=n1+⋯+nr. Let XX be a connected graph with nn vertices. For 1≤i≤r1≤i≤r, let PiPi be the ii-th color class of nini distinct pebbles. A configuration of the set of pebbles P=P1∪⋯∪PrP=P1∪⋯∪Pr on XX is defined as a bijection from the set of vertices of XX to PP. 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 ff and gg, we write f∼gf∼g if ff can be transformed into gg by a sequence of finite moves. The relation ∼∼ is an equivalence relation on the set of all the configurations of PP on XX. We study the number c(X,n1,…,nr)c(X,n1,…,nr) of the equivalence classes. A tuple (X,n1,…,nr)(X,n1,…,nr) is called transitive if for any configuration ff and for any vertex uu, a pebble f(u)f(u) can be moved to any other vertex by a sequence of finite moves. We determine c(X,n1,…,nr)c(X,n1,…,nr) for an arbitrary transitive tuple (X,n1,…,nr)(X,n1,…,nr).