График ветряной мельницы | |
---|---|
Вершины | н ( к – 1) + 1 |
Края | нк ( к − 1)/2 |
Радиус | 1 |
Диаметр | 2 |
Обхват | 3 если к > 2 |
Хроматическое число | к |
Хроматический индекс | н ( к – 1) |
Обозначение | Wd( k , n ) |
Таблица графиков и параметров |
В математической области теории графов граф ветряной мельницы Wd( k , n ) — это неориентированный граф, построенный для k ≥ 2 и n ≥ 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) . Его хроматический многочлен может быть выведен из хроматического многочлена полного графа и равен
Доказано, что граф ветряной мельницы Wd( k , n ) не является изящным, если k > 5 . [3] В 1979 году Бермонд предположил, что граф Wd(4, n ) является изящным для всех n ≥ 4 . [4] С помощью эквивалентности с совершенными разностными семействами это было доказано для n ≤ 1000 . [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]