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

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

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

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

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

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

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

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

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

Граф дружеских отношений имеет хроматическое число 3 и хроматический индекс 2n. Его хроматический многочлен может быть получен из хроматического многочлена цикла C3 и равен .

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

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

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

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

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

Примечания

Литература

  • 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 friendship graphs of cardinal  // 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.