Properties of Johnson Schemes

摘要

In this paper, we discuss and prove properties of the Johnson scheme G(n, k), with vertex set all subsets of {1,2,..., n}, and (x, y) is an edge whenever |x ∩ y| = k - 1. We proved that it is Hamiltonian by constructing an algorithm that will generate a Hamiltonian cycle given n and k. We also proved that there is an embedding from the Johnson scheme to a subgraph of the hypercube. We also proved that there is a range of lengths in a given Johnson scheme such that it is a valid cycle length, that is, there is a cycle with that length in the graph. This paper may add to the current known properties of the Johnson scheme, that may help future network engineers to decide on a specific interconnection network to use.