График колеса

График колеса
Несколько примеров колесных графиков
Вершины	п
Края	2 ( п - 1)
Диаметр	2, если n > 4 1, если n = 4
Обхват	3
Хроматическое число	4, если n четно 3, если n нечетно
Спектр	${\ Displaystyle \ {2 \ соз (2к \ пи / (п-1)) ^ {1};}$ ${\ Displaystyle к = 1, \ ldots, п-2 \}}$${\ displaystyle \ cup \ {1 \ pm {\ sqrt {n}} \}}$
Характеристики	Гамильтониан самодвойственный планарный
Обозначение	W n
Таблица графиков и параметров

В математической дисциплине теории графов , колесо граф является графом , образованного путем соединения одного универсальной вершины всех вершин цикла . Колесный граф с n вершинами также можно определить как 1- скелет ( n -1) -угольной пирамиды . Некоторые авторы ^[1] пишут W _n для обозначения графа-колеса с n вершинами (n ≥ 4); другие авторы ^[2] вместо этого используют W _n для обозначения графа колеса с n+1 вершина (n ≥ 3), которая образована соединением одной вершины со всеми вершинами цикла длины n . В остальной части статьи мы используем прежние обозначения.

Конструирование наборов [ править ]

Для данного набора вершин {1, 2, 3,…, v} набор ребер графа колеса может быть представлен в нотации конструктора множеств как {{1, 2}, {1, 3},…, {1 , v}, {2, 3}, {3, 4},…, {v - 1, v}, {v, 2}}. ^[3]

Свойства [ править ]

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

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

7 циклов колесного графика W ₄ .

Для нечетных значений п , Ш _п является идеальным графиком с хроматическим числом 3: вершины цикла может быть даны два цвета, а центр вершин даных третий цвета. Для четного n , W _n имеет хроматическое число 4 и (при n ≥ 6) не является совершенным. W ₇ - единственный граф колес, который является графом единичных расстояний в евклидовой плоскости. ^[4]

Хроматической многочлен колесного графа W _п является:

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

В теории матроидов два особенно важных специальных класса матроидов - это колесные матроиды и вихревые матроиды , оба производные от колесных графов. К -wheel матроидом является графическим матроидом колеса W _{к + 1} , в то время как к -whirl матроидом является производным от K -wheel, рассматривая внешний цикл колеса, а также все его остовных деревьев , чтобы быть независимый.

Колесо W ₆ предоставило контрпример к гипотезе Пола Эрдеша о теории Рамсея : он предположил, что полный граф имеет наименьшее число Рамсея среди всех графов с тем же хроматическим числом, но Фодри и Маккей (1993) показали, что W ₆ имеет Рамси. номер 17, в то время как полный граф с тем же хроматическим числом K ₄ имеет число Рамсея 18. ^[5] То есть для каждого 17-вершинного графа G либо G, либо его дополнение содержат W ₆ в качестве подграфа, в то время как ни один из 17 -вершинный граф Пэли и его дополнение не содержат копииК ₄ .

Ссылки [ править ]