Shuffle-Exchange Graph


A shuffle-exchange graph is a nonsimple graph (due to the existence of graph loops) whose vertices are length n binary strings with an edge from w to w^' if

1. w^' differs from w in its last bit, or

2. w^' is obtained from w by a left or right cyclic shift.

The n-dimensional shuffle-exchange graph is implemented as ShuffleExchangeGraph[n] in the Wolfram Language package Combinatorica` .

For n=1, 2, ..., the shuffle exchange graphs with self-loops removed are isomorphic to P_2, P_4, 8_(3429), ..., where P_n is a path graph and n_k denotes the kth n-vertex graph in the ordering of McKay.

See also

Star Graph

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Shuffle-Exchange Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications