Asymptotic n/6 domination conjecture for degree-six triangulations

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. A dominating set of a graph is a set containing every vertex or a neighbor of every vertex. The n/6 domination conjecture. There exists a constant cc such that every nn-vertex triangulation with maximum degree 66 has a dominating set of size at most

n/6+c.n/6+c.

The paper presents this as a possible sharp strengthening of its proved n/4n/4 bound for maximum-degree-six triangulations; its truth is not established in the supplied text.

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.