В теории графов граф -колесо — это граф , образованный путем соединения одной универсальной вершины со всеми вершинами цикла . Граф-колесо с n вершинами также может быть определен как 1- скелет ( n – 1 )-угольной пирамиды .
Некоторые авторы [1] пишут W n для обозначения графа-колеса с n вершинами ( n ≥ 4 ); другие авторы [2] вместо этого используют W n для обозначения графа-колеса с n + 1 вершинами ( n ≥ 3 ), который образуется путем соединения одной вершины со всеми вершинами цикла длины n . Прежняя нотация используется в остальной части этой статьи и в таблице справа.
{{1, 2}, {1, 3}, …, {1, v}, {2, 3}, {3, 4}, …, {v − 1, v}, {v, 2}} [3] будет множеством ребер графа-колеса с множеством вершин {1, 2, …, v}, в котором вершина 1 является универсальной вершиной .
Колесные графы являются планарными графами и имеют уникальное планарное вложение. Более конкретно, каждый колесный граф является графом Халина . Они самодвойственны: планарный двойственный граф любого колесного графа является изоморфным графом . Каждый максимальный планарный граф, отличный от K 4 = W 4 , содержит в качестве подграфа либо W 5 , либо W 6 .
В графе колеса всегда имеется гамильтонов цикл , и имеются циклы в W n (последовательность A002061 в OEIS ).
Для нечетных значений n W n является совершенным графом с хроматическим числом 3: вершинам цикла можно задать два цвета, а центральной вершине — третий цвет. Для четных n W n имеет хроматическое число 4 и (когда n ≥ 6) не является совершенным. W 7 является единственным графом-колесом, который является графом единичных расстояний в евклидовой плоскости. [ 4]
Хроматический многочлен графа колеса W n равен:
В теории матроидов два особенно важных специальных класса матроидов — это матроиды колес и матроиды вихрей , оба выведенные из графов колес. Матроид k -колеса является графическим матроидом колеса W k+1 , в то время как матроид k -вихря выводится из k -колеса путем рассмотрения внешнего цикла колеса, а также всех его остовных деревьев как независимых.
Колесо W 6 предоставило контрпример к гипотезе Пола Эрдёша о теории Рамсея : он предположил, что полный граф имеет наименьшее число Рамсея среди всех графов с тем же хроматическим числом, но Фодри и Маккей (1993) показали, что W 6 имеет число Рамсея 17, в то время как полный граф с тем же хроматическим числом, K 4 , имеет число Рамсея 18. [5] То есть для каждого 17-вершинного графа G , либо G , либо его дополнение содержат W 6 в качестве подграфа, в то время как ни 17-вершинный граф Пейли , ни его дополнение не содержат копии K 4 .
