King and Pelsmajer's bounded-exception domination conjecture for plane triangulations
King and Pelsmajer's bounded-exception domination conjecture for plane triangulations
Let be an -vertex plane triangulation, and let be a fixed nonnegative integer. A vertex has degree other than when its degree in is not equal to . A dominating set is a set of vertices such that every vertex is either in the set or adjacent to a vertex in the set.
King and Pelsmajer's conjecture. For any constant , there exists such that every -vertex plane triangulation with and at most vertices of degree other than has a dominating set of size at most .
This extends the previously studied maximum-degree-at-most- case to triangulations with only a bounded number of exceptional-degree vertices. The paper states this as a conjecture and subsequently proves a stronger bound under the same bounded-exception hypothesis.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Hong Liu and Michael J. Pelsmajer, “Dominating Sets in Triangulations on Surfaces”, arXiv:1006.1879 (2011).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.