Fan graph

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]

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]

• Wheel graph
• Graph operations
• Friendship graph