Fan graph

File:Fan graphs.svg

The path $P_n$ and empty graph $K_1$ in each fan graph $F_n$ are colored blue and orange respectively

In graph theory, a fan graph (also called a path-fan graph) is a graph formed by the join of a path graph and an empty graph on a single vertex. The fan graph on $n+1$ vertices, denoted $F_n$, is defined as $K_1+P_n$, where $K_1$ is a single vertex and $P_n$ is a path on $n$ vertices.

The fan graph $F_n$ has $n+1$ vertices and $2n-1$ edges.

Saturation

A graph $G$ is $H$-saturated if it does not contain $H$ as a subgraph, but the addition of any edge $e\notin E(G)$ results in at least one copy of $H$ as a subgraph. The saturation number $\text{sat}(n,H)$ is the minimum number of edges in an $H$-saturated graph on $n$ vertices, while the extremal number $\text{ex}(n,H)$ is the maximum number of edges possible in a graph $G$ on $n$ vertices that does not contain a copy of $H$.

The $t$-fan (sometimes called the friendship graph), $F_t(t\ge 2)$, is the graph consisting of $t$ edge-disjoint triangles that intersect at a single vertex $v$.

The saturation number for $F_t$ is $\text{sat}(n,F_t)=n+3t-4$ for $t\ge 2$ and $n\ge 3t-2$.

Graph coloring

The packing chromatic number ${\chi }_{\rho }(G)$ of a graph $G$ is the smallest integer $k$ for which there exists a mapping $\pi :V(G)\to 1,2,\dots ,k$ such that any two vertices of color $i$ are at distance at least $i+1$. The packing chromatic number has been studied for various fan and wheel related graphs.

See also

• Wheel graph
• Graph operations
• Friendship graph