turkmath.org

We aim to give a brief overview of domination in simle graphs. A set $D$ of vertices is dominating in a graph $G$ if every vertex of $G\backslash D$ is adjacent to a vertex in $D$. An arbitrary set $A$ of vertices in a graph $G$ dominates itself and the vertices which have neighbors in $A$. The domination number, $\gamma(G)$, of a graph $G$ is the minimum size of a dominating set in $G$. We will examine some fundamental results in the subject of domination, especially Reed’s where he proved that the domination number, $\gamma(G)$, of every $n$-vertex graph $G$ with minimum degree at least 3 is at most $3n/8$ and conjectured that $\gamma(H ) \leq \lceil n/3\rceil$ for every connected 3-regular (cubic) $n$-vertex graph $H$ . We will show that the conjecture is false and that the first bound could be improved.