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

граф Джонсона
граф Джонсона
	граф Джонсона
Названо на честь	Селмер Джонсон[en]
Вершин
Ребер
Діаметр
Властивості	-регулярний; вершинно-транзитивний; дистанційно-транзитивний
Позначення

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

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

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

Примітки

↑ ^а ^б 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 0-521-43594-3, MR 1232658.

[hs93-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 0-521-43594-3, MR 1232658.

[1]

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