Shuffling of tokens on a graph using local swaps Let $G= (V, E)$ be a non-regular connected graph whose degree is bounded. Suppose that each node contain a unique token.

I want to uniformly shuffle the tokens amongst the graph using only local swaps (i.e. exchange of the tokens between two adjacent nodes) ? Is there a lower bound known for this problem ?

The only idea I had is to use a random walk result, then to see how much swaps I need to "simulate" the effect of random walks transporting tokens on the graph.
Suppose your graph was a path.  I think then this problem becomes equivalent to sorting a random sequence of numbers in an array by swapping adjacent entries.  Even of all nodes are topology aware, you get a n^2 lower bound on the number of swaps (cannot do better than bubble sort which is n^2 even on a random input).