Saturation Number of Trees in the Hypercube

MaRDI QIDQ6255016zbMATH OpenFDO

Authors Kavish Gandhi, Chiheon Kim

Publication date 28 September 2014

Mathematics Subject Classification ID

Trees (05C05) Extremal combinatorics (05D99)

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.

This page was built for publication: Saturation Number of Trees in the Hypercube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6255016)