Оглавление
График Кнезера
-
Определение и свойства графа Кнезера
- Граф Кнезера K(n, k) соединяет вершины, соответствующие непересекающимся k-элементным множествам из n элементов.
- Назван в честь Мартина Кнезера, исследовавшего его в 1956 году.
-
Примеры графов Кнезера
- K(n, 1) является полным графом с n вершинами.
- K(n, 2) – дополнение линейного графа к полному графу с n вершинами.
- K(2n – 1, n – 1) – нечетный граф, в частности, O3 = K(5, 2) – граф Петерсена.
- K(7, 3) – график Кнезера O4.
-
Основные свойства
- Граф Кнезера имеет (n k) вершин и ровно (n – k k) соседей для каждой вершины.
- Является вершинно-транзитивным и дугово-транзитивным.
- При k = 2 является строго регулярным с определенными параметрами.
- При k > 2 имеет разное количество общих соседей для разных пар несмежных вершин.
- Связность графа Кнезера равна его степени, за исключением K(2k, k), который отключен.
-
Хроматическое число и гамильтоновы циклы
- Гипотеза Кнезера о хроматическом числе утверждает, что оно равно n – 2k + 2 для n ≥ 2k.
- Доказано несколькими способами, включая топологические и комбинаторные методы.
- Гамильтоновы циклы в графе Кнезера существуют при определенных условиях на n и k.
-
Группировки и диаметр
- При n < 3k граф Кнезера не содержит треугольников.
- При n < ck не содержит клик размера c, но содержит их при n ≥ ck.
- Диаметр графа Кнезера равен 2k + 1 при n ≥ 2k.
-
Спектр и номер независимости
- Спектр графа Кнезера состоит из k + 1 собственных значений.
- Число независимости графа Кнезера равно (n – k k).
-
Связанные графы
- Граф Джонсона J(n, k) подобен графу Кнезера, но смежные вершины соответствуют множествам из (k – 1) элементов.
- Двудольный граф Кнезера H(n, k) соединяет множества из k и n – k элементов.
- Обобщенный граф Кнезера K(n, k, s) соединяет множества, пересекающиеся в s или меньше элементов.
-
Рекомендации
- Ссылки на цитируемые работы и внешние ссылки для дополнительной информации.
Полный текст статьи: