Граф дружеских отношений

Граф дружеских отношений (или граф датской мельницы, или n-лопастной вентилятор) Fn — это планарный неориентированный граф с 2n+1 вершинами и 3n рёбрами.

Граф дружеских отношений Fn можно построить путём соединения n копий цикла C3 в одной общей вершине.

По построению граф дружеских отношений Fn изоморфен мельнице Wd(3,n). Граф является графом единичных расстояний, имеет обхват 3, диаметр 2 и радиус 1. Граф F2 изоморфен бабочке.

Теорема о графе дружеских отношений

Теорема о графе дружеских отношений Эрдёша, Реньи и Веры Сос утверждает, что конечные графы со свойством, что любые две вершины имеют в точности одного общего соседа, это в точности графы дружеских отношений. Неформально, если группа людей обладает свойством, что любая пара людей имеет в точности одного общего друга, то должно быть одно лицо, являющееся другом остальных членов группы. Для бесконечных графов, однако, может существовать много различных графов одной и той же мощности, имеющих это свойство.

Комбинаторное доказательство теоремы о графе дружеских отношений дали Мертциос и Унгер. Другое доказательство дал Крейг Хунеке.

Разметка и раскраска

Граф дружеских отношений имеет хроматическое число 3 и хроматический индекс 2n. Его хроматический многочлен может быть получен из хроматического многочлена цикла C3 и равен ( x − 2 ) n ( x − 1 ) n x {displaystyle (x-2)^{n}(x-1)^{n}x} .

Граф дружеских отношений Fn имеет совершенную разметку рёбер тогда и только тогда, когда n нечётно. Он имеет грациозную разметку тогда и только тогда, когда n ≡ 0 (mod 4), или n ≡ 1 (mod 4).

Любой граф дружеских отношений является фактор-критическим.

Экстремальная теория графов

Согласно экстремальной теории графов любой граф с достаточно большим числом рёбер (по отношению к числу вершин) должен содержать k-лопастной вентилятор в качестве подграфа. Более точно, это верно для графа с n вершинами, если число рёбер равно

⌊ n 2 4 ⌋ + f ( k ) , {displaystyle leftlfloor {frac {n^{2}}{4}} ight floor +f(k),}

где f(k) равно k2 − k, если k нечётно, и f(k) равно k2 − 3k/2, если k чётно. Эти границы обобщают теорему Турана о числе рёбер в графе без треугольников и они являются лучшими границами для данной задачи, поскольку для любого меньшего числа рёбер существуют графы, не содержащие k-лопастного вентилятора.