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

граф Джонсона
граф Джонсона $J(5,2)$
Названо на честь	Селмер Джонсон
Вершин	${\binom {n}{k}}$
Ребер	${\frac {k(n-k)}{2}}{\binom {n}{k}}$
Діаметр	$\min(k,n-k)$
Властивості	$(k(n-k))$-регулярний вершинно-транзитивний дистанційно-транзитивний
Позначення	$J(n,k)$

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

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

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