Recomm. for undergrads: yes
Posted by: Jon Noel
on: April 6th, 2016

Determine $ \text{wsat}(K_n,Q_3) $.

Given graphs $ G $ and $ H $, let $ \text{wsat}(G,H) $ denote the minimum number of edges in a subgraph $ F $ of $ G $ such that the edges of $ E(G)\setminus E(F) $ can be added to $ F $, one edge at a time, so that each edge completes a copy of $ H $ when it is added.

Of course, if one can solve the problem above, then a natural next step is to determine $ \text{wsat}(K_n,Q_m) $ for all $ n $ and $ m $.

Morrison, Noel and Scott [MNS] solved the related problem of determining $ \text{wsat}(Q_d,Q_m) $ for all $ d $ and $ m $.


[MNS] N. Morrison, J. A. Noel, A. Scott. Saturation in the hypercube and bootstrap percolation. To appear in Combin. Probab. Comput.

* indicates original appearance(s) of problem.


Comments are limited to a maximum of 1000 characters.
More information about formatting options