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

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

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

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

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

Примітки

1. Holton, D. A.; Sheehan, J. (1993). The Johnson graphs and even graphs. The Petersen graph. Australian Mathematical Society Lecture Series 7. Cambridge: Cambridge University Press. с. 300. ISBN 0-521-43594-3. MR 1232658. doi:10.1017/CBO9780511662058..