# Fan graph

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Fan_graph
> Markdown URL: https://mediated.wiki/source/Fan_graph.md
> Source: https://en.wikipedia.org/wiki/Fan_graph
> Source revision: 1326288613
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

[[File:Fan graphs.svg|thumb|The [path](/source/path_graph) <math> P_n </math> and [empty graph](/source/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](/source/graph_join) of a [path graph](/source/path_graph) and an [empty graph](/source/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](/source/saturation_(graph_theory)) <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](/source/Forbidden_subgraph_problem) <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](/source/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](/source/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"/>

== See also==

*[Wheel graph](/source/Wheel_graph)
*[Graph operations](/source/Graph_operations)
*[Friendship graph](/source/Friendship_graph)

== References==
{{reflist}}

{{graph-stub}}

Category:Parametric families of graphs
Category:Graph operations

---
Adapted from the Wikipedia article [Fan graph](https://en.wikipedia.org/wiki/Fan_graph) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Fan_graph?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.