Let G be a graph of order n. A classical upper bound for the domination number of a graph G having no isolated vertices is \(\lfloor \frac{n}{2}\rfloor \) . However, for several families of graphs, we have \(\gamma (G) \le \lfloor \sqrt{n}\rfloor \) which gives a substantially improved upper bound. In this paper, we give a condition necessary for a graph G to have \(\gamma (G) \le \lfloor \sqrt{n}\rfloor \) , and some conditions sufficient for a graph G to have \(\gamma (G) \le \lfloor \sqrt{n}\rfloor \) . We also present a characterization of all connected graphs G of order n with \(\gamma (G) = \lfloor \sqrt{n}\rfloor \) . Further, we prove that for a graph G not satisfying \(\textrm{rad}(G)=\textrm{diam}(G)=\textrm{rad}(\overline{G})=\textrm{diam}(\overline{G})=2\) , deciding whether \(\gamma (G) \le \lfloor \sqrt{n}\rfloor \) or \(\gamma (\overline{G}) \le \lfloor \sqrt{n}\rfloor \) can be done in polynomial time. We conjecture that this decision problem can be solved in polynomial time for any graph G.
