Tight upper bounds for the domination numbers of graphs with given order and minimum degree. II (Q1589861)

A dominating set in a graph \(G\) is a subset \(S\) of its vertex set \(V(G)\) such that each vertex of \(G\) either is in \(S\), or is adjacent to a vertex of \(S\). The minimum number of vertices of a dominating set in \(G\) is the domination number \(\gamma(G)\) of \(G\). In the paper \(\gamma(n,\delta)\) denotes the largest possible domination number of a graph with \(n\) vertices and with the minimum degree \(\delta\). Further, \(\delta_k(n)= \max(\delta\mid \gamma(n,\delta)\geq k)\) for \(k\geq 1\). Bounds for \(\delta_k(n)\) are found; they hold for sufficiently large \(n\). The upper bound is in terms of \(n\) and \(k\), the lower bound depends moreover on some constant \(c_k\) whose existence is asserted.