An improved upper bound for the domination number of a graph

Abstract

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 ?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.