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

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

В математической области теории графов граф ветряной мельницы $Wd(k, n)$ представляет собой неориентированный граф, построенный для $k \geq 2$ и $n \geq 2$ путем соединения $n$ копий полного графа $K k$ в общей универсальной вершине . То есть это 1-кликовая сумма этих полных графов. ^[1]

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

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

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

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

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

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

x\prod _{i=1}^{k-1}(x-i)^{n}.

Граф ветряной мельницы $Wd(k, n)$ не является изящным , если $k > 5$ . ^[3] В 1979 году Бермонд предположил, что $Wd(4, n)$ изящна для всех $n \geq 4$ . ^[4] С помощью эквивалентности с совершенно разностными семействами это было доказано для $n \leq 1000$ . ^[5]Бермонд, Коциг и Терджен доказали, что $Wd(k, n)$ не является изящным, когда $k = 4$ и $n = 2$ или $n = 3$ , а также когда $k = 5$ и $n = 2$ . ^[6] Ветряная мельница $Wd(3, n)$ изящна тогда и только тогда, когда $n \equiv 0 (mod 4)$ или $n \equiv 1 (mod 4)$ . ^[7]

Галерея

Ссылки

^ Галлиан, Дж. А. (3 января 2007 г.). «Динамический обзор разметки графов» (PDF) . Электронный журнал комбинаторики . ДС6 : 1–58. МР 1668059 .
^ Вайсштейн, Эрик В. «График ветряной мельницы» . Математический мир .
^ Кох, КМ; Роджерс, генеральный директор; Тео, Гонконг; Яп, Кентукки (1980). «Изящные графики: некоторые дальнейшие результаты и проблемы». Конгресс Нумерантиум . 29 : 559–571. МР 0608456 .
^ Бермонд, Ж.-К. (1979). «Изящные графики, радиоантенны и французские ветряные мельницы» . В Уилсоне, Робин Дж. (ред.). Теория графов и комбинаторика (Proc. Conf., Open Univ., Милтон Кейнс, 1978) . Конспекты исследований по математике. Том. 34. Питман. стр. 18–37. ISBN 978-0273084358 . МР 0587620 . OCLC 757210583 .
^ Ге, Г.; Мяо, Ю.; Сан, X. (2010). «Семейства совершенных разностей, матрицы совершенных разностей и связанные с ними комбинаторные структуры». Журнал комбинаторных проектов . 18 (6): 415–449. дои : 10.1002/jcd.20259 . МР 2743134 . S2CID 120800012 .
^ Бермонд, Ж.-К.; Коциг, А .; Терджен, Дж. (1978). «Об одной комбинаторной задаче антенн в радиоастрономии» . В Хайнале, А.; Сос, Вера Т. (ред.). Комбинаторика (Труды Пятого венгерского коллоквиума, Кестхей, 1976), Том I. Colloquia Mathematica Societatis Янош Бойай. Том 18. Северная Голландия. стр. 135–149. ISBN 978-0-444-85095-9 . МР 0519261 .
^ Бермонд, Ж.-К.; Брауэр, AE ; Джерма, А. (1978). «Триплетные системы и связанные с ними различия» . Комбинаторные задачи и теория графов (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) . Международные конференции Национального центра научных исследований. Полет. 260. Издания Национального центра научных исследований. стр. 35–38. ISBN 978-2-222-02070-7 . МР 0539936 .

[1] Галлиан, Дж. А. (3 января 2007 г.). «Динамический обзор разметки графов» (PDF) . Электронный журнал комбинаторики . ДС6 : 1–58. МР 1668059 .

[2] Вайсштейн, Эрик В. «График ветряной мельницы» . Математический мир .

[3] Кох, КМ; Роджерс, генеральный директор; Тео, Гонконг; Яп, Кентукки (1980). «Изящные графики: некоторые дальнейшие результаты и проблемы». Конгресс Нумерантиум . 29 : 559–571. МР 0608456 .

[4] Бермонд, Ж.-К. (1979). «Изящные графики, радиоантенны и французские ветряные мельницы» . В Уилсоне, Робин Дж. (ред.). Теория графов и комбинаторика (Proc. Conf., Open Univ., Милтон Кейнс, 1978) . Конспекты исследований по математике. Том. 34. Питман. стр. 18–37. ISBN 978-0273084358 . МР 0587620 . OCLC 757210583 .

[5] Ге, Г.; Мяо, Ю.; Сан, X. (2010). «Семейства совершенных разностей, матрицы совершенных разностей и связанные с ними комбинаторные структуры». Журнал комбинаторных проектов . 18 (6): 415–449. дои : 10.1002/jcd.20259 . МР 2743134 . S2CID 120800012 .

[6] Бермонд, Ж.-К.; Коциг, А .; Терджен, Дж. (1978). «Об одной комбинаторной задаче антенн в радиоастрономии» . В Хайнале, А.; Сос, Вера Т. (ред.). Комбинаторика (Труды Пятого венгерского коллоквиума, Кестхей, 1976), Том I. Colloquia Mathematica Societatis Янош Бойай. Том 18. Северная Голландия. стр. 135–149. ISBN 978-0-444-85095-9 . МР 0519261 .

[7] Бермонд, Ж.-К.; Брауэр, AE ; Джерма, А. (1978). «Триплетные системы и связанные с ними различия» . Комбинаторные задачи и теория графов (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) . Международные конференции Национального центра научных исследований. Полет. 260. Издания Национального центра научных исследований. стр. 35–38. ISBN 978-2-222-02070-7 . МР 0539936 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]