A NEW BOUND ON THE DOMINATION NUMBER OF CONNECTED CUBIC GRAPHS
In 1996, Reed proved that the domination number, (G), of every n-vertex graph G with minimum degree at least 3 is at most 3n/8. This bound is sharp for cubic graphs if there is no restriction on connectivity. In this paper, improving an upper bound by Kostochka and Stodolsky we show that for n > 8 the domination number of every n-vertex cubic connected graph is at most ⌊5n/14⌋. This bound is sharp for even 8 < n ≤ 18.