Routing and sorting on the graph G(n,k) of the Johnson Scheme - Ho, Hans Riyono (2001)
The graph G(n,k) of the Johnson Scheme which is also known as the "Slice of the Cube" is the undirected graph where the vertices are all the k-subsets of the fixed n-set. Two vertices A and B are adjacent if and only lA ^ Bl = k-1. This graph has been studied extensively and some properties have been found such as the hamiltonicity, diameter, connectivity and wide-diameter of the graph. In this thesis, we shall determine some more properties besides proving the hamiltonicity of the graph G(n, k) in another way. We construct algorithms to determine the complexity of one-to-one permutation routing, gossiping, and sorting on the graph. The complexity we get are O(nk squared), O (min(k,n-k)) and O(N), respectively, where N is the number of vertices.