Upper bounds and algorithms for parallel knock-out numbers

Broersma, H.J.; Johnson, M.; Paulusma, D.

Abstract

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.

Citation

Broersma, H., Johnson, M., & Paulusma, D. (2009). Upper bounds and algorithms for parallel knock-out numbers. Theoretical Computer Science, 410(14), 1319-1327. https://doi.org/10.1016/j.tcs.2008.03.024

• Journal Article Type: Article
• Publication Date: Mar 1, 2009
• Deposit Date: Apr 17, 2009
• Publicly Available Date: Dec 11, 2015
• Journal: Theoretical Computer Science
• Print ISSN: 0304-3975
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 410
• Issue: 14
• Pages: 1319-1327
• DOI: https://doi.org/10.1016/j.tcs.2008.03.024
• Keywords: Parallel knock-out schemes; Claw-free graphs; Computational complexity.
• Public URL: https://durham-repository.worktribe.com/output/1528784