In the mathematical field of graph theory, the friendship graph (or Dutch windmill graph or n-fan) Fn is a planar, undirected graph with 2n + 1 vertices and 3n edges.[1]
| Friendship graph | |
|---|---|
 The friendship graph F8. | |
| Vertices | 2n + 1 |
| Edges | 3n |
| Radius | 1 |
| Diameter | 2 |
| Girth | 3 |
| Chromatic number | 3 |
| Chromatic index | 2n |
| Properties | |
| Notation | Fn |
| Table of graphs and parameters | |
The friendship graph Fn can be constructed by joining n copies of the cycle graph C3 with a common vertex, which becomes a universal vertex for the graph.[2]
By construction, the friendship graph Fn is isomorphic to the windmill graph Wd(3, n). It is unit distance with girth 3, diameter 2 and radius 1. The graph F2 is isomorphic to the butterfly graph. Friendship graphs are generalized by the triangular cactus graphs.
Friendship theorem
editThe friendship theorem of Paul Erdős, Alfréd Rényi, and Vera T. Sós (1966)[3] states that the finite graphs with the property that every two vertices have exactly one neighbor in common are exactly the friendship graphs. Informally, if a group of people has the property that every pair of people has exactly one friend in common, then there must be one person who is a friend to all the others. However, for infinite graphs, there can be many different graphs with the same cardinality that have this property.[4]
A combinatorial proof of the friendship theorem was given by Mertzios and Unger.[5] Another proof was given by Craig Huneke.[6] A formalised proof in Metamath was reported by Alexander van der Vekens in October 2018 on the Metamath mailing list.[7]
Labeling and colouring
editThe friendship graph has chromatic number 3 and chromatic index 2n. Its chromatic polynomial can be deduced from the chromatic polynomial of the cycle graph C3 and is equal to
- .
The friendship graph Fn is edge-graceful if and only if n is odd. It is graceful if and only if n ≡ 0 (mod 4) or n ≡ 1 (mod 4).[8][9]
Every friendship graph is factor-critical.
Extremal graph theory
editAccording to extremal graph theory, every graph with sufficiently many edges (relative to its number of vertices) must contain a -fan as a subgraph. More specifically, this is true for an -vertex graph if the number of edges is
where is if is odd, and is if is even. These bounds generalize Turán's theorem on the number of edges in a triangle-free graph, and they are the best possible bounds for this problem, in that for any smaller number of edges there exist graphs that do not contain a -fan.[10]
Generalizations
editAny two vertices having exactly one neighbor in common is equivalent to any two vertices being connected by exactly one path of length two. This has been generalized to -graphs, in which any two vertices are connected by a unique path of length . For no such graphs are known, and the claim of their non-existence is Kotzig's conjecture.
See also
edit- Central digraph, a directed graph with the property that every two vertices can be connected by a unique two-edge walk
References
edit- ^ Weisstein, Eric W., "Dutch Windmill Graph", MathWorld
- ^ Gallian, Joseph A. (January 3, 2007), "A dynamic survey of graph labeling", Electronic Journal of Combinatorics: DS6, doi:10.37236/27.
- ^ Erdős, Paul; Rényi, Alfréd; Sós, Vera T. (1966), "On a problem of graph theory" (PDF), Studia Sci. Math. Hungar., 1: 215–235.
- ^ Chvátal, Václav; Kotzig, Anton; Rosenberg, Ivo G.; Davies, Roy O. (1976), "There are friendship graphs of cardinal ", Canadian Mathematical Bulletin, 19 (4): 431–433, doi:10.4153/cmb-1976-064-1.
- ^ Mertzios, George; Walter Unger (2008), "The friendship problem on graphs" (PDF), Relations, Orders and Graphs: Interaction with Computer Science
- ^ Huneke, Craig (1 January 2002), "The Friendship Theorem", The American Mathematical Monthly, 109 (2): 192–194, doi:10.2307/2695332, JSTOR 2695332
- ^ van der Vekens, Alexander (11 October 2018), "Friendship Theorem (#83 of "100 theorem list")", Metamath mailing list
- ^ Bermond, J.-C.; Brouwer, A. E.; Germa, A. (1978), "Systèmes de triplets et différences associées", Problèmes Combinatoires et Théorie des Graphes (Univ. Orsay, 1976), Colloq. Intern. du CNRS, vol. 260, CNRS, Paris, pp. 35–38, MR 0539936.
- ^ Bermond, J.-C.; Kotzig, A.; Turgeon, J. (1978), "On a combinatorial problem of antennas in radioastronomy", Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, Colloq. Math. Soc. János Bolyai, vol. 18, North-Holland, Amsterdam-New York, pp. 135–149, MR 0519261.
- ^ Erdős, P.; Füredi, Z.; Gould, R. J.; Gunderson, D. S. (1995), "Extremal graphs for intersecting triangles", Journal of Combinatorial Theory, Series B, 64 (1): 89–100, CiteSeerX 10.1.1.491.974, doi:10.1006/jctb.1995.1026, MR 1328293.
