×

On the \(i\)th graphs of the Johnson scheme. (English) Zbl 1341.05055

Lagakos, Stephen (ed.) et al., Recent advances in applied mathematics. Proceedings of the American conference on applied mathematics (AMERICAN-MATH ’10), Harvard University, Cambridge, MA, USA, January 27–29, 2010. Athens: WSEAS Press (ISBN 978-960-474-150-2). Mathematics and Computers in Science and Engineering, 396-400 (2009).
Summary: 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\cap B|=k-1\). The order of \(G_i(n,k)\) is \(^nC_k\) and that each vertex is \(k(n-k)\) regular.
The \(i\)th Johnson Graph \(G_i(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\cap B|=k-i\). Two vertices \(A\) and \(B\) are \(i\)-related if \(|A\cap B|=k-i\), and \(i\) is referred to as the Johnson distance. This scheme has \(k\) classes. The graph \(G_i(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: \[ \begin{aligned} \sum^n_{k=0} \deg(G(n,k)) & =|V(G(n+1,3))|\\ \sum^{n-i}_{k=i}\deg(G_i(n,k))& = |V(G_i(n+1,2i+1))|\\ \sum^k_{i=1}\deg(G_i(n,k))& ={n\choose k}-1. \end{aligned} \]
For the entire collection see [Zbl 1205.00088].

MSC:

05C12 Distance in graphs
05C07 Vertex degrees
05E30 Association schemes, strongly regular graphs
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite