График колеса - Wheel graph

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

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

Конструкция-конструктор

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

Свойства

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

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

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

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

В хроматический полином колеса графа W_п является :

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

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

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

использованная литература

1. Вайсштейн, Эрик В. «Колесный график». MathWorld.
2. Розен, Кеннет Х. (2011). Дискретная математика и ее приложения (7-е изд.). Макгроу-Хилл. п.655. ISBN  978-0073383095.
3. Трюдо, Ричард Дж. (1993). Введение в теорию графов (Исправленное, расширенное переиздание. Ред.). Нью-Йорк: Dover Pub. п. 56. ISBN  978-0-486-67870-2. Получено 8 августа 2012.
4. Бакли, Фред; Харари, Фрэнк (1988), «Об евклидовом измерении колеса», Графики и комбинаторика, 4 (1): 23–30, Дои:10.1007 / BF01864150.
5. Фодри, Ральф Дж.; Маккей, Брендан Д. (1993), "Гипотеза Эрдеша и числа Рамсея р(W₆)", J. Комбинаторная математика. и комбинаторные вычисления., 13: 23–31.