We show that for a cubic graph on \(n\) nodes, the size of the dominating set found by the greedy algorithm is at most \(\frac{4}{9}n\), and that this bound is tight.
Citation
Suzanne M.Seager. The Greedy Algorithm for Domination in Cubic Graphs[J], Ars Combinatoria, Volume 071. 101-107. .
