# Construction of one graph from another - known ? (“Sokoban graph”, chips configurations)

Consider a [directed] graph and natural number "m". Let us construct new [directed] graph[s] from it as follows. There is one idea behind the construction, but one can play with details and get several constructions.

Vertices of new graph - all possible configurations of "m" ([non]-marked) chips on vertices (edges) of original graph [with/without] constraint that two chips should be in different positions.

Edge of new graph - two vertices are connected if one configuration of chips can be obtained from another in one "MOVE".

Where by "MOVE" I mean that we can move ONE chip from vertex of original graph to neighboring (edge)-vertex of original graph.

Question Is this construction(s) well-known ? what is name/refrence ? How properties of the original graph are related to the one of the new graph ?

Motivation: Such graph appears if one thinks on the question:

Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another

The solution to question above is related considering the construction above and searching if two vertices of the new graph are connected.

Roland Bacher in his answer describes similar idea which is directly related to sokoban game.

See also:

Path search algorithms on graphs

-
These are a little like lamplighter graphs. See arxiv.org/pdf/math/0403320v1.pdf. You just seem to forget where the lamplighter is and assume he switches at his current position moves and switches at the new one. –  Benjamin Steinberg Feb 17 at 16:13
add comment