请输入您要查询的百科知识：

　

词条 Friendship graph
释义

  1. Friendship theorem

  2. Labeling and colouring

  3. Extremal graph theory

  4. References

{{infobox graph
| name = Friendship graph
| image =
| image_caption = The friendship graph F8.
| vertices = 2n+1
| edges = 3n
| automorphisms =
| chromatic_number = 3
| girth = 3
| diameter = 2
| radius = 1
| chromatic_index = 2n
|notation = Fn
| properties = {{plainlist|1=
  • Unit distance
  • Planar
  • Eulerian
  • factor-critical
  • locally linear

}}
}}

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]

The friendship graph Fn can be constructed by joining n copies of the cycle graph C3 with a common vertex.[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 theorem

The friendship theorem of {{harvs|first1=Paul|last1=Erdős|author1-link=Paul Erdős|first2=Alfréd|last2=Rényi|author2-link=Alfréd Rényi|first3=Vera T.|last3=Sós|author3-link=Vera T. Sós|year=1966|txt}}[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 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

According 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]

References

1. ^{{MathWorld|urlname=DutchWindmillGraph|title=Dutch Windmill Graph}}
2. ^{{citation|last=Gallian|first=J. A.|url=http://www.combinatorics.org/Surveys/ds6.pdf|title=Dynamic Survey DS6: Graph Labeling|journal= Electronic Journal of Combinatorics|at=DS6, 1-58|date=January 3, 2007}}.
3. ^{{citation|first1=Paul|last1=Erdős|author1-link=Paul Erdős|first2=Alfréd|last2=Rényi|author2-link=Alfréd Rényi|first3=Vera T.|last3=Sós|author3-link=Vera T. Sós|url=http://www.renyi.hu/~p_erdos/1966-06.pdf|title=On a problem of graph theory|journal=Studia Sci. Math. Hungar.|volume=1|year=1966|pages=215–235}}.
4. ^{{citation|first1=Václav|last1=Chvátal|author1-link=Václav Chvátal|first2=Anton|last2=Kotzig|first3=Ivo G.|last3=Rosenberg|first4=Roy O.|last4=Davies|title=There are friendship graphs of cardinal |journal=Canadian Mathematical Bulletin|volume=19|issue=4|year=1976|pages=431–433|doi=10.4153/cmb-1976-064-1}}.
5. ^{{citation|last=Mertzios|first=George|author2=Walter Unger|title=The friendship problem on graphs|journal=Relations, Orders and Graphs: Interaction with Computer Science|date=2008|url=http://www.dur.ac.uk/george.mertzios/papers/Conf/Conf_Windmills.pdf}}
6. ^{{citation|jstor=2695332|title=The Friendship Theorem|first=Craig|last=Huneke|date=1 January 2002|publisher=|journal=The American Mathematical Monthly|volume=109|issue=2|pages=192–194|doi=10.2307/2695332}}
7. ^Alexander van der Vekens, Friendship Theorem (#83 of "100 theorem list") (11 October 2018) https://groups.google.com/forum/#!msg/metamath/j3EjD6ibhvo/ZVlOD3noBAAJ
8. ^{{citation | last1 = Bermond | first1 = J.-C. | last2 = Brouwer | first2 = A. E. | author2-link = Andries Brouwer | last3 = Germa | first3 = A. | contribution = Systèmes de triplets et différences associées | mr = 539936 | pages = 35–38 | publisher = CNRS, Paris | series = Colloq. Intern. du CNRS | title = Problèmes Combinatoires et Théorie des Graphes (Univ. Orsay, 1976) | volume = 260 | year = 1978}}.
9. ^{{citation | last1 = Bermond | first1 = J.-C. | last2 = Kotzig | first2 = A. | last3 = Turgeon | first3 = J. | contribution = On a combinatorial problem of antennas in radioastronomy | mr = 519261 | pages = 135–149 | publisher = North-Holland, Amsterdam-New York | series = Colloq. Math. Soc. János Bolyai | title = Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I | volume = 18 | year = 1978}}.
10. ^{{citation | last1 = Erdős | first1 = P. | author1-link = Paul Erdős | last2 = Füredi | first2 = Z. | author2-link = Zoltán Füredi | last3 = Gould | first3 = R. J. | author3-link = Ronald J. Gould | last4 = Gunderson | first4 = D. S. | doi = 10.1006/jctb.1995.1026 | issue = 1 | journal = Journal of Combinatorial Theory | mr = 1328293 | pages = 89–100 | series = Series B | title = Extremal graphs for intersecting triangles | url = http://www.math.uiuc.edu/~z-furedi/PUBS/furedi_erdos_gould_gunderson_triangles.ps | volume = 64 | year = 1995}}.

2 : Parametric families of graphs|Planar graphs
随便看

　

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

　

Copyright © 2023 OENC.NET All Rights Reserved
京ICP备2021023879号 更新时间：2024/11/13 11:41:13