Fan graph
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
P_n and empty graph K_1 in each fan graph F_n 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 F_n , is defined as K_1 + P_n , where K_1 is a single vertex and P_n is a path on n vertices. The fan graph F_n has n + 1 vertices and 2n - 1 edges.
P_n and empty graph K_1 in each fan graph F_n 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 F_n , is defined as K_1 + P_n , where K_1 is a single vertex and P_n is a path on n vertices. The fan graph F_n 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 \notin E(G) results in at least one copy of H as a subgraph. The saturation number \text{sat}(n, H) is the minimum number of edges in an H -saturated graph on n vertices, while the extremal number \text{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), F_t(t \geq 2) , is the graph consisting of t edge-disjoint triangles that intersect at a single vertex v . The saturation number for F_t is \text{sat}(n, F_t) = n + 3t - 4 for t \geq 2 and n \geq 3t - 2 .
Graph coloring
The packing chromatic number \chi_\rho(G) of a graph G is the smallest integer k for which there exists a mapping \pi : V(G) \to {1, 2, \ldots, 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
Wheel graph Graph operations Friendship graph
References
Text derived from https://en.wikipedia.org/w/index.php?oldid=1326288613 under CC BY-SA 4.0; modifications have been made.