Playing with tokens (potentially infinite vertex capacity--Theoretical)

Abstract

In this paper, a basic token sliding puzzle in graphs (with infinite vertex capacities) has been studied. The rule is in each step (or time epoch) we are moving k tokens simultaneously, where k may be fixed or may be varied over a given set T. The reachability characterisations is done completely(Assuming no edge-swapping collision constraint). Then the edge swapping collision constraint is introduced (The basic motivation behind defining this type of collision is:- If two or more tokens travel through an edge in same direction, by stacking them one upon the other, collision can be avoided, and collision in vertices is avoided by the infinite capacity. So, if k tokens move simultaneously, the only unavoidable collision is when two tokens move through same edge but along opposite direction. This motivates to define edge swapping collision). Under this constraint, for some special classes of graphs , reachability characterisation is done. Then the idea is generalised from discrete set of tokens to non atomic measurable set of tokens when k (fixed) is less than total number of tokens and to any set of tokens when k = total number of tokens. This paper may open potential research direction in Computer Science and Measure Theoretic Combinatorics.