A saturation problem in meshes

Let [Formula: see text] and [Formula: see text] be graphs, where we view [Formula: see text] as the “host” graph and [Formula: see text] as a “forbidden” graph. A spanning subgraph [Formula: see text] of [Formula: see text] is called [Formula: see text]-saturated in[Formula: see text] if [Formula: see text] contains no subgraph isomorphic to [Formula: see text], but [Formula: see text] contains [Formula: see text] for any edge [Formula: see text]. We let [Formula: see text] be the minimum number of edges in any graph [Formula: see text] which is [Formula: see text]-saturated in [Formula: see text], where [Formula: see text] if [Formula: see text] contains no copy of [Formula: see text] as a subgraph. Let [Formula: see text] be the [Formula: see text]-dimensional mesh (or grid), with vertex set [Formula: see text] integer, [Formula: see text] and edge set [Formula: see text] and [Formula: see text]. Let [Formula: see text] be the star graph on [Formula: see text] leaves. In this paper we study [Formula: see text]. We give asymptotically exact results for [Formula: see text]. We also give upper bounds for [Formula: see text], [Formula: see text], which are within a factor of [Formula: see text] from optimal when [Formula: see text]. These two results are based on constructions, as well as lower bounds we obtain for [Formula: see text] for [Formula: see text] and [Formula: see text]. Finally for arbitrary [Formula: see text] we obtain asymptotically exact results for [Formula: see text], thereby showing the asymptotic behavior of the minimum size of a maximal matching in [Formula: see text]. This result is based on a construction for the upper bound, and an edge weighting argument for the matching lower bound.