Note on an extremal problem arising for unreliable networks in parallel computing
Motivated by a certain model of parallel computing in unreliable networks we study combinatorial problems of the following type: For any graph and any integer c, what is the least number d such that removal of any d edges (or vertices) leaves a graph with a largest connected component of more than c vertices. We give rather precise estimates for the n-cube.
47
137-152
137-152
Elsevier BV
application/pdf