Johnson Graph

The Johnson graph $ J(n, k) $ is the graph where the vertices are labelled by the $ k $ element subsets of a set of size $ n $ and the edges join those subsets where the intersection is of size $ k - 1 $.

Why $ J(n, k) $: Johnson graph with parameters $ n $ and $ k $.

$ \mathbb{Z}_n = \{ 0, 1, 2, \ldots, n \} $.

Vertices: $ V = \{ K \mid K \subseteq \mathbb{Z}_n, |K| = k-1 \} $.

Edges: $ E = \{ (K_i, K_j) \mid |K_i \cup K_j| = k - 1 \} $.

Example

$ J(4, 2) $: Johnson graph with parameters $ n=4 $ and $ k=2 $.

$ \begin{aligned} V = \big\{ & \{ 1,2 \} , \{ 1,3 \} , \{ 1,4 \} , \\ & \{ 2,3 \} , \{ 2,4 \} , \{ 3,4 \} \big\} \end{aligned} $

$ \begin{aligned} E = \big\{ & (\{1,2\},\{1,3\}), (\{1,2\},\{1,4\}), \\ & (\{1,2\},\{2,3\}), (\{1,2\},\{2,4\}), \\ & (\{1,3\},\{1,4\}), (\{1,3\},\{2,3\}), \\ & (\{1,3\},\{3,4\}), (\{1,4\},\{2,4\}), \\ & (\{1,4\},\{3,4\}), (\{2,3\},\{2,4\}), \\ & (\{2,3\},\{3,4\}), (\{2,4\},\{3,4\}) \big\} \end{aligned} $