H.J. Broersma
Upper bounds and algorithms for parallel knock-out numbers
Broersma, H.J.; Johnson, M.; Paulusma, D.
Authors
Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
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 |
Files
Accepted Journal Article
(255 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by-nc-nd/4.0/
Copyright 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/
You might also like
On hamiltonicity of P3-dominated graphs
(2009)
Journal Article
Sharp upper bounds for the minimum number of components of 2-factors in claw-free graphs
(2009)
Journal Article
Complexity of conditional colorability of graphs
(2009)
Journal Article
More about subcolorings
(2002)
Journal Article
Radio labeling with preassigned frequencies
(2004)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search