Domination in cubic graphs

Status open medium confidence

Reed's 1996 conjecture that $\gamma(G) \leq \lceil |G|/3 \rceil$ for all cubic graphs was disproved for graphs of connectivity 1 and 2 (Kelmans 2006, Kostochka–Stodolsky, Stodolsky 2008), but the 3-connected case posed by Reed remains open. The strongest known upper bound for large-girth cubic graphs is $\gamma(G) \leq 0.2999|G|$ (Kral–Skoda–Volec), and recent work by Dorbec–Henning (2024) makes partial progress on related girth-based and bipartite variants of the 1/3-threshold conjecture, but does not directly address the 3-connected case.

Cited literature (1)

• partial The 1/3-conjectures for domination in cubic graphs (2024)
  Paul Dorbec, Michael A. Henning · arXiv preprint · arXiv:2401.17820

  Proves Verstraete's conjecture ($\gamma(G) \leq n/3$ for cubic graphs of girth $\geq 6$) when no 7- or 8-cycle is present, and proves Kostochka's conjecture ($\gamma(G) \leq n/3$ for cubic bipartite graphs) when no 4- or 8-cycle is present; the original 3-connected conjecture is not addressed.

Reviewer notes. Kelmans (math/0607512, 2006, pre-posting) disproved Reed's conjecture for 2-connected cubic graphs and explicitly proposed a strengthened conjecture for 3-connected cubic graphs, corroborating that the 3-connected case is still open. Stodolsky (Electron. J. Combin. 2008, pre-posting) independently showed counterexamples for 2-connected graphs. The Kral–Skoda–Volec paper (arXiv:0907.1166, submitted July 2009, before OPG posting) is already in the OPG bibliography; its journal publication appeared in J. Graph Theory 69 (2012). No paper found after 2009-08-19 directly proves or disproves the 3-connected case.

Auto-reviewed 2026-05-08 with claude-sonnet-4-6 (worker 04) (web search enabled).