Граф Кнезера - Kneser graph

Граф Кнезера
Граф Кнезера KG (5,2) .svg
Граф Кнезера K(5, 2),
изоморфен Граф Петерсена
Названный в честьМартин Кнезер
Вершины
Края
Хроматическое число
Характеристики-обычный
дуговой переходный
ОбозначениеK(п, k), КГп,k.
Таблица графиков и параметров

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

Примеры

Граф Кнезера K(п, 1) это полный график на п вершины.

Граф Кнезера K(п, 2) это дополнять из линейный график полного графика на п вершины.

Граф Кнезера K(2п − 1, п − 1) это нечетный график Оп; особенно О3 = K(5, 2) это Граф Петерсена.

Характеристики

  • Граф Кнезера K(п, k) имеет вершины. В каждой вершине ровно соседи.
С
относится ко всем k это условие выполняется, если
  • Граф Кнезера K(п, k) содержит гамильтонов цикл, если существует неотрицательное целое число а такой, что (Мютце, Нумменпало и Вальчак 2018 ). В частности, нечетный график Оп имеет гамильтонов цикл, если п ≥ 4.
  • За исключением графа Петерсена, все связные графы Кнезера K(п, k) с п ≤ 27 гамильтоновы (Щиты 2004 ).
  • Когда п < 3k, граф Кнезера K(п, k) не содержит треугольников. В более общем плане, когда п < ск он не содержит клики размера c, а такие клики есть, когда пск. Более того, хотя граф Кнезера всегда содержит циклы длины четыре, когда п ≥ 2k + 2, для значений п рядом с 2k кратчайший нечетный цикл может иметь непостоянную длину (Денли 1997 ).
более того происходит с множественность за и имеет кратность 1. См. это бумага для доказательства.

Связанные графики

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

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

В двудольный граф Кнезера ЧАС(п, k) имеет в качестве вершин множества k и пk предметы, взятые из коллекции п элементы. Две вершины соединяются ребром, если одно множество является подмножеством другого. Как и граф Кнезера, он вершинно транзитивен со степенью Двудольный граф Кнезера может быть сформирован как двусторонняя двойная обложка из K(п, k) в котором делается две копии каждой вершины и каждое ребро заменяется парой ребер, соединяющих соответствующие пары вершин (Симпсон 1991 ). Двудольный граф Кнезера ЧАС(5, 2) это График дезарга и двудольный граф Кнезера ЧАС(п, 1) это граф короны.

Рекомендации

внешняя ссылка