Arumugam, S.Hegde, S.M.Kulamarva, S.2026-02-032025Proceedings of the Indian Academy of Sciences: Mathematical Sciences, 2025, 135, 2, pp. -2534142https://doi.org/10.1007/s12044-025-00850-5https://idr.nitk.ac.in/handle/123456789/19921Let G be a graph of order n. A classical upper bound for the domination number of a graph G having no isolated vertices is ?n2?. However, for several families of graphs, we have ?(G)??n? which gives a substantially improved upper bound. In this paper, we give a condition necessary for a graph G to have ?(G)??n?, and some conditions sufficient for a graph G to have ?(G)??n?. We also present a characterization of all connected graphs G of order n with ?(G)=?n?. Further, we prove that for a graph G not satisfying rad(G)=diam(G)=rad(G¯)=diam(G¯)=2, deciding whether ?(G)??n? or ?(G¯)??n? can be done in polynomial time. We conjecture that this decision problem can be solved in polynomial time for any graph G. © Indian Academy of Sciences 2025.AnonymityGraphic methodsNumber theoryUndirected graphsBound on dominationConditionConnected graphDomination in graphsDomination numberGraph GIsolated verticesPolynomial-timePrivate neighborUpper BoundPolynomial approximation