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 ${\displaystyle n+1}$ vertices, denoted ${\displaystyle F_{n}}$, is defined as ${\displaystyle K_{1}+P_{n}}$, where ${\displaystyle K_{1}}$ is a single vertex and ${\displaystyle P_{n}}$ is a path on ${\displaystyle n}$ vertices.^[1][2]

The path ${\displaystyle P_{n}}$ and empty graph ${\displaystyle K_{1}}$ in each fan graph ${\displaystyle F_{n}}$ are colored blue and orange respectively

The fan graph ${\displaystyle F_{n}}$ has ${\displaystyle n+1}$ vertices and ${\displaystyle 2n-1}$ edges.^[1]

Saturation

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

The ${\displaystyle t}$-fan (sometimes called the friendship graph), ${\displaystyle F_{t}(t\geq 2)}$, is the graph consisting of ${\displaystyle t}$ edge-disjoint triangles that intersect at a single vertex ${\displaystyle v}$.^[2]

The saturation number for ${\displaystyle F_{t}}$ is ${\displaystyle {\text{sat}}(n,F_{t})=n+3t-4}$ for ${\displaystyle t\geq 2}$ and ${\displaystyle n\geq 3t-2}$.^[2]

Graph coloring

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

See also

• Wheel graph
• Graph operations
• Friendship graph