← All problems

Goddard–Henning thoroughly dispersed family conjecture

Every finite cubic graph GG has four total dominating sets D1,D2,D3,D4⊆V(G)D_1,D_2,D_3,D_4\subseteq V(G) such that, for every i∈{1,2,3,4}i\in\{1,2,3,4\} and every vertex v∈V(G)v\in V(G), NG(v)∩Di≠∅N_G(v)\cap D_i\ne\varnothing, and every vertex belongs to at most two of the sets: ∣{i∈{1,2,3,4}:v∈Di}∣≤2\left|\{i\in\{1,2,3,4\}:v\in D_i\}\right|\le 2. The analogous hypergraph question asks whether every 33-uniform, 33-regular hypergraph HH has four transversals T1,T2,T3,T4⊆V(H)T_1,T_2,T_3,T_4\subseteq V(H) such that ∣{i∈{1,2,3,4}:v∈Ti}∣≤2\left|\{i\in\{1,2,3,4\}:v\in T_i\}\right|\le 2 for every v∈V(H)v\in V(H).

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

An October 2026 preprint claims to settle the conjecture for cubic graphs and the corresponding hypergraph question, but the claim has not been independently checked.

The conjecture asks whether every cubic graph admits four total dominating sets covering each vertex at most twice, equivalently a thoroughly dispersed family of four sets. The 2016 formulation also poses the analogous question for 33-uniform, 33-regular hypergraphs.

Known results

  • The 2016 paper states this as Conjecture 37 and gives no proof.
  • Computations reported there support the conjecture for tested connected cubic graphs, with exceptional graphs attaining the known lower value.
  • The same paper proves only the asymptotic bound FTD⁡(G)≥2−o(1)\operatorname{FTD}(G)\ge 2-o(1), equivalently a hypergraph bound FDT⁡(H)≥2n/(n+1)\operatorname{FDT}(H)\ge 2n/(n+1) for connected 33-regular, 33-uniform hypergraphs.

October 2026 preprint

Hyemin Kwon, Boram Park, and Yoshio Sano claim that every cubic graph has four total dominating sets covering each vertex at most twice, and that the analogous hypergraph question is answered. This is an unrefereed preprint without independent mathematical verification.

Current status (as of October 2026): The four-set statements are claimed solved by an unrefereed preprint, but remain unverified; the earlier literature treated them as open conjectures.

Sources

Solutions 0

No solutions have been posted yet.