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.
|Full text:||(AM) Accepted Manuscript|
Available under License - Creative Commons Attribution Non-commercial No Derivatives.
Download PDF (249Kb)
|Publisher Web site:||http://dx.doi.org/10.1016/j.tcs.2008.03.024|
|Publisher statement:||© 2008 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/|
|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|