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

Граф дружеских отношений
Вершин	2n+1
Рёбер	3n
Радиус	1
Диаметр	2
Обхват	3
Хроматическое число	3
Хроматический индекс	2n
Свойства	Граф единичных расстояний планарный эйлеров фактор-критический
Обозначение	Fn
Медиафайлы на Викискладе

Графы дружеских отношений F₂, F₃ и F₄.

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

Граф дружеских отношений F_n можно построить путём соединения n копий цикла C₃ в одной общей вершине^[2].

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

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

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

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

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

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

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

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

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

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

${\displaystyle \left\lfloor {\frac {n^{2}}{4}}\right\rfloor +f(k),}$

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

Примечания

1. Weisstein, Eric W. Dutch Windmill Graph (англ.) на сайте Wolfram MathWorld.
2. Gallian, 2007, с. 1-58.
3. Erdős, Rényi, Sós, 1966.
4. Erdős, Rényi, Sós, 1966, с. 215–235.
5. Chvátal, Kotzig, Rosenberg, Davies, 1976, с. 431–433.
6. Mertzios, Unger, 2008.
7. Huneke, 2002, с. 192–194.
8. Bermond, Brouwer, Germa, 1978, с. 35-38.
9. Bermond, Kotzig, Turgeon, 1978, с. 135-149.
10. Erdős, Füredi, Gould, Gunderson, 1995, с. 89–100.

Литература

• J. A. Gallian. Dynamic Survey DS6: Graph Labeling // Electronic J. Combinatorics. — 2007. — Январь. Архивировано 31 января 2012 года.
• J.C. Bermond, A. E. Brouwer, A. Germa. Systèmes de triplets et différences associées // Problèmes Combinatoires et Théorie des Graphes. — Paris, 1978. — Т. 260, Editions du Centre Nationale de la Recherche Scientifique. — (Colloq. Intern. du CNRS).
• J. C. Bermond, A. Kotzig, J. Turgeon. On a combinatorial problem of antennas in radioastronomy, in Combinatorics // Colloq. Math. Soc. János Bolyai, / A. Hajnal, V. T. Sos, eds.. — North-Holland, Amsterdam, 1978. — Т. 18, 2 vols..
• Paul Erdős, Alfréd Rényi, Vera T. Sós. On a problem of graph theory // Studia Sci. Math. Hungar.. — 1966. — Т. 1. — С. 215–235.
• Václav Chvátal, Anton Kotzig, Ivo G. Rosenberg, Roy O. Davies. There are ${\displaystyle \scriptstyle 2^{\aleph _{\alpha }}}$ friendship graphs of cardinal ${\displaystyle \scriptstyle \aleph _{\alpha }}$ // Canadian Mathematical Bulletin. — 1976. — Т. 19, вып. 4. — С. 431–433. — doi:10.4153/cmb-1976-064-1.
• George Mertzios, Walter Unger. The friendship problem on graphs // Relations, Orders and Graphs: Interaction with Computer Science. — 2008.
• Craig Huneke. The Friendship Theorem // The American Mathematical Monthly. — 2002. — Январь (т. 109, вып. 2). — С. 192–194. — doi:10.2307/2695332. — JSTOR 2695332.
• Paul Erdős, Z. Füredi, R. J. Gould, D. S. Gunderson. Extremal graphs for intersecting triangles // Journal of Combinatorial Theory. — 1995. — Т. 64, вып. 1. — С. 89–100. — doi:10.1006/jctb.1995.1026.