Вітряк (теорія графів)
У теорії графів «вітряк» Wd(k,n) — це неорієнтований граф, побудований для k ≥ 2 і n ≥ 2 об'єднанням n копій повних графів Kk в одній спільній вершині. Тобто це сума за 1-клікою цих повних графів[1].
Властивості ред.
Граф має (k−1)n+1 вершин і nk(k−1)/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[2]. 1979 року Бермонд висловив гіпотезу, що Wd(4,n) є граціозним для всіх n ≥ 4[3]. Відомо, що це так для n ≤ 22[4]. Бермонд, Котціг і Тургеон довели, що Wd(k,n) не є граціозними при k = 4 і n = 2 або n = 3, і при k = 5 і n = 2[5]. Вітряк Wd(3,n) граціозний тоді і тільки тоді, коли n ≡ 0 (mod 4) або n ≡ 1 (mod 4)[6].
Галерея ред.
Примітка ред.
- ↑ Gallian, 2007, с. 1-58.
- ↑ 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 (3 січня). Архівовано з джерела 31 січня 2012. Процитовано 29 липня 2021.
- K. M. Koh, D. G. Rogers, H. K. Teo, K. Y. Yap. Graceful graphs: some further results and problems // Congr. Numer.. — 1980. — Вип. 29 (21 квітня).
- 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 (21 квітня).
- 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)