Domination in graphs with minimum degree two

Abstract

Abstract The domination number γ( G ) of a graph G = ( V, E ) is the minimum cardinality of a subset of V such that every vertex is either in the set or is adjacent to some vertex in the set. We show that if a connected graph G has minimum degree two and is not one of seven exceptional graphs, then γ( G )γ 2/5| V |. We also characterize those connected graphs with γ( G )γ 2/5| V |.