Граф Джонсона

Граф Джонсона $J(n,k)$ — це неорієнтований граф, вершинами якого є $k$-елементні підмножини множини з $n$ елементів; дві вершини суміжні, коли вони мають спільну $(k-1)$-елементну множину. Граф Джонсона та споріднена з ним Шаблон:Iw2 названо за ім'ям Шаблон:Iw2 (1916—1996).

Спеціальні випадки

• $J(n,1)$ — повний граф $K_n$.
• $J(4,2)$ — октаедральний граф.
• $J(5,2)$ — граф, обернений до графу Петерсена, тобто реберний граф до графу $K_5$. Більш загально, для кожного $n$ граф Джонсона $J(n,2)$ — це граф, обернений до графу Кнезера $KG(n,2)$