PROFILPELAJAR.COM

Граф товаришування
Граф товаришування
Вершин	2n+1
Ребер	3n
Радіус	1
Діаметр	2
Обхват	3
Хроматичне число	3
Хроматичний індекс	2n
Властивості	граф одиничних відстаней; планарний; ейлерів; фактор-критичний

Граф товаришування (або граф данського млина, або 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_{3, він} дорівнює $(x-2)^{n}(x-1)^{n}x$ .

Граф товаришування F_n має досконалу розмітку ребер тоді і тільки тоді, коли n непарне. Він має граціозну розмітку тоді і тільки тоді, коли n ≡ 0 (mod 4), або n ≡ 1 (mod 4)^[8]^[9].

Будь-який граф товаришування є фактор-критичним.

Екстремальна теорія графів

Згідно з екстремальною теорією графів будь-який граф з досить великим числом ребер (відносно числа вершин) повинен містити, як підграф, k-лопатевий вітряк. Точніше, це істинне для графа з n вершинами, якщо число ребер дорівнює

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

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

Примітки

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

Література

J. A. Gallian^[en]. Dynamic Survey DS6: Graph Labeling // Electronic J. Combinatorics. — 2007. — Jan.. Архівовано з джерела 31 січня 2012.
J.C. Bermond, A. E. Brouwer^[en], 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^[en], 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 (3 січня). — С. 215–235. Архівовано з джерела 8 серпня 2021. Процитовано 1 серпня 2021.
Václav Chvátal, Anton Kotzig, Ivo G. Rosenberg, Roy O. Davies. There are $\scriptstyle 2^{\aleph _{\alpha }}$ friendship graphs of cardinal $\scriptstyle \aleph _{\alpha }$ // Canadian Mathematical Bulletin. — 1976. — Т. 19, вип. 4 (3 січня). — С. 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. — 3 січня.
Craig Huneke. The Friendship Theorem // The American Mathematical Monthly. — 2002. — Т. 109, вип. 2 (January). — С. 192–194. — DOI:10.2307/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 (3 січня). — С. 89–100. — (Series B). — DOI:10.1006/jctb.1995.1026.