\magnification=1200
\hsize=4in
\nopagenumbers
\noindent
%
%
{\bf W. Edwin Clark, Larry A. Dunning, Stephen Suen}
%
%
\medskip
\noindent
%
%
{\bf Tight Upper Bounds for the Domination Numbers of\hfil\break
Graphs with Given Order and Minimum Degree, II}
%
%
\vskip 5mm
\noindent
%
%
%
%
Let $\gamma (n,\delta)$ denote the largest
possible domination number for a graph of order $n$ and minimum degree
$\delta$. This paper is concerned with the behavior of the right side
of the sequence
$$\gamma (n,0) \ge \gamma (n,1) \ge \cdots \ge \gamma (n,n-1) = 1.
$$
We set
$ \delta _k(n) = \max \{ \delta \, \vert \, \gamma (n,\delta) \ge k \}$, $k
\ge 1.$ Our main result is that for any fixed $k \ge 2$ there is a
constant $c_k$ such that for sufficiently large
$n$,
$$ n-c_kn^{(k-1)/k} \le \delta _{k+1}(n) \le n - n^{(k-1)/k}.
$$ The lower bound is obtained by use of circulant graphs. We also
show that for $n$ sufficiently large relative to $k$, $\gamma (n,\delta _k(n)) =
k$. The case
$k=3$ is examined in further detail. The existence of circulant
graphs with domination number greater than 2 is related to a kind of
difference set in ${\bf Z}_n$.
\bye