Fan graph

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 path $P_{n}$ and empty graph $K_{1}$ in each fan graph $F_{n}$ are colored blue and orange respectively

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\geq 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\geq 2$ and $n\geq 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,\ldots ,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