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

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

Граф Джонсона $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)$ — це граф, обернений до графу Кнезера $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. ISBN 0-521-43594-3. MR 1232658. doi:10.1017/CBO9780511662058..

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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. ISBN 0-521-43594-3. MR 1232658. doi:10.1017/CBO9780511662058..