Tight upper bounds for the domination numbers of graphs with given order and minimum degree
Summary: Let \(\gamma(n,\delta)\) denote the maximum possible domination number of a graph with \(n\) vertices and minimum degree \(\delta\). Using known results we determine \(\gamma(n,\delta)\) for \(\delta=0, 1, 2, 3\), \(n \geq \delta + 1\) and for all \(n\), \(\delta\) where \(\delta = n-k\) and \(n\) is sufficiently large relative to \(k\). We also obtain \(\gamma(n,\delta)\) for all remaining values of \((n,\delta)\) when \(n \leq 14\) and all but 6 values of \((n,\delta)\) when \(n = 15\) or 16.
scientific article; zbMATH DE number 1118010