Let and be graphs. Say that a spanning subgraph of is -saturated if contains no copy of but contains a copy of for every edge . Let denote the minimum number of edges in a -saturated graph. Saturation was introduced by Erdős, Hajnal and Moon [EHM] who proved the following:
Let denote the -dimensional hypercube. Saturation of -cycles in the hypercube has been studied by Choi and Guan [CG] who proved that . This was drastically improved by Johnson and Pinto [JP] to . The saturation number for longer cycles in the hypercube is not known, though. The question above addresses this.
Another open problem is to determine the saturation number of sub-hypercubes in . This was first considered by Johnson and Pinto [JP] who proved that for fixed and . This upper bound was improved to by Morrison, Noel and Scott [MNS]. The best known lower bound on for fixed and large , also due to [MNS], is .
The results of [MNS] show that for fixed . Howver, the precise asymptotic behaviour of this quantity is unknown.
Bibliography
[CG] S. Choi and P. Guan, Minimum critical squarefree subgraph of a hypercube, Proceedings of the Thirty-Ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing, vol. 189, 2008, pp. 57–64.
[EHM] P. Erdős, A. Hajnal, and J. W. Moon, A problem in graph theory, Amer. Math. Monthly 71 (1964), 1107–1110.
[JP] J. R. Johnson and T. Pinto, Saturated subgraphs of the hypercube, arXiv:1406.1766v1, preprint, June 2014.
[MNS] N. Morrison, J. A. Noel and A. Scott, Saturation in the Hypercube and Bootstrap Percolation, arXiv:1408.5488v2, June 2015.
* indicates original appearance(s) of problem.