Parallel Knockouts in the Complete Graph

From MaRDI portal





In a parallel knockout procedure we begin with a graph \(G\). A step is defined as follows. Each non-isolated vertex chooses one of its neighbours; each chosen with equal probability. Then all chosen vertices (and their incident edges) are eliminated simultaneously from the graph. The procedure terminates when no edges remain. Let \(t\) be the smallest number of steps until termination. The set of isolated vertices at termination is called the terminating set and denoted \(G_t\). Let \(L(G)\) denote the expected cardinality of \(G_t\). Two questions are posed. (1) Which graphs have the property that every independent set can be a terminating set? (2) Does \(\lim_{n \rightarrow \infty} L(K_n)\) exist and if so what is it?











This page was built for publication: Parallel Knockouts in the Complete Graph

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