We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science


Publication details for Professor Matthew Johnson

front coverBroersma, H.J., Johnson, M. & Paulusma, D. (2009). Upper bounds and algorithms for parallel knock-out numbers. Theoretical Computer Science 410(14): 1319-1327.

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.