Кнезер граф

В теории графов граф Кнезера $K (n, k)$ (альтернативно $KGn, k$ ) — это граф, вершины которого соответствуют $k -$ $элементным$ подмножествам множества из $n$ элементов , и где две вершины смежны тогда и только тогда, когда два соответствующих множества не пересекаются . Графы Кнезера названы в честь Мартина Кнезера , который впервые исследовал их в 1956 году.

Граф Кнезера $K (2 n - 1, n - 1)$ является нечетным графом $O n$ ; в частности , $O 3 = K (5, 2)$ является графом Петерсена (см. верхний правый рисунок).

Как предположил Кнезер ( 1956 ), хроматическое число графа Кнезера $K (n, k)$ для точно равно $n$ $-$ $2k$ $+ 2$ ; например, граф Петерсена требует трех цветов в любой правильной раскраске. Эта гипотеза была доказана несколькими способами. ${\ Displaystyle п \ geq 2k}$

Граф Джонсона $J (n, k)$ — это граф, вершины которого являются $k$ - элементными подмножествами $n$ - элементного множества, причем две вершины считаются смежными, когда они встречаются в $(k - 1)$ -элементном множестве. Граф Джонсона $J (n, 2)$ является дополнением графа Кнезера $K (n, 2)$ . Графы Джонсона тесно связаны со схемой Джонсона , обе названы в честь Селмера М. Джонсона .

Обобщенный граф Кнезера $K (n, k, s)$ имеет тот же набор вершин, что и граф Кнезера $K (n, k)$ , но соединяет две вершины всякий раз, когда они соответствуют множествам, которые пересекаются в $s$ или меньшем количестве элементов ( Denley 1997 ). Таким образом , $K (n, k, 0) = K (n, k)$ .

Двудольный граф Кнезера $H (n, k)$ имеет в качестве вершин множества из $k$ и $n - k$ элементов, взятых из набора из $n$ элементов. Две вершины соединены ребром, если одно множество является подмножеством другого. Подобно графу Кнезера, он транзитивен по вершинам со степенью . Двудольный граф Кнезера может быть сформирован как двудольное двойное покрытие $K$ $($ $n$ $,$ $k$ $)$ , в котором делается две копии каждой вершины и заменяется каждое ребро парой ребер, соединяющих соответствующие пары. вершин ( Симпсон 1991 ${\ displaystyle {\ tbinom {nk} {k}}.}$ ). Двудольный граф Кнезера $H (5, 2)$ является графом Дезарга, а двудольный граф Кнезера $H (n, 1)$ является коронным графом .

Граф Кнезера

O 4 = K (7, 3)