Меню Главная Случайная статья Настройки Мельница (теория графов) Материал из https://ru.wikipedia.org В теории графов «мельница» Wd(k,n) — это неориентированный граф, построенный для k 2 и n 2 путём объединения n копий полных графов Kk в одной общей вершине. То есть это сумма по 1-клике этих полных графов[1]. Содержание 1 Свойства 2 Специальные случаи 3 Разметка и раскраска 4 Галерея 5 Примечания 6 Литература Свойства Граф имеет (k-1)n+1 вершин и nk(k1)/2 рёбер [2], обхват 3 (при k > 2), радиус 1 и диаметр 2. Граф имеет вершинную связность 1, поскольку его центральная вершина является точкой сочленения. Однако, подобно полным графам, из которых он образован, он является рёберно (k-1)-связным. Граф является тривиально совершенным графом и блоковым графом. Специальные случаи По построению мельница Wd(3,n) является графом дружеских отношений Fn, мельница Wd(2,n) является звездой Sn, а мельница Wd(3,2) является «бабочкой». Разметка и раскраска Граф «мельница» имеет хроматическое число k и хроматический индекс n(k-1). Его хроматический многочлен может быть получен из хроматического полинома полного графа и равен ${\displaystyle \prod _{i=0}^{k-1}(x-i)^{n}.}$ Доказано, что граф «мельница» Wd(k,n) не является грациозным, если k > 5[3]. В 1979 Бермонд высказал гипотезу, что Wd(4,n) является грациозным для всех n 4[4]. Известно, что это верно для n 22[5]. Бермонд, Котциг и Тургеон доказали, что Wd(k,n) не является грациозными при k = 4 и n = 2 или n = 3, и при k = 5 и n = 2[6]. Мельница Wd(3,n) грациозна тогда и только тогда, когда n 0 (mod 4) или n 1 (mod 4)[7]. Галерея Примечания Gallian, 2007, с. 1-58. Weisstein, Eric W. Windmill Graph (англ.) на сайте Wolfram MathWorld. Koh, Rogers, Teo, Yap, 1980, с. 559-571. Bermond, 1979, с. 18-37. Huang, Skiena, 1994, с. 225-242. Bermond, Kotzig, Turgeon, 1978, с. 135-149. Bermond, Brouwer, Germa, 1978, с. 35-38. Литература J. A. Gallian. Dynamic Survey DS6: Graph Labeling // Electronic J. Combinatorics. — 2007. — Вып. DS6. K. M. Koh, D. G. Rogers, H. K. Teo, K. Y. Yap. Graceful graphs: some further results and problems // Congr. Numer.. — 1980. — Вып. 29. J.C. Bermond. Graph Theory and Combinatorics / R.J. Wilson. — London: Pitman, 1979. — Т. 34. — (Research Notes in Mathematics). J. Huang, S. Skiena. Gracefully labeling prisms // Ars Combinatoria. — 1994. — Вып. 38.