Мельница (теория графов)
В теории графов «мельница» Wd(k,n) — это неориентированный граф, построенный для k ≥ 2 и n ≥ 2 путём объединения n копий полных графов Kk в одной общей вершине. То есть это сумма по 1-клике этих полных графовШаблон:Sfn.
Свойства
Граф имеет (k-1)n+1 вершин и nk(k−1)/2 рёбер [1], обхват 3 (при k > 2), радиус 1 и диаметр 2. Граф имеет вершинную связность 1, поскольку его центральная вершина является точкой сочленения. Однако, подобно полным графам, из которых он образован, он является рёберно (k-1)-связным. Граф является тривиально совершенным графом и блоковым графом.
Специальные случаи
По построению мельница Wd(3,n) является графом дружеских отношений Fn, мельница Wd(2,n) является звездой Sn, а мельница Wd(3,2) является «бабочкой».
Разметка и раскраска
Граф «мельница» имеет хроматическое число k и хроматический индекс n(k-1). Его хроматический многочлен может быть получен из хроматического полинома полного графа и равен
Доказано, что граф «мельница» Wd(k,n) не является грациозным, если k > 5Шаблон:Sfn. В 1979 Бермонд высказал гипотезу, что Wd(4,n) является грациозным для всех n ≥ 4Шаблон:Sfn. Известно, что это верно для n ≤ 22Шаблон:Sfn. Бермонд, Котциг и Тургеон доказали, что Wd(k,n) не является грациозными при k = 4 и n = 2 или n = 3, и при k = 5 и n = 2Шаблон:Sfn. Мельница Wd(3,n) грациозна тогда и только тогда, когда n ≡ 0 (mod 4) или n ≡ 1 (mod 4)Шаблон:Sfn.
Галерея
