On the ith graphs of the Johnson scheme
Geoffrey A. Solano, Jaime D. L. Caro · 2010
Abstract: Let n and k be fixed positive integers. The Johnson Graph G(n,k),also known as the slice of the cube, or the graph of the Johnson Scheme of the first order is the undirected graph where the vertices are all the k-subsets of a fixed n-set. Two vertices A and B are adjacent if and only if |A∩B | = k-1 [5]. The order of Gi(n,k) is nCk and that each vertex is k(n-k) regular. The ith Johnson Graph Gi(n,k) is the undirected graph where the vertices are also all the k-subsets of a fixed n-set. Here two vertices A and B are adjacent if and only if |A∩B | = k-i. Two vertices A and B are i-related if |A∩B | = k-i, and i is referred to as the johnson distance. This scheme has k classes. [5] The graph Gi(n,k) of the Johnson Scheme has shown very promising properties as a static interconnection network topology. This paper shows some properties of the said graph, among them the following degree properties: