Some graph properties of the Hamming and the Johnson schemes - Solano, Geoffrey A. (2005)
The vertex set of the ith graph of the Johnson Scheme Gi(n,k) is the set of all k subsets of a fixed set of n elements. Two vertices A and B are i-related and are adjacent if and only if [A ^ B] = k-i. The combined ith graphs of the Johnson Scheme SGi(n) is the graph formed by the union of all the graphs Gi(n,k) where 0 <_ k <_ n. The Hamming Scheme (n,q) is an association scheme whose vertex set Q to the n, the set of all words of length n over the alphabet Q of q symbols. Two words are r-related if they differ in exactly r coordinate positions. The graph of the Hamming Scheme H (n,q,r) is the graph whose vertex set is the same as that of H(n,q) and two vertices are adjacent if and only if they are r-related. The generalized n-cube Q(n,m) is the graph whose vertices are all the binary n-tuples , such that two vertices are adjacent whenever they differ in exactly m coordinates. This makes the generalized n-cube Q(n,m) isomorphic to the graph of the Hamming Scheme H(n,2,m). This paper shows the existence of isomorphisms of the Hamming and the Johnson Graphs with some other graphs, along with some of their combinatorial and graph properties. Finally we will show that there is an embedding of the graph SGi(n), or the combined ith graphs of the Johnson Scheme, into the graph of the Hamming Scheme H(n,q,r) when q=2 and when the hamming distance r is twice the Johnson distance i, by showing SGi(n) is a spanning subgraph of the generalized n-cube Q(n,2i).
Thesis (M.S. Computer Science)--University of the Philippines Diliman.
Keywords: Isomorphisms (Mathematics).; Hamming Schemes; Johnson Schemes