Saturation Number of Trees in the Hypercube

Abstract

A graph $H^{\prime }$ is $(H,G)$-saturated if it is $G$-free and the addition of any edge of $H$ not in $H^{\prime }$ creates a copy of $G$. The saturation number $sat(H,G)$ is the minimum number of edges in a $(H,G)$-saturated graph. We investigate bounds on the saturation number of trees $T$ in the $n$-dimensional hypercube $Q_n$. We first present a general lower bound on the saturation number based on the minimum degree of non-leaves. From there, we suggest two general methods for constructing $T$-saturated subgraphs of $Q_n$, and prove nontrivial upper bounds for specific types of trees, including paths, generalized stars, and certain caterpillars under a restriction on minimum degree with respect to diameter.

21 pages