Saturation numbers for trees
Summary: For a fixed graph \(H\), a graph \(G\) is \(H\)-saturated if there is no copy of \(H\) in \(G\), but for any edge \(e\not\in G\), there is a copy of \(H\) in \(G+e\). The collection of \(H\)-saturated graphs of order \(n\) is denoted by \({\mathbf {SAT}}(n,H)\), and the saturation number, \({\mathbf {sat}}(n,H)\), is the minimum number of edges in a graph in \({\mathbf {SAT}}(n,H)\). Let \(T_k\) be a tree on \(k\) vertices. The saturation numbers \({\mathbf {sat}}(n,T_k)\) for some families of trees are determined precisely. Some classes of trees for which \({\mathbf {sat}}(n,T_k)< n\) are identified, and trees \(T_k\) in which graphs in \({\mathbf {SAT}}(n,T_k)\) are forests are presented. Also, families of trees for which \({\mathbf {sat}}(n,T_k)\geq n\) are presented. The maximum and minimum values of \({\mathbf {sat}}(n,T_k)\) for the class of all trees are given. Some properties of \({\mathbf {sat}}(n,T_k)\) and \({\mathbf {SAT}}(n,T_k)\) for trees are discussed.
- Gaps in the saturation spectrum of trees
- Saturation numbers for Ramsey-minimal graphs
- Saturation numbers for disjoint stars
- A lower bound on the saturation number, and graphs for which it is sharp
- Linear bounds for cycle-free saturation games
- Saturation numbers for nearly complete graphs
- The partite saturation number of spider
- Saturation numbers for families of graph subdivisions
- Saturation number for linear forest \(2{P_3} \bigcup t{P_2}\)
- Weak saturation numbers for sparse graphs
- Saturation for the 3-uniform loose 3-cycle
- Saturation numbers for linear forests $P_6 + tP_2$
- Saturation numbers for linear forests 2 P₄ t P₂^
- A lower bound on the saturation number and a strengthening for triangle-free graphs
- Some results on the saturation number of graphs
- (K₁ P_t)-saturated graphs with minimum number of edges
- The saturation number of W₄
- Saturation numbers of balanced double stars
- Saturation numbers for linear forests P₅ tP₂
This page was built for publication: Saturation numbers for trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2380246)
