Connected domination conjecture for plane triangulations

About 1 year old · traced to

Let GG be a plane triangulation of sufficiently large order nn. A connected dominating set is a subset X⊆V(G)X\subseteq V(G) such that V(G)=⋃x∈XNG[x]V(G)=\bigcup_{x\in X}N_G[x] and G[X]G[X] is connected; let γc(G)\gamma_c(G) denote the minimum cardinality of a connected dominating set.

Connected domination conjecture.

γc(G)≤3n8.\gamma_c(G)\le\frac{3n}{8}.

The paper constructs plane triangulations with γc(G)≥3∣V(G)∣/8−1\gamma_c(G)\ge 3|V(G)|/8-1, so this weaker bound is presented as a revised conjecture; the supplied status evidence says it remains open.

References

Primary source

Kengo Enami, Naoki Matsumoto and Takamasa Yashima, “Contributions to conjectures on planar graphs: Induced Subgraphs, Treewidth, and Dominating Sets”, arXiv:2506.10471 (2025).

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.