Saturation numbers for trees (Q2380246)

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.