Publication details for Professor Matthew JohnsonBroersma, H.J., Johnson, M. & Paulusma, D. (2009). Upper bounds and algorithms for parallel knock-out numbers. Theoretical Computer Science 410(14): 1319-1327.
- Publication type: Journal Article
- ISSN/ISBN: 0304-3975
- DOI: 10.1016/j.tcs.2008.03.024
- Keywords: Parallel knock-out schemes; Claw-free graphs; Computational complexity.
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
We study parallel knock-out schemes for graphs. These schemes proceed in rounds in each of which each surviving vertex simultaneously eliminates one of its surviving neighbours; a graph is reducible if such a scheme can eliminate every vertex in the graph. We resolve the square-root conjecture, first posed at MFCS 2004, by showing that for a reducible graph G, the minimum number of required rounds is View the MathML source; in fact, our result is stronger than the conjecture as we show that the minimum number of required rounds is View the MathML source, where α is the independence number of G. This upper bound is tight. We also show that for reducible K1,p-free graphs at most p−1 rounds are required. It is already known that the problem of whether a given graph is reducible is NP-complete. For claw-free graphs, however, we show that this problem can be solved in polynomial time. We also pinpoint a relationship with (locally bijective) graph homomorphisms.