A graph of friendships (either a graph of a Danish mill , or an n- blade fan ) F n is a planar undirected graph with 2n + 1 vertices and 3n edges [1] .
| Friendship graph | |
|---|---|
 | |
| Top | 2n + 1 |
| Riber | 3n |
| Radius | one |
| Diameter | 2 |
| Girth | 3 |
| Chromatic number | 3 |
| Chromatic Index | 2n |
| The properties | Unit distance graph planar Euler critical factor |
| Designation | F n |
The friendship graph F n can be constructed by connecting n copies of the cycle C 3 at one common vertex [2] .
By construction, the friendship graph F n is isomorphic to the mill Wd (3, n ). The graph is a graph of unit distances , has a girth of 3, a diameter of 2, and a radius of 1. The graph F 2 is isomorphic to a butterfly .
Content
- 1 The graph of friendship relations
- 2 Marking and coloring
- 3 Extreme graph theory
- 4 notes
- 5 Literature
Friendship Theorem
The Erdos, Renyi, and Vera Sos [3] [4] friendship graph theorem states that finite graphs with the property that any two vertices have exactly one common neighbor are exactly graphs of friendship. Informally, if a group of people has the property that any pair of people has exactly one common friend, then there should be one person who is a friend of the other members of the group. For infinite graphs, however, there can be many different graphs of the same cardinality having this property [5] .
A combinatorial proof of the graph of friendship relations was given by Mertzios and Unger [6] . Another proof was given by Craig Huneck [7] .
Marking and coloring
The friendship graph has a chromatic number of 3 and a chromatic index of 2n . Its chromatic polynomial can be obtained from the chromatic polynomial of the C 3 cycle and is equal to .
The friendship graph F n has perfect edge marking if and only if n is odd. It has graceful markup if and only if n ≡ 0 (mod 4), or n ≡ 1 (mod 4) [8] [9] .
Any graph of friendships is factor-critical .
Extreme Graph Theory
According to extremal graph theory, any graph with a sufficiently large number of edges (with respect to the number of vertices) must contain a k- blade fan as a subgraph. More precisely, this is true for a graph with n vertices if the number of edges is
where f ( k ) is equal to k 2 - k if k is odd, and f ( k ) is equal to k 2 - 3 k / 2 if k is even. These boundaries generalize Turan's theorem on the number of edges in a graph without triangles and they are the best boundaries for this problem, since for any smaller number of edges there are graphs that do not contain a k- blade fan [10] .
Notes
- ↑ Weisstein, Eric W. Dutch Windmill Graph on Wolfram MathWorld .
- ↑ Gallian, 2007 , p. 1-58.
- ↑ Erdős, Rényi, Sós, 1966 .
- ↑ Erdős, Rényi, Sós, 1966 , p. 215–235.
- ↑ Chvátal, Kotzig, Rosenberg, Davies, 1976 , p. 431-433.
- ↑ Mertzios, Unger, 2008 .
- ↑ Huneke, 2002 , p. 192–194.
- ↑ Bermond, Brouwer, Germa, 1978 , p. 35-38.
- ↑ Bermond, Kotzig, Turgeon, 1978 , p. 135-149.
- ↑ Erdős, Füredi, Gould, Gunderson, 1995 , p. 89-100.
Literature
- JA Gallian. Dynamic Survey DS6: Graph Labeling // Electronic J. Combinatorics. - 2007. - January. Archived January 31, 2012.
- JC Bermond, AE Brouwer, A. Germa. Systèmes de triplets et différences associées // Problèmes Combinatoires et Théorie des Graphes. - Paris, 1978. - T. 260, Editions du Center Nationale de la Recherche Scientifique. - (Colloq. Intern. Du CNRS).
- JC Bermond, A. Kotzig, J. Turgeon. On a combinatorial problem of antennas in radioastronomy, in Combinatorics // Colloq. Math. Soc. János Bolyai, / A. Hajnal, VT Sos, eds .. - North-Holland, Amsterdam, 1978.- T. 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. - T. 1 . - S. 215–235 .
- Václav Chvátal, Anton Kotzig, Ivo G. Rosenberg, Roy O. Davies. There are friendship graphs of cardinal // Canadian Mathematical Bulletin. - 1976. - T. 19 , no. 4 . - S. 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. - January ( t. 109 , issue 2 ). - S. 192–194 . - DOI : 10.2307 / 2695332 .
- Paul Erdős , Z. Füredi, RJ Gould, DS Gunderson. Extremal graphs for intersecting triangles // Journal of Combinatorial Theory. - 1995 .-- T. 64 , no. 1 . - S. 89–100 . - DOI : 10.1006 / jctb.1995.1026 .