Friendship graph
Encyclopedia
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.
The friendship graph Fn can be constructed by joining n copies of the cycle graph
C3 with a common vertex.
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
.
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).
Every friendship graph is factor-critical
.
, every graph with sufficiently many edges (relative to its number of vertices) must contain a k-fan. More specifically, this is true for an n-vertex graph if the number of edges is
where f(k) is k2 − k if k is odd, and
f(k) is k2 − 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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
field of graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, the friendship graph (or dutch windmill graph or n-fan) Fn is a planar
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
undirected graph with 2n+1 vertices and 3n edges.
The friendship graph Fn can be constructed by joining n copies of the cycle graph
Cycle graph
In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...
C3 with a common vertex.
By construction, the friendship graph Fn is isomorphic to the windmill graph
Windmill graph
In the mathematical field of graph theory, the windmill graph Wd is a simple undirected graph with n+1 vertices and nk/2 edges. It is defined for k ≥ 2 and n ≥ 2....
Wd(3,n). It is unit distance
Unit distance graph
In mathematics, and particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points by an edge whenever the distance between the two points is exactly one...
with girth 3, diameter 2 and radius 1. The graph F2 is isomorphic to the butterfly graph
Butterfly graph
In the mathematical field of graph theory, the butterfly graph is a planar undirected graph with 5 vertices and 6 edges...
.
Friendship theorem
The friendship theorem of 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 a 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.Labeling and colouring
The friendship graph has chromatic number 3 and chromatic index 2n. Its chromatic polynomialChromatic polynomial
The chromatic polynomial is a polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to attack the four color problem. It was generalised to the Tutte...
can be deduced from the chromatic polynomial of the cycle graph C3 and is equal to
.The friendship graph Fn is edge-graceful
Edge-graceful labeling
In graph theory, an edge-graceful graph labeling is a type of graph labeling. This is a labeling for simple graphs, namely ones in which no two distinct edges connect the same two distinct vertices, no edge connects a vertex to itself, and the graph is connected. Edge-graceful labelings were first...
if and only if n is odd. It is graceful
Graceful labeling
In graph theory, a graceful labeling of a graph with e edges is a labeling of its vertices with distinct integers between 0 and e inclusive, such that each edge is uniquely identified by the positive, or absolute difference between its endpoints. A graph which admits a graceful labeling is called a...
if and only if n ≡ 0 (mod 4) or n ≡ 1 (mod 4).
Every friendship graph is factor-critical
Factor-critical graph
In graph theory, a mathematical discipline, a factor-critical graph is a graph with vertices in which every subgraph of vertices has a perfect matching, a subset of its edges such that each of the vertices is the endpoint of exactly one of the edges in the subset.A matching that covers all but...
.
Extremal graph theory
According to extremal graph theoryExtremal graph theory
Extremal graph theory is a branch of the mathematical field of graph theory. Extremal graph theory studies extremal graphs which satisfy a certain property. Extremality can be taken with respect to different graph invariants, such as order, size or girth...
, every graph with sufficiently many edges (relative to its number of vertices) must contain a k-fan. More specifically, this is true for an n-vertex graph if the number of edges is
where f(k) is k2 − k if k is odd, and
f(k) is k2 − 3k/2 if k is even. These bounds generalize Turán's theorem
Turán's theorem
In graph theory, Turán's theorem is a result on the number of edges in a Kr+1-free graph.An n-vertex graph that does not contain any -vertex clique may be formed by partitioning the set of vertices into r parts of equal or nearly-equal size, and connecting two vertices by an edge whenever they...
on the number of edges in a triangle-free graph
Triangle-free graph
In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally...
, 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.