کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653892 | 1632796 | 2012 | 9 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Colored pebble motion on graphs Colored pebble motion on graphs](/preview/png/4653892.png)
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).
Journal: European Journal of Combinatorics - Volume 33, Issue 5, July 2012, Pages 884–892