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

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

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

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

$J (n, 1)$ — повний граф $K_{n}$ .
$J (4, 2)$ — октаедральний граф.
$J (5, 2)$ — граф, обернений до графу Петерсена^[1], тобто реберний граф до графу $K_{5}$ . Більш загально, для кожного $n$ граф Джонсона $J (n, 2)$ — це граф, обернений до графу Кнезера $K G (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)$
Названо на честь	Селмер Джонсон
Вершин	$(\binom{n}{k})$
Ребер	$\frac{k (n - k)}{2} (\binom{n}{k})$
Діаметр	$min (k, n - k)$
Властивості	$(k (n - k))$ -регулярний вершинно-транзитивний дистанційно-транзитивний
Позначення	$J (n, k)$