We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Upper bounds and algorithms for parallel knock-out numbers.

Broersma, Hajo and Johnson, Matthew and Paulusma, Daniel (2009) 'Upper bounds and algorithms for parallel knock-out numbers.', Theoretical computer science., 410 (14). pp. 1319-1327.


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.

Item Type:Article
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF
Publisher Web site:
Publisher statement:© 2008 This manuscript version is made available under the CC-BY-NC-ND 4.0 license
Date accepted:No date available
Date deposited:11 December 2015
Date of first online publication:March 2009
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar