Gaps in the Saturation Spectrum of Trees

Abstract

A graph G is H-saturated if H is not a subgraph of G but the addition of any edge from the complement of G to G results in a copy of H. The minimum number of edges (the size) of an H-saturated graph on n vertices is denoted sat(n,H), while the maximum size is the well studied extremal number, ex(n,H). The saturation spectrum for a graph H is the set of sizes of H-saturated graphs between sat(n,H) and ex(n,H). In this paper we show that paths, trees with a vertex adjacent to many leaves, and brooms have a gap in the saturation spectrum.

Keywords

• saturation spectrum
• tree
• saturation number
• 05c35
• 05c05