Goddard–Henning conjecture on independent domination in cubic graphs

About 9 years old · traced to

Let GG be a connected cubic graph of order nn, and let i(G)i(G) denote its independent domination number. Reed's bound concerns domination in cubic graphs, and the exceptional graphs here are K3,3K_{3,3} and the 55-prism C5□K2C_5 \mathbin{\Box} K_2.

Goddard–Henning conjecture. If

G∉{K3,3,C5□K2},G \notin \{K_{3,3}, C_5 \mathbin{\Box} K_2\},

then

i(G)≤38n.i(G) \leq \frac{3}{8}n.

The conjecture asks whether Reed's 38\frac{3}{8} upper bound for the domination number extends to independent domination, apart from the two stated exceptions. The supplied source presents it as a conjecture; its resolution is not specified here.

References

Primary source

Boštjan Brešar, Tanja Dravec and Michael A. Henning, “A proof of the 38-conjecture for independent domination in cubic graphs”, arXiv:2510.14762 (2025).

Additional references

4 papers in this index state this conjecture (2017–2025). The statement above is taken from the most recent of them; the others are arXiv:2303.09993, arXiv:2001.02946, arXiv:1708.01725.

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.