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

В математической области теории графов граф ветряной мельницы $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)$ является графом звезды $S n$ , а граф-мельница $Wd(3,2)$ является графом бабочки .

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

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

x\prod _{i=1}^{k-1}(xi)^{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]

Галерея

Ссылки

^ Gallian, JA (3 января 2007 г.). "Динамический обзор маркировки графов" (PDF) . Электронный журнал комбинаторики . DS6 : 1–58. MR 1668059.
^ Вайсштейн, Эрик В. «График ветряной мельницы». Математический мир .
^ Кох, К. М.; Роджерс, Д. Г.; Тео, Х. К.; Яп, К. Й. (1980). «Изящные графики: некоторые дальнейшие результаты и проблемы». Congressus Numerantium . 29 : 559–571. MR 0608456.
^ Bermond, J.-C. (1979). "Изящные графы, радиоантенны и французские ветряные мельницы". В Wilson, Robin J. (ред.). Теория графов и комбинаторика (Proc. Conf., Open Univ., Milton Keynes, 1978) . Исследовательские заметки по математике. Том 34. Pitman. С. 18–37. ISBN 978-0273084358. MR 0587620. OCLC 757210583.
^ Ge, G.; Miao, Y.; Sun, X. (2010). «Семейства совершенных разностей, матрицы совершенных разностей и связанные с ними комбинаторные структуры». Журнал комбинаторных конструкций . 18 (6): 415–449. doi :10.1002/jcd.20259. MR 2743134. S2CID 120800012.
^ Бермонд, Ж.-К.; Коциг, А .; Терджен, Дж. (1978). «Об одной комбинаторной задаче антенн в радиоастрономии». В Хайнале, А.; Сос, Вера Т. (ред.). Комбинаторика (Труды Пятого венгерского коллоквиума, Кестхей, 1976), Vol. Я. Colloquia Mathematica Societatis Янош Бойяи. Том. 18. Северная Голландия. стр. 135–149. ISBN 978-0-444-85095-9. МР 0519261.
^ Бермонд, Ж.-К.; Брауэр, AE ; Джерма, А. (1978). «Системы тройных и ассоциированных различий». Комбинированные проблемы и теория графов (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) . Международные коллоквиумы Национального центра научных исследований. Том. 260. Éditions du Centre national de la recherche scientifique. стр. 35–38. ISBN 978-2-222-02070-7. МР 0539936.