An upper bound on the domination number of nn-vertex connected cubic graphs

In 1996, Reed proved that the domination number γ(G)γ(G) of every nn-vertex graph GG with minimum degree at least 3 is at most 3n/83n/8. This bound is sharp for cubic graphs if there is no restriction on connectivity. In this paper we show that γ(G)≤4n/11γ(G)≤4n/11 for every nn-vertex cubic connected graph GG if n>8n>8. Note that Reed’s conjecture that γ(G)≤⌈n/3⌉γ(G)≤⌈n/3⌉ for every connected cubic nn-vertex graph GG is not true.