Saturation numbers for trees (Q2380246)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Saturation numbers for trees |
scientific article |
Statements
Saturation numbers for trees (English)
0 references
26 March 2010
0 references
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.
0 references