Colored pebble motion on graphs

Let r, n and n1,…,nr be positive integers with n=n1+⋯+nr. Let X be a connected graph with n vertices. For 1≤i≤r, let Pi be the i-th color class of ni distinct pebbles. A configuration of the set of pebbles P=P1∪⋯∪Pr on X is defined as a bijection from the set of vertices of X to P. A move of pebbles...

Full description

Saved in:
Bibliographic Details
Published in:European journal of combinatorics 2012-07, Vol.33 (5), p.884-892
Main Authors: Fujita, Shinya, Nakamigawa, Tomoki, Sakuma, Tadashi
Format: Article
Language:English
Subjects:
Color
Combinatorial analysis
Exchanging
Graphs
Integers
Mathematical analysis
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let r, n and n1,…,nr be positive integers with n=n1+⋯+nr. Let X be a connected graph with n vertices. For 1≤i≤r, let Pi be the i-th color class of ni distinct pebbles. A configuration of the set of pebbles P=P1∪⋯∪Pr 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,n1,…,nr) of the equivalence classes. A tuple (X,n1,…,nr) 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,n1,…,nr) for an arbitrary transitive tuple (X,n1,…,nr).
ISSN:0195-6698
1095-9971
DOI:10.1016/j.ejc.2011.09.019