Мельница (теория графов)

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

Граф «Мельница»
Вершин (k-1)n+1
Рёбер nk(k−1)/2
Радиус 1
Диаметр 2
Обхват 3 при k > 2
Хроматическое число k
Хроматический индекс n(k-1)
Обозначение Wd(k,n)
 Медиафайлы на Викискладе

Свойства

Граф имеет (k-1)n+1 вершин и nk(k−1)/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). Его хроматический многочлен может быть получен из хроматического полинома полного графа и равен

Доказано, что граф «мельница» 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].

Галерея
Малые графы-мельницы.

Примечания
  1. Gallian, 2007, с. 1-58.
  2. Weisstein, Eric W. Windmill Graph (англ.) на сайте Wolfram MathWorld.
  3. Koh, Rogers, Teo, Yap, 1980, с. 559-571.
  4. Bermond, 1979, с. 18-37.
  5. Huang, Skiena, 1994, с. 225-242.
  6. Bermond, Kotzig, Turgeon, 1978, с. 135-149.
  7. 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. — London: Pitman, 1979. — Т. 34. — (Research Notes in Mathematics).
  • J. Huang, S. Skiena. Gracefully labeling prisms // Ars Combinatoria. — 1994. — Вып. 38.
  • J. C. Bermond, A. Kotzig, J. Turgeon. Proc. 18 Hungarian Combinatorial Colloquium, Keszthely (1976) / A. Hajnal and V. T. Sos, eds.. — North-Holland, Amsterdam, 1978. — (Colloquia mathematica Societatis János Bolyai).
  • J.C. Bermond, A. E. Brouwer, A. Germa. Problèmes Combinatoires et Théorie des Graphes. — Paris: Editions du Centre Nationale de la Recherche Scientifique, 1978. — Т. 260. — (Colloq. Intern. du CNRS).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.