Home » Subject » Graph Theory » Extremal G.T.
Importance: Low ✭
Author(s): Morrison, Natasha
Noel, Jonathan A.
Subject: Graph Theory
» Extremal Graph Theory
Keywords: bootstrap percolation
hypercube
Weak saturation
Recomm. for undergrads: yes
Posted by: Jon Noel
on: April 6th, 2016
Problem  

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 $.

Bibliography

[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.
add new comment

Reply

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