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

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

граф Джонсона
граф Джонсона ${\displaystyle J(5,2)}$
Названо на честь	^[en]
(Вершин)	${\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)}$ — граф, обернений до графу Петерсена, тобто реберний граф до графу ${\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, doi:10.1017/CBO9780511662058, ISBN , MR 1232658.