### Abstract

We consider parallel knock-out schemes, a procedure on graphs introduced by Lampert and Slater in 1997 in which each vertex eliminates exactly one of its neighbors in each round. We are considering cases in which after a finite number of rounds, where the minimimum number is called the parallel knock-out number, no vertices of the graph are left. We derive a number of combinatorial and algorithmical results on parallel knock-out numbers.
We observe that for families of sparse graphs (like planar graphs, or graphs with bounded tree-width), the parallel knock-out number grows at most logarithmically with the number n of vertices, which is basically tight for trees. Furthermore, we construct a family of bipartite graphs for which the parallel knock-out number grows proportionally to the square root of n. We characterize trees with parallel knock-out number at most 2, and show that the parallel knock-out number for trees can be computed in polynomial time via a dynamic programming approach, whereas the general problem is known to be NP-hard. Finally we show that claw-free graphs with minimum degree at least 2 have parallel knock-out number at most 2, and that the lower bound on the minimum degree is best possible.

Original language | English |
---|---|

Title of host publication | Mathematical Foundations of Computer Science (Proceedings 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004) |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 204-214 |

DOIs | |

Publication status | Published - 2004 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Volume | 3153 |

ISSN (Print) | 0302-9743 |

## Fingerprint Dive into the research topics of 'Parallel knock-out schemes in networks'. Together they form a unique fingerprint.

## Cite this

Broersma, H. J., Fomin, F. V., & Woeginger, G. J. (2004). Parallel knock-out schemes in networks. In

*Mathematical Foundations of Computer Science (Proceedings 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004)*(pp. 204-214). (Lecture Notes in Computer Science; Vol. 3153). Springer. https://doi.org/10.1007/978-3-540-28629-5_13