Domination conjecture for triangulations with finitely many non-six-valent vertices

About 18 years old · traced to

A triangulation is a plane graph in which every face, including the outer face, is bounded by a triangle. The degree of a vertex is its number of incident edges. The bounded-exception domination conjecture. For every constant tt, there exists an integer ntn_t such that every nn-vertex triangulation with at most tt vertices whose degree is not 66, and with n≥ntn\geq n_t, has a dominating set of size at most n/4n/4. This extends the paper's maximum-degree-six result to triangulations that are degree six except at a bounded number of vertices; the supplied text does not resolve it.

References

Primary source

Erika L. C. King and Michael J. Pelsmajer, “Dominating Sets in Plane Triangulations”, arXiv:0806.2421 (2010).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.