2024/01/05 by Subramanian Arumugam, Arumugam, Subramanian, S. M. Hegde +3
Computer Science · #Advanced Graph Theory Research #Cooperative Communication and Network Coding
paper · pdf · doi:10.48550/arxiv.2401.02765
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(n)/(2)\rfloor. However, for several families of graphs, we have γ(G) ≤ \lfloor√(n)\rfloor which gives a substantially improved upper bound. In this paper, we give a condition necessary for a graph G to have γ(G) ≤ \lfloor√(n)\rfloor, and some conditions sufficient for a graph G to have γ(G) ≤ \lfloor√(n)\rfloor. We also present a characterization of all connected graphs G of order n with γ(G) = \lfloor√(n)\rfloor. Further, we prove that for a graph G not satisfying rad(G)=diam(G)=rad(G)=diam(G)=2, deciding whether γ(G) ≤ \lfloor√(n)\rfloor or γ(G) ≤ \lfloor√(n)\rfloor can be done in polynomial time. We conjecture that this decision problem can be solved in polynomial time for any graph G.