График ветряной мельницы - Windmill graph

График ветряной мельницы
График ветряка Wd (5,4) .svg
Граф Windmill Wd (5,4).
Вершины(к-1) п + 1
Краяnk (k − 1) / 2
Радиус1
Диаметр2
Обхват3 если k> 2
Хроматическое числоk
Хроматический индексп (к-1)
ОбозначениеWd (k,п)
Таблица графиков и параметров

в математический поле теория графов, то график ветряка Wd (k,п) является неориентированный граф построен для k ≥ 2 и п ≥ 2 путем присоединения п копии полный график Kk на общем универсальная вершина. То есть это 1-кликовая сумма этих полных графиков.[1]

Характеристики

Она имеет (к-1) п + 1 вершины и nk (k − 1) / 2 края,[2] обхват 3 (если k> 2), радиусом 1 и диаметром 2. связность вершин 1, потому что его центральная вершина является точкой сочленения; однако, как и полные графы, из которых он сформирован, он (к-1)-кромочные. это тривиально идеальный и блочный граф.

Особые случаи

По построению граф ветряной мельницы Wd (3,п) это граф дружбы Fп, граф ветряка Wd (2,п) это звездный график Sп а граф ветряка Wd (3,2) - это график бабочки.

Маркировка и окраска

График ветряка имеет хроматическое число k и хроматический индекс п (к-1). Его хроматический полином может быть выведен из хроматического полинома полного графа и равен

График ветряка Wd (k,п) доказано не изящный если k > 5.[3] В 1979 г. Бермонд предположил, что Wd (4,п) изящен для всех п ≥ 4.[4] Через эквивалентность с семействами совершенных разностей это доказано для п ≤ 1000.[5]Бермон, Котциг, и Тюрджен доказал, что Wd (k,п) не изящно, когда k = 4 и п = 2 или п = 3, а когда k = 5 и м = 2.[6] Мельница Wd (3,п) изящно тогда и только тогда, когда п ≡ 0 (мод 4) или п ≡ 1 (мод.4).[7]

Галерея

Графики малых ветряков.

Рекомендации

  1. ^ Галлиан, Дж. А. (3 января 2007 г.). «Динамическое обследование DS6: разметка графиков» (PDF). Электронный журнал комбинаторики. DS6: 1–58.
  2. ^ Вайсштейн, Эрик В. "График ветряных мельниц". MathWorld.
  3. ^ Koh, K. M .; Роджерс, Д.Г .; Teo, H.K .; Яп, К. Я. (1980). «Изящные графики: некоторые дальнейшие результаты и проблемы». Congr. Нумер. 29: 559–571.
  4. ^ Бермонд, Дж. К. (1979). «Изящные графики, радиоантенны и французские ветряки». В Уилсоне, Робин Дж. (Ред.). Теория графов и комбинаторика. Примечания к исследованиям по математике. 34. Питман. С. 18–37. ISBN  978-0273084358. OCLC  757210583.
  5. ^ Ge, G .; Miao, Y .; Солнце, X. (2010). «Семейства совершенных разностей, матрицы совершенных разностей и родственные комбинаторные структуры». Журнал комбинаторных дизайнов. 18 (6): 415–449. Дои:10.1002 / jcd.20259.
  6. ^ Bermond, J.C .; Коциг, А.; Turgeon, J. (1978). «К комбинаторной задаче антенн в радиоастрономии». In Hajnal, A .; Сос, Вера Т. (ред.). Комбинаторика. Colloquia mathematica Societatis János Bolyai. 18. Северная Голландия. С. 135–149. ISBN  978-0-444-85095-9.
  7. ^ Bermond, J.C .; Brouwer, A.E .; Джерма, А. (1978). "Systèmes de triplets et différences associées". Problèmes combinatoires et théorie des graphes: Орсе, 9-13 июля 1976 г.. Международные коллоквиумы национального центра научных исследований. 260. Éditions du Centre national de la recherche scientifique. С. 35–38. ISBN  978-2-222-02070-7.