Friendship graph

Friendship graph
	The friendship graph F8.
Vertices	2n+1
Edges	3n
Radius	1
Diameter	2
Girth	3
Chromatic number	3
Chromatic index	2n
Properties	Unit distance; Planar; Eulerian; factor-critical; locally linear;
Notation	Fn
	Table of graphs and parameters

In the mathematical field of graph theory, the friendship graph (or Dutch windmill graph or n-fan) F_n is a planar undirected graph with 2n+1 vertices and 3n edges.[1]

The friendship graphs F₂, F₃ and F₄.

The friendship graph F_n can be constructed by joining n copies of the cycle graph C₃ with a common vertex.[2]

By construction, the friendship graph F_n is isomorphic to the windmill graph Wd(3, n). It is unit distance with girth 3, diameter 2 and radius 1. The graph F₂ is isomorphic to the butterfly graph.

Friendship theorem

The 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

The friendship graph has chromatic number 3 and chromatic index 2n. Its chromatic polynomial can be deduced from the chromatic polynomial of the cycle graph C₃ and is equal to $(x-2)^{n}(x-1)^{n}x$ .

The friendship graph F_n 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

According to extremal graph theory, every graph with sufficiently many edges (relative to its number of vertices) must contain a $k$ -fan as a subgraph. More specifically, this is true for an $n$ -vertex graph if the number of edges is

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

where $f(k)$ is $k^{2}-k$ if $k$ is odd, and $f(k)$ is $k^{2}-3k/2$ if $k$ 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 $k$ -fan.[10]

gollark: I could have my gecko visit it.

gollark: 3 is a lower bound.

gollark: See? That's three people, at least, lyricly.

gollark: Visit my website tomorrow, it has an april fools' joke set up.

gollark: I hope I got the timing logic right. I tested it on a different day, but can hardly know how if I got it right.

References

Weisstein, Eric W. "Dutch Windmill Graph". MathWorld.
Gallian, J. A. (January 3, 2007), "Dynamic Survey DS6: Graph Labeling" (PDF), Electronic Journal of Combinatorics, DS6, 1-58, archived from the original (PDF) on January 31, 2012, retrieved September 16, 2009.
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 $\scriptstyle 2^{\aleph _{\alpha }}$ friendship graphs of cardinal $\scriptstyle \aleph _{\alpha }$ ", 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@googlegroups.com (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, 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, 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, doi:10.1006/jctb.1995.1026, MR 1328293.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Weisstein, Eric W. "Dutch Windmill Graph". MathWorld.

[2] Gallian, J. A. (January 3, 2007), "Dynamic Survey DS6: Graph Labeling" (PDF), Electronic Journal of Combinatorics, DS6, 1-58, archived from the original (PDF) on January 31, 2012, retrieved September 16, 2009.

[3] 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.

[4] Chvátal, Václav; Kotzig, Anton; Rosenberg, Ivo G.; Davies, Roy O. (1976), "There are $\scriptstyle 2^{\aleph _{\alpha }}$ friendship graphs of cardinal $\scriptstyle \aleph _{\alpha }$ ", Canadian Mathematical Bulletin, 19 (4): 431–433, doi:10.4153/cmb-1976-064-1.

[5] Mertzios, George; Walter Unger (2008), "The friendship problem on graphs" (PDF), Relations, Orders and Graphs: Interaction with Computer Science

[6] Huneke, Craig (1 January 2002), "The Friendship Theorem", The American Mathematical Monthly, 109 (2): 192–194, doi:10.2307/2695332, JSTOR 2695332

[7] van der Vekens, Alexander (11 October 2018). "Friendship Theorem (#83 of "100 theorem list")". metamath@googlegroups.com (Mailing list).

[8] 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, 260, CNRS, Paris, pp. 35–38, MR 0539936.

[9] 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, 18, North-Holland, Amsterdam-New York, pp. 135–149, MR 0519261.

[10] 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, doi:10.1006/jctb.1995.1026, MR 1328293.