Fan graph

The path Pn and empty graph K1 in each fan graph Fn 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 n+1 vertices, denoted Fn, is defined as K1+Pn, where K1 is a single vertex and Pn is a path on n vertices.

The fan graph Fn 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∉E(G) results in at least one copy of H as a subgraph. The saturation number sat(n,H) is the minimum number of edges in an H-saturated graph on n vertices, while the extremal number 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), Ft(t≥2), is the graph consisting of t edge-disjoint triangles that intersect at a single vertex v.

The saturation number for Ft is sat(n,Ft)=n+3t−4 for t≥2 and n≥3t−2.

Graph coloring

The packing chromatic number χρ(G) of a graph G is the smallest integer k for which there exists a mapping π:V(G)→1,2,…,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

References

  1. 1 2 3 Roy, S. (2017). "Packing chromatic number of certain fan and wheel related graphs". AKCE International Journal of Graphs and Combinatorics. 14 (1): 63–69. doi:10.1016/j.akcej.2016.11.001. ISSN 0972-8600.
  2. 1 2 3 Fuller, Jessica; Gould, Ronald J. (2023). "On fan saturated graphs". Involve, a Journal of Mathematics. 16 (4): 637–657. doi:10.2140/involve.2023.16.637.