В теории графов колесом W _n называется граф с n вершинами (n ≥ 4), образованный соединением единственной вершины со всеми вершинами ( n -1)- цикла . Числовое обозначение колёс в литературе не устоялось — некоторые авторы используют n для обозначения длины цикла, так что их W _n означает граф W _n+1 по определению выше . Колесо может быть определено также, как (англ.) ( ( n -1)-угольной пирамиды .

Представление в виде множества

Пусть задано множество вершин {1,2,3,…,v}. Множество рёбер графа-колеса можно представить в виде множества {{1,2},{1,3},…,{1,v},{2,3},{3,4},…,{v-1,v},{v,2}} .

Свойства

Колеса являются планарными графами , а потому имеют единственное вложение в плоскость. Любое колесо является графом Халина . Они самодвойственны — двойственный граф любого колеса изоморфен самому колесу. Любой максимальный планарный граф, отличный от K ₄ = W ₄ , содержит в качестве подграфа либо W ₅ , либо W ₆ .

В колесе всегда имеется гамильтонов цикл и число циклов в W _n равно ${\displaystyle n^{2}-3n+3}$ (последовательность в OEIS ).

7 циклов в колесе W 4 .

Для нечётных значений n W _n является совершенным графом с хроматическим числом 3 — вершины цикла можно выкрасить в два цвета, а центральная вершина будет иметь третий цвет. Для чётного n W _n колесо имеет хроматическое число 4 и (при n ≥ 6) не будет совершенным графом. W ₇ — это единственное колесо, являющееся графом единичных расстояний на евклидовой плоскости .

Хроматический многочлен колеса W _n равен:

${\displaystyle P_{W_{n}}(x)=x((x-2)^{(n-1)}-(-1)^{n}(x-2)).}$

В теории матроидов есть два особо важных вида матроидов — колеса и вихри , и оба вида являются производными от графов-колес. Матроид k -колёса — это (англ.) ( колеса W _k+1 , а матроид k -вихря получается из матроида k -колеса путём объявления внешнего цикла (обода) таким же независимым множеством, как и его остовные деревья .

Колесо W ₆ даёт контрпример гипотезе Пола Эрдёша в теории Рамсея — он высказал предположение, что полный граф имеет наименьшее число Рамсея среди всех графов с тем же хроматическим числом. Однако Фаудри и МакКей (Faudree, McKay, 1993) показали, что для W ₆ число Рамсея равно 17, в то время как для полного графа K ₄ , с тем же хроматическим числом, число Рамсея равно 18 . Таким образом, для любого графа G с 17 вершинами либо сам G , либо его дополнение содержит W ₆ как подграф, в то время как ни граф Пэли , имеющий 17 вершин, ни его дополнение не содержат K ₄ .

Примечания