Fan graph

[[File:Fan graphs.svg|thumb|The path <math> P_n </math> and empty graph <math> K_1 </math> in each ''fan graph'' <math> F_n </math> 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 <math> n + 1 </math> vertices, denoted <math> F_n </math>, is defined as <math> K_1 + P_n </math>, where <math> K_1 </math> is a single vertex and <math> P_n </math> is a path on <math> n </math> vertices.<ref name="Roy2017"> {{cite journal |last=Roy |first=S. |year=2017 |title=Packing chromatic number of certain fan and wheel related graphs |journal=AKCE International Journal of Graphs and Combinatorics |volume=14 |issue=1 |pages=63–69 |doi=10.1016/j.akcej.2016.11.001 |url=https://www.researchgate.net/publication/311394521_Packing_chromatic_number_of_certain_fan_and_wheel_related_graphs |issn=0972-8600|doi-access=free }} </ref><ref name="Fuller2023"> {{cite journal |last1=Fuller |first1=Jessica |last2=Gould |first2=Ronald J. |year=2023 |title=On fan saturated graphs |journal=Involve, a Journal of Mathematics |volume=16 |issue=4 |pages=637–657 |doi=10.2140/involve.2023.16.637}} </ref>

The fan graph <math> F_n </math> has <math> n + 1 </math> vertices and <math> 2n - 1 </math> edges.<ref name="Roy2017"/>

== Saturation==

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

The ''' <math> t </math>-fan''' (sometimes called the friendship graph), <math> F_t(t \geq 2) </math>, is the graph consisting of <math> t </math> edge-disjoint triangles that intersect at a single vertex <math> v </math>.<ref name="Fuller2023"/>

The saturation number for <math> F_t </math> is <math> \text{sat}(n, F_t) = n + 3t - 4 </math> for <math> t \geq 2 </math> and <math> n \geq 3t - 2 </math>.<ref name="Fuller2023"/>

== Graph coloring==

The packing chromatic number <math> \chi_\rho(G) </math> of a graph <math> G </math> is the smallest integer <math> k </math> for which there exists a mapping <math> \pi : V(G) \to {1, 2, \ldots, k} </math> such that any two vertices of color <math> i </math> are at distance at least <math> i + 1 </math>. The packing chromatic number has been studied for various fan and wheel related graphs.<ref name="Roy2017"/>

== References== {{reflist}}

Category:Parametric families of graphs Category:Graph operations