\input amstex \documentstyle{amsppt} \magnification = 1200 %\input amsfonts \loadeusb \define\F{\eusb{F}} \define\g{\gamma} \define\ZZ{[p]} \define\dd{\delta} \define\ndd{(n,\dd)} %Definition of Table See Page 150 of Tex by Example by Arvind Borde \newdimen\tempdim \newdimen\othick \othick=.4pt \newdimen\ithick \ithick=.4pt \newdimen\spacing \spacing=9pt \newdimen\abovehr \abovehr=6pt \newdimen\belowhr \belowhr=8pt \newdimen\nexttovr \nexttovr=2pt \def\r{\hfil&\omit\vrsp\vrule width\othick\cr&} \def\rr{\hfil\down{\abovehr}&\omit\vrsp\vrule width\othick\cr \noalign{\hrule height\ithick}\up{\belowhr}&} \def\up#1{\tempdim=#1\advance\tempdim by1ex \vrule height\tempdim width0pt depth0pt} \def\down#1{\vrule height0pt depth#1 width0pt} \def\large#1#2{\setbox0=\vtop{\hsize#1 \lineskiplimit=0pt \lineskip=1pt \baselineskip\spacing \advance\baselineskip by 3pt \noindent #2}\tempdim=\dp0\advance\tempdim by\abovehr\box0\down{\tempdim}} \def\dig{{\hphantom0}} \def\hgap#1{\hskip-\nexttovr\hskip#1\hskip-\nexttovr\relax} \def\vrsp{\hskip\nexttovr\relax} \def\toprule#1{\def\startrule{\hrule height#1\relax}} \toprule{\othick} \def\nstrut{\vrule height\spacing depth3.5pt width0pt} \def\exclaim{\char`\!} \def\preamble#1{\def\startup{#1}} \preamble{&##} {\catcode`\!=\active \gdef!{\hfil\vrule width0pt\vrsp\vrule width\ithick\relax\vrsp&}} \def\table#1{\vbox\bgroup \setbox0=\hbox{#1} \vbox\bgroup\offinterlineskip \catcode`\!=\active \halign\bgroup##\vrule width\othick\vrsp&\span\startup\nstrut\cr \noalign{\medskip} \noalign{\startrule}\up{\belowhr}&} \def\caption #1{\down{\abovehr}&\omit\vrsp\vrule width\othick\cr \noalign{\hrule height\othick}\egroup\egroup \setbox1=\lastbox \tempdim=\wd1 \hbox to\tempdim{\hfil \box0 \hfil} \box1 \smallskip \hbox to\tempdim{\advance\tempdim by-20pt\hfil\vbox{\hsize\tempdim \noindent #1}\hfil}\egroup} %End of Table Definitions \font\smcp=cmcsc8 \footline={\hfil} \headline={\ifnum\pageno>1 {\smcp the electronic journal of combinatorics 4 (1997), \#R26 \hfil \folio}\else \hfil \fi} \topmatter \title Tight upper bounds for the domination numbers of graphs with given order and minimum degree \endtitle \author W. Edwin Clark \\ University of South Florida \\ Tampa, FL 33620-5700 \\ {\rm eclark\@math.usf.edu} \\ and \\ Larry A. Dunning \\ Bowling Green State University \\ Bowling Green, OH 43403-0214 \\ {\rm dunning\@cs.bgsu.edu} \endauthor %\address \rm Department of Mathematics, % University of South Florida, Tampa, %FL 33620-5700, USA %\endaddress \email eclark\@math.usf.edu \quad dunning\@cs.bgsu.edu \endemail \date Submitted: June 2, 1997; Accepted: October 27, 1997\enddate \abstract 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 \ge \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 \le 14$ and all but 6 values of $(n,\delta)$ when $n = 15$ or 16. \endabstract \keywords graph, domination number, upper bounds, minimum degree \endkeywords \subjclass 05C35 \endsubjclass \endtopmatter \document \normalbaselineskip 20pt \normalbaselines \head 1. Introduction \endhead We denote the domination number of a graph $G$ by $\g(G)$. By an $\ndd$-graph we mean a graph with $n$ vertices and minimum degree $\dd$. Let $\g\ndd$ be the maximum of $\g(G)$ where $G$ is an $\ndd$-graph. Using known results \cite{3,7,8,9} one easily finds the exact values of $\g\ndd$ when $\dd = 0,1,2,3$. It is also fairly easy to obtain $\g\ndd$ when $\dd = n-k$ for $n$ sufficiently large relative to $k$. By various methods we also find $\g(n,\dd)$ for all remaining values of $(n,\dd)$ when $ n \le 14$ and all but 6 values of $(n,\delta)$ when $n=15$ and 16. Many values can be established using the upper bounds in \cite{2} together with examples found by computer search or {\it ad hoc} techniques. In a number of cases we have used Brendan McKay's program makeg \cite{6} to generate all nonisomorphic $(n,\dd)$-graphs while checking the domination numbers using a simple recursive, depth-first search. Our results give support to the the natural conjecture that $\g\ndd$ is attained by an $\ndd$-graph with the minimum number of edges, that is, by a regular graph if $n\dd$ is even or by a graph with degree sequence $(\dd+1, \dd,\dd, \dots, \dd) $ if $n\dd$ is odd. We are able to verify the conjecture for all the cases mentioned above where we are able to determine $\g\ndd$ and in at least one case where we are not (see Proposition 4.11). However, see Section 5 for some evidence in oppostion to the conjecture. To simplify discussion we say that a graph is {\it almost $\dd$-regular} if its degree sequence has the form $(\dd+1, \dd,\dd, \dots, \dd) $ and we define $\g_r\ndd$ to be the maximum of $\g(G)$ where $G$ is an $\ndd$-graph which is regular if $n\dd$ is even and almost regular if $n\dd$ is odd. In this notation the above mentioned conjecture becomes $\g\ndd = \g_r\ndd$ for all $n$ and $\dd$. We use the following standard notation. Let $G=(V,E)$ be a graph with vertex set $V$ and edge set $E$. We write $ x \sim y$ to indicate that the vertices $x$ and $y$ are adjacent. For $v \in V$ the open neighborhood $N(v)$ is the set of all vertices adjacent to $v$ and the closed neighborhood of $v$ is the set $N[v] = N(v) \cup \{ v \}$. $S \subseteq V$ is a dominating set for $G$ if $ \bigcup_{x \in S} N[x] = V. $ The domination number, $\gamma(G)$, is the cardinality of a smallest dominating set for $G$. If $x \sim y$ or $x = y$ we say that $x$ covers $y$. If $A \subseteq V$ then we let $\langle A \rangle$ denote the subgraph of $G$ induced by $A$. Table 1 contains the value of $\gamma(n,\delta)$ for $n \le 16$, $ 0 \le \delta \le n-1$ if the value is known, otherwise upper and lower bounds for $\gamma(n,\delta)$. We establish these values in Sections 2, 3 and 4. \newpage \eightpoint $$ \table{ Table 1. Values of $\gamma(n,\delta)$ for $n \le 16$, $ 0 \le \delta \le n-1$.} \text{$n \diagdown \delta$}! 0!1 ! 2 ! 3 ! 4 ! 5 ! 6 ! 7 ! 8 ! 9 ! 10 ! 11 ! 12 ! 13 ! 14 !15 \rr 1 !1 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! \rr 2 !2 ! 1 \; \; ! ! ! ! ! ! ! ! ! ! ! ! ! ! \rr 3 !3 ! 1 ! 1 \; ! ! ! ! ! ! ! ! ! ! ! ! ! \rr 4 !4 ! 2 ! 2 ! 1 \; \; ! ! ! ! ! ! ! ! ! ! ! ! \rr 5 !5 ! 2 ! 2 \; \; ! 1 ! 1 ! ! ! ! ! ! ! ! ! ! ! \rr 6 !6 ! 3 ! 2 ! 2 ! 2 ! 1 ! ! ! ! ! ! ! ! ! ! \rr 7 !7 ! 3 ! 3 ! 2 ! 2 ! 1 ! 1 ! ! ! ! ! ! ! ! ! \rr 8 !8 ! 4 ! 4 ! 3 ! 2 ! 2 ! 2 ! 1 ! ! ! ! ! ! ! ! \rr 9!9 ! 4 ! 4 ! 3 ! 3 ! 2 ! 2 ! 1 ! 1 ! ! ! ! ! ! ! \rr 10 !10 ! 5 ! 4 ! 3 ! 3 ! 2 ! 2 ! 2 ! 2 ! 1 ! ! ! ! ! ! \rr 11 !11 ! 5 ! 5 ! 4 ! 3 ! 3 ! 3 ! 2 ! 2 ! 1 ! 1 ! ! ! ! ! \rr 12 !12 ! 6 ! 6 ! 4 ! 4 ! 3 ! 3 ! 2 ! 2 ! 2 ! 2 ! 1 ! ! ! ! \rr 13 !13 ! 6 ! 6 ! 4 ! 4 ! 3 ! 3 ! 3 ! 2 ! 2 ! 2 ! 1 ! 1 ! ! ! \rr 14 !14 ! 7 ! 6 ! 5 ! 4 ! 4 ! 3 ! 3 ! 3 ! 2 ! 2 ! 2 ! 2 ! 1 ! ! \rr 15 !15 ! 7 ! 7 ! 5 ! 5 ! 4 ! \text{3-4} ! 3 ! 3 ! \text{2-3} ! 2 ! 2 ! 2 ! 1 ! 1 ! \rr 16 !16 ! 8 ! 8 ! 6 ! 5 \; ! \text{4-5} ! 4 ! \text{3-4} ! 3 \; ! \text{2-3} ! \text{2-3} ! 2 ! 2 ! 2 ! 2 ! 1 \caption{\;} $$ \tenpoint \normalbaselineskip 20pt \normalbaselines \head 2. The cases $\dd = 0, 1, 2, 3.$ \endhead \proclaim{Lemma 2.1} If $n \ge m > \dd \ge 1$ then $$ \g\ndd + \g(m,\dd) \le \g(n+m, \dd) \tag2.1 $$ and if $n\dd$ or $m \dd$ is even $$ \g_r\ndd + \g_r(m,\dd) \le \g_r(n+m, \dd). \tag2.2 $$ \endproclaim \demo{Proof} The lemma is immediate from the fact that if $G$ is an $\ndd$-graph and $H$ is an $(m,\dd)$-graph then the disjoint union $G \cup H$ is an $(n + m , \dd)$-graph with domination number $\g(G \cup H) = \g(G) + \g(H)$. (2.2) follows from the fact that if $G$ is regular and $H$ is regular (resp., almost regular) then $G \cup H$ is regular (resp., almost regular). \qed \enddemo \proclaim{Corollary 2.2} For every positive integer $k$ we have $$ k \g(n,\dd) \le \g(kn,\dd) \tag2.2 $$ and provided that $n \dd$ is even, $$ k \g_r(n,\dd) \le \g_r(kn,\dd).\qed \tag2.3 $$ \endproclaim We will need the following two theorems: \proclaim{Ore's Theorem \cite{7}} If $G$ is an $(n,\dd)$-graph with $\dd \ge 1$ then $\g(G) \le n/2$. \qed \endproclaim \proclaim{Reed's Theorem \cite{9}} If $G$ is an $(n,\dd)$-graph with $\dd \ge 3$ then $\g(G) \le 3n/8$. \qed \endproclaim \proclaim{Proposition 2.3} For $n \ge 1$ $$\g(n,0) = \g_r(n,0) = n$$ and for $n \ge 2$ $$\g(n,1) = \g_r(n,1) = \lfloor n/2 \rfloor. \qed $$ \endproclaim \demo{Proof} The case $\dd = 0$ is trivial and the case $\dd = 1$ is immediate from Ore's Theorem. \qed \enddemo \proclaim{Proposition 2.4} For $n \ge 3$, $$ \g(n,2) = \g_r(n,2) = \cases \lfloor n/2 \rfloor - 1, &\text{if $n \equiv 2 \pmod 4$}\\ \lfloor n/2 \rfloor, &\text{otherwise.} \endcases $$ \endproclaim \demo{Proof} From Ore's Theorem we have $\g(n,2) \le \lfloor n/2 \rfloor$. Consider the four cases: \roster \item $ n = 4k$, \quad $k \ge 1$. \item $ n = 4k+1$, \quad $k \ge 1$. \item $ n = 4k+2$, \quad $k \ge 1$. \item $ n = 4k+3$, \quad $k \ge 0$. \endroster In cases (1) and (2) $ \lfloor n/2 \rfloor = 2k$ so in these cases it suffices to exhibit a 2-regular graph $G$ with $ \gamma (G) = 2k $. In case (1) we can take $G$ to be the disjoint union of $k$ 4-cycles. In case (2) we can take $G$ to be the disjoint union of $k-1$ 4-cycles and one 5-cycle. In case (4) we can take $G$ to be the union of $k$ 4-cycles and one 3-cycle. Then $\g(G) = 2k + 1 = \lfloor n/2 \rfloor$. For case (3) we first note that by \cite{8} or \cite{3} if a graph $G$ has no isolated vertices and if $\g(G) = n/2$ then each connected component of $G$ is either a 4-cycle or has a vertex of degree 1. Since we are interested here only in graphs with $\dd = 2$ it follows that such a graph cannot have $\g(G) = n/2$ unless it has order $4k$. So in case (3) we have $\g(n,2) \le n/2 -1$. To see that this upper bound can be attained one must only consider the disjoint union of $k-1$ 4-cycles and one 6-cycle.\qed \enddemo \proclaim{Proposition 2.5} If $n \ge 4$ then $$ \g(n,3) = \g_r(n,3) = \lfloor 3n/8 \rfloor. $$ \endproclaim \demo{Proof} From Reed's Theorem $\g(n,3) \le 3n/8$. Thus it suffices to exhibit for each $n \ge 4$ an $(n,3)$-graph $G_n$ which is 3-regular if $n$ is even and almost regular if $n$ is odd such that $\g(G_n) = \lfloor 3n/8 \rfloor$. We first note that it suffices to find the graphs $G_n$ for $4 \le n \le 11$: For $12 \le n \le 15$ we can take $$ G_{15} = G_8 \cup G_7, \quad G_{14} = G_8 \cup G_6, \quad G_{13} = G_8 \cup G_5, \quad G_{12} = G_8 \cup G_4. $$ If $n \ge 16$ we can write $n = 8k + r$ where $k \ge 1$ and $r \in \{ 8,9,10,11,12,13,14,15 \}$. Then $ \lfloor 3n/8 \rfloor = 3k + \lfloor 3r/8 \rfloor. $ So if we let $G_n$ be the disjoint union of k copies of $G_8$ and one copy of $G_r$ we have $$ \g(G_n) = k\g(G_8) + \g(G_r) = 3k + \lfloor 3r/8 \rfloor = \lfloor 3n/8 \rfloor. $$ Moreover since $G_8$ is 3-regular, $G_n$ will be regular if $r$ is even and almost regular if $r$ is odd. This leaves the cases $4 \le n \le 11$. It is easy to see that we may take $G_4 = K_4$, $G_5 = K_5 - \{ \text{two disjoint edges} \}$, $G_6$ = any regular (6,3)-graph, $G_7$ = any almost regular (7,3)-graph, $G_8$ can be taken to be the 8-cycle with 4 diameters added, and $G_{10} = G_4 \cup G_6$. This leaves only $G_9$ and $G_{11}$. See appendix B for these graphs, namely, the graphs listed there as $G(9,3,3)$ and $G(11,3,4)$. \qed \enddemo \head 3. The cases $\dd = n - k$ for $k$ small. \endhead We first describe an upper bound for $\g(n,\dd)$ which is a variation of Theorem 2 in \cite{2}. This result plays a major role in almost all of our arguments. \bigpagebreak \proclaim{Proposition 3.1} Let $G$ be an $(n,\dd)$-graph containing a set $S$ of $s$ vertices which covers at least $\lambda$ vertices. Define the sequence $g_s, g_{s+1}, \cdots, g_{n-\delta}$ by $g_s = n- \lambda$ and $$ g_{t+1} = \left \lfloor g_{t} \left(1 - \frac{\delta + 1}{n-t} \right ) \right \rfloor = g_{t} -\left \lceil \frac {g_{t}(\dd +1)}{n-t} \right \rceil , \quad t \ge s. $$ Then for any $t$, $s \le t \le n-\delta$, there is a set of $t$ vertices that covers at least $n - g_t$ vertices. Thus if we set $$ M(n,\dd,\lambda, s) = min \{ \ t \ | \ g_t = 0 \ \} $$ we have $$ \g(G) \le M(n,\dd,\lambda,s). $$ In particular, $$\g(n,\dd) \le M(n,\dd,\dd+1,1)$$ and if $n\dd$ is odd, $$\g(n,\dd) \le M(n,\dd,\dd +2,1).$$ \endproclaim \demo{Proof} Starting with the set $S= \{v_1, v_2, \cdots, v_s\}$ we select successively and greedily the elements $v_{s+1},v_{s+2}, \cdots, v_t$. Let $u_t$, $t \ge s$, be the number of vertices left uncovered after the vertices $v_1, v_2, \cdots, v_t$ have been chosen. It clearly suffices to prove that $u_t \le g_t$ for $t \ge s$. We prove this by induction on $t$. If $t = s$ then since $S$ covers at least $\lambda$ vertices $u_s \le n-\lambda = g_s$. Assume that $u_t \le g_t$ holds for some $t \ge s$. Let $$ U_t=\{ x_1, x_2, \cdots, x_{u_t} \} $$ be the set of vertices not covered by $v_1, v_2, \cdots, v_t$ and let $$ V - \{v_1, \cdots, v_t \} =\{y_1, y_2, \cdots, y_{n-t} \}. $$ Now define the $u_t \times(n-t)$ matrix $M$ whose $(i,j)$-th entry is given by $$ M_{i,j} = \cases 1, &\text{if $x_i$ covers $y_j$} \\ 0, &\text{otherwise.} \endcases $$ Since none of the $x_i$'s are covered by any of the vertices $v_1, v_2, \cdots, v_t$ chosen so far and $\deg (x_i) \ge \dd $ there are at least $\dd + 1$ ones in each row of $M$. This gives at least $u_t(\dd + 1)$ ones in the entire matrix. Since there are $n-t$ columns at least one column must contain at least $$N=\left \lceil \frac {u_t(\dd +1)}{n-t} \right \rceil$$ ones. Say it is the $j$-th column. This means that $y_j$ covers at least $N$ of the $x_i$'s. So if we select $v_{t+1}$ to cover the maximum number $N_{max}$ of the $x_i$'s we have $N \le N_{max}$ and the number of vertices now left uncovered is $$ \align u_{t+1} &=u_t - N_{max} \\ &\le u_t - N \\ &=u_t -\left \lceil \frac {u_t(\dd +1)}{n-t} \right \rceil \\ &= u_t +\left \lfloor - \frac {u_t(\dd +1)}{n-t} \right \rfloor \\ &= \left \lfloor u_t \left(1- \frac{\dd +1}{n-t}\right) \right \rfloor \\ &\le \left \lfloor g_t \left(1- \frac{\dd +1}{n-t}\right) \right \rfloor \\ &= g_{t+1}. \endalign $$ This completes the proof. \qed \enddemo \proclaim{Proposition 3.2} \roster \item $\g(n,n-1) = \g_r(n,n-1) = 1$ for any $n \ge 1$. \item $\g(n,n-2) = \g_r(n,n-2) = 1$ for odd $n \ge 2$. \item $\g(n,n-2) = \g_r(n,n-2) = 2$ for even $n \ge 2$. \endroster \endproclaim \demo{Proof} For each of the cases (1) and (2) there is a vertex of degree $n-1$ which by itself forms a dominating set. For case (3) any regular graph with $\dd = n-2$ clearly has domination number 2.\qed \enddemo \proclaim{Lemma 3.3} Let $n \ge 2$ and let $G$ be an $(n,\dd)$-graph with a vertex of degree $\Delta$. Then $\g(G) \le 2$ if $$ (n - \Delta -1)(n- \dd -2) < n-1 \tag3.1 $$. \endproclaim \demo{Proof} By Proposition 3.1 $\g(G) \le M(n,\dd,\Delta+1,1)$ and $M(n,\dd,\Delta+1,1) = 2$ if and only if $g_2 =0$. Now $g_1 = n - \Delta -1$ and $$ g_{2} = \left \lfloor g_1 \left(1 - \frac{\delta + 1}{n-1} \right ) \right \rfloor. $$ So $g_2 = 0$ if and only if $$ (n - \Delta -1) \left(1 - \frac{\delta + 1}{n-1} \right ) < 1 $$ which is equivalent to (3.1). \qed \enddemo \proclaim{Proposition 3.4} Let $3 \le k \le n-1$. \roster \item If $(k-1)(k-2) + 1 < n$ then $$\g(n,n-k)= \g_r(n,n-k)= 2.$$ \item If $n$ is odd, $k$ is even and $ (k-2)^2 + 1 < n$ then $$\g(n,n-k)= \g_r(n,n-k) = 2$$ \endroster \endproclaim \demo{Proof} If $k \ge 3$ then $\g(n,n-k) \neq 1$ since a regular or almost regular graph with $\dd = n-k$ has vertices of degree at most $n-k+1$ so a single vertex cannot cover all $n$ vertices. Hence whenever $\g(n,n-k) \le 2$ we have $\g(n,n-k)=\g_r(n,n-k) =2$. By Lemma 3.3 $\g(n,n-k) \le 2$ if $(k-1)(k-2) + 1 < n$. This proves (1). To prove (2) we observe that if $n$ is odd and $k$ is even then $\dd = n-k$ is odd and so any $(n,\dd)$-graph has a vertex of degree at least $\dd + 1$ so we can take $\Delta = \dd + 1 = n - k + 1$ in (3.1) and we obtain (2). \qed \enddemo \proclaim{Corollary 3.5} \roster \item $\g(n,n-3)= \g_r(n,n-3)= 2$ if $n > 3$. \item $\g(n,n-4)= \g_r(n,n-4)= 2$ if $n \ge 7$. \item $\g(n,n-5)= \g_r(n,n-5)= 2$ if $n > 13$. \item $\g(n,n-6)= \g_r(n,n-6)= 2$ if $n \ge 21$ or $n=19$. \item $\g(n,n-7)= \g_r(n,n-7)= 2$ if $n > 31$.\qed \endroster \endproclaim \head 4. $\g(n,\dd)$ for $n \le 16$. \endhead In Table 1 we give a list of values (or bounds) for $\g(n,\dd)$ when $n \le 16$. In this section we justify the entries of this table. See Table 3 in Appendix A for a summary of how entries in Table 1 are obtained. From Propositions 2.3, 2.4, 2.5, 3.2 and Corollary 3.5 we obtain immediately the exact values of $\g(n,\dd)$ for all values of $n$ and $\dd$ for $n \le 16$ except for the following 33 cases: \roster \item $n = 9$, $\dd = 4$. \item $n = 10$, $\dd = 4, 5$. \item $n = 11$, $\dd = 4, 5, 6$. \item $n = 12$, $\dd = 4, 5, 6, 7$. \item $n = 13$, $\dd = 4, 5, 6, 7, 8$. \item $n = 14$, $\dd = 4, 5, 6, 7, 8$. \item $n = 15$, $\dd = 4, 5, 6, 7, 8, 9$. \item $n = 16$, $\dd = 4,5,6,7,8,9,10.$ \endroster The number of unknown $\g(n,\dd)$ can be reduced further by using the upper bounds given in Proposition 3.1 (taking $s = 1$) and Reed's Theorem. See Table 2 for upper bounds computed using Proposition 3.1. Let $Ub(n,\delta)$ denote $M(n,\delta,\delta+1,1)$ if $n\delta$ is even or $M(n,\delta,\delta+2,1)$ if $n\delta$ is odd. If the entry in the $(n,\delta)$-th cell of Table 2 is a single number then that number is $Ub(n,\delta)$ and is, in fact, equal to $\gamma(n,\delta)$. So only an example suffices to establish $\gamma(n,\delta)$ in these cases. Tight lower bounds are given by the graphs $G(n,\dd, \g)$ in Appendix B. Each graph $G(n,\dd,\g)$ listed in Appendix B is an $(n,\dd)$-graph with domination number $\g$. These graphs are regular if $n\delta$ is even and almost regular otherwise. After applying these results we have only the following 15 remaining cases: \roster \item $n = 10$, $\dd = 5$. \item $n = 11$, $\dd = 4$. \item $n = 12$, $\dd = 7$. \item $n = 13$, $\dd = 5, 8$. \item $n = 14$, $\dd = 4, 6$. \item $n = 15$, $\dd = 5, 6,9$. \item $n = 16$, $\dd = 4,5,7,9,10.$ \endroster As indicated in Table 3 (in Appendix A) all but 6 of these cases are settled by one of the following propositions and/or the use of an exhaustive search using Brendan McKay's program makeg augmented with a subroutine to compute domination numbers. For example we use Propostion 4.1 below to reduce the determination of $\g(10,5)$ to the determination of $\g_r(10,5)$. Then we search through all 5-regular graphs of order 10 to find that $\g_r(10,5) = 2$. \newpage \eightpoint $$ \table {Table 2. Upper bounds given by Proposition 3.1 for $5 \le n \le 16$} \text{$n \diagdown \delta$} !\hfil 4!\hfil 5!\hfil 6!\hfil 7!\hfil 8!\hfil 9!\hfil 10!\hfil 11!\hfil 12!\hfil 13!\hfil 14!\hfil 15 \rr \hfil 5!\hfil 1!\hfil !\hfil !\hfil !\hfil !\hfil !\hfil !\hfil !\hfil !\hfil !\hfil !\hfil \rr \hfil 6!\hfil 2!\hfil 1!\hfil !\hfil !\hfil !\hfil !\hfil !\hfil !\hfil !\hfil !\hfil !\hfil \rr \hfil 7!\hfil 2!\hfil 1!\hfil 1!\hfil !\hfil !\hfil !\hfil !\hfil !\hfil !\hfil !\hfil !\hfil \rr \hfil 8!\hfil 2!\hfil 2!\hfil 2!\hfil 1!\hfil !\hfil !\hfil !\hfil !\hfil !\hfil !\hfil !\hfil \rr \hfil 9!\hfil 3!\hfil 2!\hfil 2!\hfil 1!\hfil 1!\hfil !\hfil !\hfil !\hfil !\hfil !\hfil !\hfil \rr \hfil 10!\hfil 3!\hfil \text{ 2,3,7} !\hfil 2!\hfil 2!\hfil 2!\hfil 1!\hfil !\hfil !\hfil !\hfil !\hfil !\hfil \rr \hfil 11!\hfil \text{3,4,5} !\hfil 3!\hfil 3!\hfil 2!\hfil 2!\hfil 1!\hfil 1!\hfil !\hfil !\hfil !\hfil !\hfil \rr \hfil 12!\hfil 4!\hfil 3!\hfil 3!\hfil \text{ 2,3,8} !\hfil 2!\hfil 2!\hfil 2!\hfil 1!\hfil !\hfil !\hfil !\hfil \rr \hfil 13!\hfil \text{ 4,5,6} !\hfil \text{ 3,4,7} !\hfil 3!\hfil 3!\hfil \text{ 2,3,9} !\hfil 2!\hfil 2!\hfil 1!\hfil 1!\hfil !\hfil !\hfil \rr \hfil 14!\hfil \text{ 4,5,7} !\hfil 4!\hfil \text{ 3,4,7} !\hfil 3!\hfil 3!\hfil 2!\hfil 2!\hfil 2!\hfil 2!\hfil 1!\hfil !\hfil \rr \hfil 15!\hfil 5!\hfil \text{ 4,5,8} !\hfil \text{ 3-4*} !\hfil 3!\hfil 3 !\hfil \text{ 2-3*} !\hfil 2!\hfil 2!\hfil 2!\hfil 1!\hfil 1!\hfil \rr \hfil 16!\hfil \text{ 5,6,5} !\hfil \text{ 4-5*} !\hfil 4!\hfil \text{ 3-4*} !\hfil 3!\hfil \text{ 2-3*} !\hfil \text{ 2-3*} !\hfil 2!\hfil 2!\hfil 2!\hfil 2!\hfil 1 \caption{An entry of the form $a,a+1,\lambda$ indicates that $\gamma(n,\delta)=a$ and $Ub(n,\delta) = a+1$. $\lambda$ is the least postive integer for which $M(n,\delta,\lambda+1,1) = a$. Thus in these cases one obtains a tight upper bound by assuming the existence of a vertex of degree $\lambda$. In cells containing $x$-$y*$ the value of $\gamma(n,\delta)$ is unknown, but our current best upper bound is given by $Ub(n,\delta)=y$ and $x$ is our current best lower bound. } $$ \tenpoint \normalbaselineskip 20pt \normalbaselines Several times below we need the following trivial result. \proclaim{Lemma 4.0} Let $\F$ be a set of two element subsets of a four element set $X$. If the following two conditions hold \roster \item $A \cap B \ne \emptyset$ for all $A, B \in \F$, and \item $\bigcup_{A \in \F } A = X$, \endroster then $\bigcap_{A \in \F} A \ne \emptyset$ \qed \endproclaim \proclaim{Proposition 4.1} $2 \le \g_r(10,5) = \g(10,5) \le 3.$ \endproclaim \demo{Proof} From Proposition 3.1 (see Table 2) we obtain $\g(10,5) \le 3$ so it suffices to show that if $G=(V,E)$ is a (10,5)-graph that is not regular then $\g(G) \le 2$. If $\Delta \ge 7$ then by Lemma 3.3 (or Table 2), $\g(G) \le 2$. So suppose that $\Delta = 6$. Let x be a vertex of degree 6. Then $V$ is the disjoint union of $N[x]$, the closed neighborhood of x, and the 3-set $A = \{ a, b, c \}$. If the induced graph $H=\langle A \rangle $ has 2 edges then it can be dominated by a single vertex. So we can assume that $H$ has at most one edge. Thus $H$ has at least one isolated vertex, say, c. This means that $c$ is adjacent to at least 5 vertices in the open neighborhood $N(x)$ of $x$ and each of the remaining two vertices $a$ and $b$ are adjacent to at least 4 vertices of $N(x)$. It follows that there is at least one vertex $y$ in $N(x)$ that is adjacent to all three vertices in $A$. Hence $\{ x,y \}$ is a dominating set for $G$. \qed \enddemo \proclaim{Proposition 4.2} $3 \le \g_r(11,4) = \g(11,4) \le 4$ \endproclaim \demo{Proof} By Proposition 3.1 $\g(11,4) \le 4$. By Lemma 2.1 and the above $$ \gamma_r(11,4) \ge \gamma_r(6,4) + \gamma_r(5,4) = 3. $$ So it suffices to show that if $G$ an (11,4) graph that is not regular then $\g(G) \le 3$. But it is immediate from Proposition 3.1 that if $\Delta \ge 5$ then $\g \le 3$. \qed \enddemo \proclaim{Proposition 4.3} $2 \le \g_r(12,7) = \g(12,7) \le 3$ \endproclaim \demo{Proof} Any regular (12,7)-graph has $2 \le \g$. By Proposition 3.1 if $G$ is a (12,7)-graph with $\g(G) \le 3$ and $\Delta \ge 8$, then $\g(G) \le 2$, and the proposition follows. \qed \enddemo \proclaim{Proposition 4.4} $\g_r(13,5) = \g(13,5) = 3.$ \endproclaim \demo{Proof} By Appendix B there is an almost regular (13,5)-graph with domination number 3 so $ 3 \le \g_r(13,5) \le \g(13,5)$. It therefore suffices to show that $\g(13,5) \le 3$. If $G=(V,E)$ is a (13,5)-graph with maximum degree $\Delta \ge 7$ then from Proposition 3.1 we have $\g(G) \le 3$. Now if $\Delta \le 6$ then since $n\dd$ is odd $G$ will always a vertex $x$ of degree 6. Thus $V$ is a disjoint union of the closed neighborhood $N[x]$ of $x$ and a set $A$ of cardinality 6. Consider the $6 \times 12$ matrix $M$ whose rows are indexed by the elements of $A$ and the columns are indexed by the elements of $V - \{ x \}$. If $a \in A$ is adjacent to or equal to $y \in V - \{ x \}$ let $M_{a,y} = 1$. Otherwise, let $M_{a,y} = 0$. Now each row of $M$ has at least 6 ones, so $M$ has in all at least 36 ones. If there is a column with 4 ones this means there is a vertex $y \in V - \{ x \}$ that covers all but two vertices, say, $z,w$ in $A$. If the sets $N[z]$, $N[w]$ are disjoint their union contains all but one vertex $t$. Then $\{z,w,t \}$ is a dominating set and we are done. But if $v \in N[z] \cap N[w]$, then $v$ dominates both $z$ and $w$ so $\{x,y,v \}$ is a dominating set. We are left with the case where each column of $M$ contains at most three ones. This implies that each column contains exactly three ones. Hence each vertex in the subgraph $H = \langle A \rangle$ has degree exactly 2. Hence $H$ is a (6,2)-graph and by Proposition 2.4 can be dominated by two vertices. Hence $G$ can be dominated by $x$ together with these two vertices and we are done. \qed \enddemo \proclaim{Proposition 4.5} $2 \le \gamma_r(13,8) = \gamma(13,8) \le 3$. \endproclaim \demo{Proof} Any regular (13,8)-graph $G$ has domination number at least 2. By Lemma 3.3 if $G$ has a vertex of degree greater than 8 then $\gamma(G) \le 2$. \qed \enddemo \proclaim{Proposition 4.6} $\gamma_r(14,4) = \gamma(14,4) = 4$. \endproclaim \demo{Proof} From Appendix B there is a 4-regular graph of order 14 with domination number 4. This lower bound also follows from Lemma 2.1 and the fact that $\gamma(7,4) = \gamma_r(7,4) = 2$ by Corollary 3.5. Thus it suffices to show that if $G = (V,E)$ is a (14,4)-graph then $\gamma(G) \le 4$. If there is a vertex of degree 7 we obtain $\gamma(G) \le 4$ from Proposition 3.1. Hence we may assume that $\Delta$ is at most 6. We consider two cases: \roster \item There are vertices $a$ and $b$ such that $| N[a] \cup N[b] | \ge 10$. \item For all vertices $a$ and $b$ we have $| N[a] \cup N[b] | \le 9.$ \endroster In case (1) if $| N[a] \cup N[b] | \ge 11$ we get $\gamma(G) \le 4$ immediately from Proposition 3.1 with $s=2$ and $\lambda=11$. Hence can assume that $| N[a] \cup N[b] | = 10$. We let $A$ be the set of 4 vertices not in $N[a] \cup N[b]$ and $H = \langle A \rangle$. Let $$ B =(N[a] \cup N[b])-\{a,b\}. $$ For each vertex $v \in B$ let $A_v$ be the set of vertices in $A$ that are adjacent to $v$. If $|A_v| \ge 3$ for some $v$ then $v$ covers at least three vertices from $A$ and then clearly $\gamma(G) \le 4$. Hence we may assume that $|A_v| \le 2$ for each $v \in B$. Note that the sum of the $|A_v|$'s is the number of edges from $A$ to $B$. If $H$ has 2 edges then $\gamma(H) \le 2$ so $\gamma(G) \le 4$. So we may assume that $H$ has at most one edge. We consider the two subcases: \roster \item "{(1a)}" $H$ has no edges; and \item "{(1b)}" $H$ has exactly one edge. \endroster If (1a) holds then there are at least $4 \cdot 4 = 16$ edges from $A$ to $B$. Thus, the sum of the $|A_v|$'s is at least 16. Since $|A_v| \le 2$ for all $v \in B$ we must have $|A_v| = 2$ for all eight $v$ in $B$. If $A_{v_{1}} \cap A_{v_{2}} = \emptyset$ then $A_{v_{1}} \cup A_{v_{2}} = A$ and so $\{a,b,v_1, v_2 \}$ is a dominating set for $G$. So we can assume that $A_{v_{1}} \cap A_{v_{2}} \ne \emptyset$ for all $v_1$ and $v_2$. The sets $A_v$ must cover $A$ as the vertices of A have degree at least $4$ in $G$. Clearly the hypotheses of Lemma 4.0 hold for $\F = \{ A_v \, | \, v \in B \}$ and hence the $A_v$'s contain a common element. But this common element would be a vertex of degree 8, contrary to the assumption that $\Delta \le 6$. This settles case (1a). Assume that (1b) holds. Let $A = \{x,y,z,w \}$ and assume that $\{z,w \}$ is the single edge in $H$. In this case there are at least 14 edges from $A$ to $B$ and there must be at least 6 of the $A_v$'s that have cardinality 2. If there were more than 6 the argument for case (1a) repeated would show the existence of a vertex of degree greater than 6, a situation already handled. Thus we may assume that there are exactly 6 vertices $v$, in $B$ such that $|A_{v}| = 2$. If for some $i$, $A_{v_i} = \{x,y\}$ then $\{a,b,v_i,z \}$ is a domination set for $G$. We show this must happen. If not, since both $x$ and $y$ have degree at least 4 in $G$ but degree 0 in $H$ we can assume that $A_{v_i}$ contains $x$ for $i = 1,2,3,4$ and that $A_{v_i}$ contains $y$ for $i = 5,6,7,8$. This means that the two $A_v$'s that have one element must contain either an $x$ or a $y$. It follows that there are at least three of the two element $A_v$'s that contain $z$ and at least three, that contain $w$. So it is clear that we cannot avoid having either two $A_v$'s of the form $\{x,z\}$ and $\{y,w\}$ or, of the form $\{x,w\}$ and $\{y,z\}$. But this contradicts our assumption that the two element $A_v$'s are never disjoint. This completes the proof in case (1b) and hence the proof of case (1). Assume that case (2) holds. Note that if $G$ is not regular then it contains a vertex of degree at least 5 and by Proposition 3.1 there will be two vertices that cover at least 10 vertices which puts us back in case (1). Thus we can assume that $G$ is 4-regular. Note that this implies that $N[a] \cap N[b] \ne \emptyset$ for all vertices $a$ and $b$. Hence any two vertices can be covered by a single vertex. Thus if we are able to show that we can cover 12 vertices with 3 vertices we will know that $\gamma(G) \le 4$. By Proposition 3.1 there are two vertices $a$ and $b$ such that $N[a] \cup N[b]=9$. Let $$ B = (N[a] \cup N[b]) - \{ a, b \} $$ and let $$ A= V - (N[a] \cup N[b]). $$ Now again let $H = \langle A \rangle$. If H contains a vertex $x$ of degree 2 we can cover 12 vertices with the $a$, $b$ and $x$ and we are done. So we can assume that $H$ has only vertices of degree 1 and hence $H$ has at most 2 edges. It follows that there must be at least 16 edges with one end in $A$ and the other end in $B$. Since $|A| = 5$ and $|B|=7$ there must be at least one vertex $x \in B$ that is incident with at least 3 vertices in $A$. Then $a$, $b$ and $x$ cover all but 2 vertices in $A$ and as before we are done. \qed \enddemo \proclaim{Lemma 4.7} A graph $G=(V,E)$ with $|V|=7$, $|E|\ge 10$, and $\Delta \le 3$ satisfies $\gamma(G) \le 2$. \endproclaim \demo{Proof} The graph $G=(V,E)$ must have six vertices of degree $3$ and a single vertex of degree $2$. Let $v$ be a vertex of degree $3$ which is adjacent to a vertex of degree 2. Let $A$ denote the set of three vertices not adjacent to $v$. If $\langle A \rangle$ has two or more edges, then clearly $G$ can be dominated by $v$ together with a vertex of degree $2$ taken from $\langle A \rangle$. So we may assume that $\langle A \rangle$ has at most one edge. The sum of the degrees (in $G$) of the vertices of $A$ is 9 since the single vertex of degree 2 is not in $A$. Since $\langle A \rangle$ has at most one edge, there are at least $7=9-2$ edges between $N(v)$ and $A$. Hence at least one vertex, say $x$, in $N(v)$ must be incident with 3 of these edges. It follows that $\{x, v \}$ is a dominating set for $G$.\qed \enddemo The restriction that $\Delta \le 3$ in the preceding lemma is essential. A graph with $\gamma=3$ can be constructed meeting the other hypotheses even if we assume no isolated vertices. Begin with the tetrahedron $K_4$. Add an additional vertex connecting it to any two vertices of the tetrahedron. Finally, add two additional vertices, connecting each to one of the remaining two vertices of the tetrahedron. This graph has $10$ edges and $7$ vertices, but has maximum degree $4$ and minimum degree $1$. The graphs described by the lemma had maximum degree $3$ and minimum degree $2$. There is also a graph with 7 vertices, 10 edges, minimum degree 2, maximum degree 4 with domination number 3. \proclaim{Proposition 4.8} $\gamma_r(14,6) = \gamma(14,6) = 3$. \endproclaim \demo{Proof} By Appendix B there is a regular $(14,6)$-graph whose domination number is $3$. That $\gamma_r(14,6) = \gamma(14,6)$ follows from Proposition 3.1. It remains to prove that $\gamma_r(14,6) \le 3$. Let $G=(V,E)$ be a regular $(14,6)$-graph. Since every closed neighborhood contains 7 vertices, $\gamma(G) = 2$ if there are disjoint closed neighborhoods in $G$. Thus we can assume that any two closed neighborhoods $N[x]$ and $N[y]$ intersect in at least one point. This implies that any two vertices can be covered by a single vertex. So if we can cover 12 vertices with just 2 vertices we will be done. Let $v \in V$ and set $A = V - N[v]$. If $\gamma( \langle A \rangle) \le 2$ we are clearly done. If $\langle A \rangle$ has a vertex of degree at least 4 it covers 5 vertices in addition to the 7 covered by v and we are done. So we can assume that the maximum degree of a vertex in $\langle A \rangle$ is $3$. If there are at least 10 edges in $\langle A \rangle$ we are done by Lemma 4.7. Thus we may assume that $\langle A \rangle$ has at most 9 edges. An endpoint of an edge in $G$ is either in $A$ or $N(v)$. Since $\langle A \rangle$ has at most 9 edges and $G$ is 6-regular there are at least $24=|A| \cdot 6 - 2 \cdot 9$ edges from $A$ to $N(v)$. If some vertex in $N(v)$ covers 5 or more of the vertices in $A$ we are done. Thus each of the 6 vertices in $N(v)$ is incident with at most 4 of the vertices in $A$. This implies that there are exactly $24$ edges between $A$ and $N(v)$ and that each $x \in N(v)$ is incident to $v$ and to exactly four vertices in $A$. It follows that $\langle N(v) \rangle$ is a 1-regular graph. Thus we can assume that { \it for every } vertex $v \in V$ the graph $\langle N(v) \rangle$ is 1-regular. But we shall see that this is impossible: Let $v \in V$ and let $x,y \in N(v)$ be chosen such that $x \sim y$. It is clear that $$N[v] \cap N[x] \cap N[y] = N[v] \cap N[x] = N[v]\cap N[y] = \{v,x,y\}$$ as $x$ and $y$ are adjacent only to each other in $\langle N(v) \rangle$. Also we have $$N[x] \cap N[y] = \{v,x,y\}.$$ For suppose, to the contrary, that $w \in N[x] \cap N[y]$ and $w \notin \{v,x,y\}$. Then $y \in N(x)$ is adjacent to both $v, w \in N(x)$ which contradicts the assumption that $\langle N(x) \rangle$ is 1-regular. But then we have $$ \align |N[v] \cup N[x] \cup N[y]| &= \\ & \ \ |N[v]|+|N[x]|+|N[y]| \\ & \ - |N[v] \cap N[x]| - |N[v] \cap N[y]| - |N[x] \cap N[y]| \\ & \ + |N[v] \cap N[x] \cap N[y]| \\ &= 7+7+7-3-3-3+3 = 15, \endalign $$ which cannot be since there are only 14 vertices in $G$. \qed \enddemo \proclaim{Proposition 4.9} $\gamma(15,5)=\gamma_r(15,5) = 4.$ \endproclaim \demo{Proof} The almost regular graph $G(15,5,4)$ given in Appendix B has domination number 4, so it suffices to prove that $\gamma(15,5) \le 4.$ Let $G=(V,E)$ be a (15,5)-graph. If $G$ has a vertex of at least degree at least 8 then $\gamma(G) \le 4$ by Proposition 3.1. Since the minimum degree and the order are odd, there must be a vertex, say, $x$ of degree at least 6. Again by Proposition 3.1 there is a vertex $y$ such that $|N[x] \cup N[y]| \ge 11$. If $|N[x] \cup N[y]| \ge 12$ then Proposition 3.1 shows that $\gamma(G) \le 4$. So we can assume that $|N[x] \cup N[y]| = 11$. Let $$ A= \{a,b,c,d\} = V-(N[x] \cup N[y]), $$ $$ B = (N[x] \cup N[y]) - \{x,y\}, $$ and $ H=\langle A \rangle.$ If $H$ has domination number 1 or 2 we are done. So we may assume that $H$ has at most one edge. It follows that there are at least $4 \cdot 5 - 2 =18$ edges with one end in $B$ and the other end in $A$. For each vertex $v$ in $B$ let $A_v$ denote the vertices in $A$ adjacent to $v$. If any $A_v$ has three or more elements we are clearly done. So we may assume that each $A_v$ has at most 2 elements. But since there are at least 18 edges joining $A$ to $B$ we must have $|A_v|=2$ for each $v \in B$. Now if $A_{v_1} \cap A_{v_2}=\emptyset$ then $A_{v_1} \cup A_{v_2}= A$ and so $\{x,y,v_1,v_2\}$ is a dominating set for $G$. Thus we may assume that $A_{v_1} \cap A_{v_2} \ne \emptyset$ for all $v_1$ and $v_2$ in $B$. By Lemma 4.0 the $A_v$'s have an element in common. But the common element would have degree at least 9, a case we already covered. This completes the proof.\qed \enddemo \proclaim{Proposition 4.10} $\gamma_r(16,4) = \gamma(16,4) = 5$. \endproclaim \demo{Proof} Since $\gamma_r(6,4) = 2$ and $\gamma_r(10,4)=3$ there is, by Lemma 2.1, a regular graph whose domination number is $5$. It remains to prove that $\gamma(16,4) \le 5$. Given a $(16,4)$ graph, we may assume that any two closed neighborhoods $N[x]$ and $N[y]$ intersect in at least one point. If they were disjoint, then Proposition 3.1 would apply with $|S| = 2$ and $\lambda = 10$ vertices covered. Applying Proposition 3.1 directly with $|S|=1$ and $\lambda = 5$ we obtain $g_4=2$. Thus, 4 vertices cover all but (at most) 2 vertices. The closed neighborhoods of the remaining two vertices are not disjoint and hence they can be covered by a single vertex yielding a dominating set of at most 5 vertices. \qed \enddemo \proclaim{Proposition 4.11} $4 \le \gamma_r(16,5) = \gamma(16,5) \le 5$. \endproclaim \demo{Proof} A regular $(16,5)$-graph whose domination number is $4$ may be formed by taking the disjoint union of two regular $(8,5)$-graphs whose domination numbers are $2$. That $\gamma(16,5) \le 5$ follows from Proposition 3.1. It will then suffice to prove that if a $(16,5)$-graph $G=(V,E)$ is not regular then $\gamma(G)=4$. We will show that for any $x, y \in V, N[x] \cap N[y] \ne \emptyset$. Given this, choose $x \in V$ of degree at least $6$ and apply Proposition 3.1 with $S=\{x\}$ to conclude that $g_3 \le 2$. This will mean that $3$ vertices of $G$ cover all but (at most) $2$ vertices of $G$ and the remaining $2$ can be covered by a single vertex since their closed neighborhoods are not disjoint completing the proof. Let $x, y \in V$ and assume $N[x] \cap N[y] = \emptyset$. The vertices $x$ and $y$ both have degree 5 or we are done by Proposition 3.1 starting with $S=\{x,y\}$. Let $B=N(x) \cup N(y)$ and let $A = V - N[x] - N[y]$. Clearly $|A| = 4$ and $|B| = 10$. If $A$ can be covered by two vertices, we are done and hence $$ has at most 1 edge. Thus, there are at least $4 \cdot 5 - 2 = 18$ edges from $A$ to $B$. For each $v \in B$, let $A_v$ denote the set of vertices in $A$ which are adjacent to $v$. If there exists $v \in B$ such that $|A_v| \ge 3$, then at most one point $z$ of $A$ is not covered by $v$ and $\{x,y,v,z\}$ is a dominating set. Hence we may assume that $|A_v| \le 2$ for each $v \in B$. Let $B'$ denote the set of vertices $v \in B$ for which $|A_v|=2$. Since there are at least 18 edges joining $B$ to $A$ we must have $|B'| \ge 8$. Note that the $A_v$'s, $v \in B^\prime$, must cover $A$ for if a vertex in $A$ is not adjacent to any vertex in $B'$ then it has degree at most 3. If there exists $u,v \in B'$ such that $A_u$ and $A_v$ are disjoint then $\{x,y,u,v\}$ would be a dominating set. So it follows from Lemma 4.0 that the sets $A_v$, $v \in B'$, have a common vertex. This common element must be a vertex of degree at least 8. Given a vertex of degree $8$, Proposition 3.1 applies to show that the domination number of $G$, in this case, is at most $4$. \qed \enddemo \head 5. Miscellaneous Remarks \endhead The following proposition tempts one to conjecture that $\gamma_r(n,4) = \gamma(n,4) = \lfloor \frac n 3 \rfloor$. \proclaim{Proposition 5.1} For $5 \le n \le 16$, $$ \gamma_r(n,4) = \gamma(n,4) = \lfloor \frac n 3 \rfloor $$ and for $n \ge 17$, $$ \lfloor \frac n 3 \rfloor \le \gamma_r(n,4). $$ \endproclaim \demo{Proof} The first sentence follows from Appendix A. If $n \ge 16$ then we can write $n = 6 \ell + s$ where $\ell \ge 1$ and $s \in \{ 6,7,8,9,10,11 \}$. Now by Lemma 2.1 we have $$ \lfloor \frac n 3 \rfloor =2\ell + \lfloor \frac s 3 \rfloor =\ell \gamma_r(6,4) + \gamma_r(s,4) \le \gamma_r(6\ell + s ,4) = \gamma_r(n,4).\qed $$ \enddemo One of the authors has conjectured that $\gamma_r(n,\delta)=\gamma(n,\delta)$ is always true. Indeed, no example to the contrary has been found in our search. Even when the value of $\gamma(n,\delta)$ is not known, one is sometimes able to show that $\gamma_r(n,\delta)=\gamma(n,\delta)$, see, {\it e.g.}, Proposition 4.11. The other author conjectures that $\gamma_r(n,\delta)=\gamma(n,\delta)$ is false. The discussion following Lemma 4.7 provides an example where a more uneven distribution of degree for the vertices of a graph leads to a higher value of $\gamma$ even though the number of vertices and the number of edges remains the same. Finally we remark that if graphs are assumed to be connected at least in the cases $\delta = 1 $ or $\delta = 2$ different results may be expected. See, for example, \cite{5} where it is proved that with a few exceptions the domination number of a connected $(n,2)$-graph is at most $2n/5$. \remark{ Acknowledgement} The authors are grateful to David Fisher, Teresa Haynes, Bill McCuaig, Boris Shekhtman and Stephen Suen for useful discussions and/or help with references. Special thanks to Brendan McKay for the use of his program makeg. \endremark \Refs \ref \no1 \by I. Anderson \book Combinatorics of Finite Sets \publ Clarendon Press, Oxford, \publaddr New York \yr 1987. \endref \ref \no 2 \by W. E. Clark, D. Fisher, B.Shekhtman and S. Suen \paper Upper bounds for the domination number of a graph \jour preprint \endref \ref \no 3 \by J. F. Fink, M. S. Jacobson, L. K. Kinch and J. Roberts \paper On graphs having domination number half their order \jour Period. Math. Hungar. \vol 16 \yr 1985 \pages 287--293. \endref \ref \no 4 \by T. W. Haynes \paper Domination in graphs: a brief overview \jour preprint \endref \ref \no 5 \by W. McCuaig and B. Shepherd \paper Domination in graphs with minimum degree two \jour J. Graph Theory \vol 13 \yr 1989 \pages 749-762 \endref \ref \no 6 \by B. D. McKay \paper Isomorph-free exhaustive generation \jour preprint \endref \ref \no7 \by O. Ore \book Theory of Graphs \publ Amer. Math. Soc. Colloq. Publ. 38, American Mathematical Society \publaddr Providence \yr 1962. \endref \ref \no8 \by C. Payan and N. H. Xuong \paper Domination--balanced graphs \jour J. Graph Theory \vol 6 \yr 1982 \pages 23--32. \endref \ref \no9 \by B. Reed \paper Paths, stars, and the number three \jour Combin. Probab. and Comput. \vol 5 \yr 1996 \pages 277--295 \endref \endRefs \newpage \head Appendix A \endhead \eightpoint $$ \table{ Table 3. Derivation of $\gamma(n,\delta)$ for $n \le 16$, $ 0 \le \delta \le n-1$.} \text{$n \diagdown \delta$}! 0!1 ! 2 ! 3 ! 4 ! 5 ! 6 ! 7 ! 8 ! 9 ! 10 ! 11 ! 12 ! 13 ! 14 !15 \rr 1 !2.3 ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! \rr 2 !2.3 ! 2.3 ! ! ! ! ! ! ! ! ! ! ! ! ! ! \rr 3 !2.3 !2.3 !2.4 ! ! ! ! ! ! ! ! ! ! ! ! ! \rr 4 !2.3 !2.3 !2.4 !3.1 ! ! ! ! ! ! ! ! ! ! ! ! \rr 5 !2.3 ! 2.3 ! 2.4 ! 3.1 ! 3.1 ! ! ! ! ! ! ! ! ! ! ! \rr 6 !2.3 !2.3 !2.4 !3.1 !3.1 !3.1 ! ! ! ! ! ! ! ! ! ! \rr 7 !2.3 !2.3 !2.4 !3.1 !3.1 !3.1 ! 3.1 ! ! ! ! ! ! ! ! ! \rr 8 !2.3 !2.3 !2.4 !R !3.1 !3.1 !3.1 !3.1 ! ! ! ! ! ! ! ! \rr 9!2.3 !2.3 !2.4 !R !3.1a !3.1 !3.1 !3.1 !3.1 ! ! ! ! ! ! ! \rr 10 !2.3 !2.3 !2.4 !R !3.1a !4.1c !3.1 !3.1 !3.1 !3.1 ! ! ! ! ! ! \rr 11 !2.3 !2.3 !2.4 !R !4.2c !3.1a !3.1a !3.1 !3.1 !3.1 !3.1 ! ! ! ! ! \rr 12 !2.3 !2.3 !2.4 !R !3.1b !3.1a !3.1a !4.3c !3.1 !3.1 !3.1 !3.1 ! ! ! ! \rr 13 !2.3 !2.3 !2.4 !R !Rd !4.4 !3.1a !3.1a !4.5c !3.1 !3.1 !3.1 !3.1 ! ! ! \rr 14 !2.3 !2.3 !2.4 !R !4.6 !3.1a !4.8e !3.1a !3.1a !3.1 !3.1 !3.1 !3.1 !3.1 ! ! \rr 15 !2.3 !2.3 !2.4 !R !3.1f !4.9 !3.1a !3.1a !3.1a !3.1 !3.1 !3.1 !3.1 !3.1 !3.1 ! \rr 16 !2.3 !2.3 !2.4 !R !4.10 !3.1b !3.1b !3.1a !3.1a ! 3.1 !3.1 !3.1 !3.1 !3.1 !3.1 !3.1 \caption{The number in the $(n,\delta)$-th cell is the number of the proposition which justifies the corresponding value in Table 1. The letter code is as follows: \roster \item "{a}" \quad With lower bound from Appendix B graph $G(n,\delta,\gamma)$ \item "{b}" \quad Also used Lemma 2.1 with $\gamma(n,\delta) = 2*\gamma(n/2,\delta)$ \item "{c}" \quad Also required computer search \item "{d}" \quad Also used Lemma 2.1 with $\gamma(7,4) + \gamma(6,4) = 4$ \item "{e}" \quad Confirmed by computer search using 11 days of cpu time \item "{f}" \quad Also used Lemma 2.1 with $\gamma(9,4) + \gamma(6,4) = 5$ \item "{R}" \quad Reed's Theorem \endroster} $$ \tenpoint \newpage \head Appendix B \endhead Each graph $G(n,\dd, \g) $ listed below is an $(n,\dd) $-graph with domination number $\g $. All graphs are either regular or almost regular. The vertices are numbered $0, 1, \dots, n-1 $ and the $i $-th row represents the neighbors of the vertex in the first entry of that row. These graphs were found by Brendan McKay's program makeg augmented by a program to check domination numbers or by {\it ad hoc} construction in two case. \eightpoint $$G(9,3,3) = \left[ \matrix 0&1&2&4& \\ 1&0&2&3& \\ 2&0&1&3& \\ 3&1&2&4& \\ 4&0&3&5&8\\ 5&4&6&7& \\ 6&5&7&8& \\ 7&5&6&8& \\ 8&4&6&7& \endmatrix \right] G(11,3,4) = \left[ \matrix 0&1&2&5& \\ 1&0&2&4& \\ 2&0&1&3& \\ 3&2&4&7& \\ 4&1&3&5&10\\ 5&0&4&6& \\ 6&5&8&9& \\ 7&3&8&9& \\ 8&6&7&10& \\ 9&6&7&10& \\ 10&4&8&9& \endmatrix \right] $$ $$G(9,4,3) = \left[ \matrix 0&1&2&5&8\\ 1&0&2&4&7 \\ 2&0&1&3&6\\ 3&2&4&5&8 \\ 4&1&3&5&7\\ 5&0&3&4&6 \\ 6&2&5&7&8\\ 7&1&4&6&8 \\ 8&0&3&6&7 \endmatrix \right] G(10,4,3 )=\left[ \matrix 0&1&2&3&9\\ 1&0&2&3&8 \\ 2&0&1&3&5\\ 3&0&1&2&4 \\ 4&3&5&6&7\\ 5&2&4&6&7 \\ 6&4&5&8&9\\ 7&4&5&8&9 \\ 8&1&6&7&9\\ 9&0&6&7&8 \endmatrix \right] $$ $$G(11,5,3)= \left[ \matrix 0&1&2&3&5&9& \\ 1&0&2&3&5&8& \\ 2&0&1&3&4&7& \\ 3&0&1&2&4&7& \\ 4&2&3&5&6&8&10\\ 5&0&1&4&6&10& \\ 6&4&5&7&8&9& \\ 7&2&3&6&9&10& \\ 8&1&4&6&9&10& \\ 9&0&6&7&8&10& \\ 10&4&5&7&8&9& \endmatrix \right] G(11,6,3 )= \left[ \matrix 0&1&2&4&7&9&10\\ 1&0&2&3&5&7 &10\\ 2&0&1&3&4&6&8\\ 3&1&2&4&5&8&9 \\ 4&0&2&3&5&6&9\\ 5&1&3&4&6&7&10 \\ 6&2&4&5&7&8&10\\ 7&0&1&5&6&8&9 \\ 8&2&3&6&7&9&10\\ 9&0&3&4&7&8&10 \\ 10&0&1&5&6&8&9 \endmatrix \right] $$ $$G(12,5,3 )= \left[ \matrix 0&1&2&3&9&10\\ 1&0&2&3&4&8 \\ 2&0&1&3&4&5\\ 3&0&1&2&4&5 \\ 4&1&2&3&5&11\\ 5&2&3&4&6&7 \\ 6&5&7&8&10&11\\ 7&5&6&8&9&11 \\ 8&1&6&7&9&10\\ 9&0&7&8&10&11 \\ 10&0&6&8&9&11\\ 11&4&6&7&9&10 \endmatrix \right] G(12,6,3 )= \left[ \matrix 0&1&2&3&5&7&11\\ 1&0&2&3&4&8 &10\\ 2&0&1&3&4&7&11\\ 3&0&1&2&4&6&9 \\ 4&1&2&3&5&6&10\\ 5&0&4&6&7&10&11 \\ 6&3&4&5&7&8&9\\ 7&0&2&5&6&8&9 \\ 8&1&6&7&9&10&11\\ 9&3&6&7&8&10&11 \\ 10&1&4&5&8&9&11\\ 11&0&2&5&8&9&10 \endmatrix \right] $$ $$G(13,6,3 )= \left[ \matrix 0&6&7&8&9&10&11\\ 1&6&7&8&9& 10&11\\ 2&6&8&9&10&11&12\\ 3&6&8&9&10&11& 12\\ 4&7&8&9&10&11&12\\ 5&7&8&9&10&11&12 \\ 6&0&1&2&3&7&12\\ 7&0&1&4&5&6&12 \\ 8&0&1&2&3&4&5\\ 9&0&1&2&3&4&5 \\ 10&0&1&2&3&4&5\\ 11&0&1&2&3&4&5 \\ 12&2&3&4&5&6&7\endmatrix \right] G(13,5,3 )= \left[ \matrix 0&1&2&3&4&6& \\ 1&0&2&3&4&5& \\ 2&0&1&3&4&5& \\ 3&0&1&2&4&5& \\ 4&0&1&2&3&5& \\ 5&1&2&3&4&6& \\ 6&0&5&7&8&9&12\\ 7&6&8&10&11&12& \\ 8&6&7&9&10&11& \\ 9&6&8&10&11&12& \\ 10&7&8&9&11&12& \\ 11&7&8&9&10&12& \\ 12&6&7&9&10&11& \endmatrix \right] $$ $$G(13,4,4 )= \left[ \matrix 0&1&2&3&12\\ 1&0&2&3&10 \\ 2&0&1&3&5\\ 3&0&1&2&4 \\ 4&3&6&7&11\\ 5&2&6&7&11 \\ 6&4&5&8&9\\ 7&4&5&8&9 \\ 8&6&7&10&12\\ 9&6&7&10&12 \\ 10&1&8&9&11\\ 11&4&5&10&12 \\ 12&0&8&9&11 \endmatrix \right] G(13,7,3 )= \left[ \matrix 0&1&2&3&6&7&8&12& \\ 1&0&2 &3&4&6&10&12& \\ 2&0&1&3&4&5&10&11& \\ 3&0 &1&2&4&5&8&9& \\ 4&1&2&3&5&6&7&9& \\ 5&2&3 &4&6&7&11&12& \\ 6&0&1&4&5&7&8&11&12\\ 7&0 &4&5&6&8&9&10& \\ 8&0&3&6&7&9&10&11& \\ 9& 3&4&7&8&10&11&12& \\ 10&1&2&7&8&9&11&12& \\ 11&2&5&6&8&9&10&12& \\ 12&0&1&5&6&9&10& 11& \endmatrix \right] $$ $$G(14,6,3 )= \left[ \matrix 0&6&7&8&9&10&11\\ 1&6&7&9&10 &12&13\\ 2&7&8&9&10&11&12\\ 3&7&9&10&11&12 &13\\ 4&8&9&10&11&12&13\\ 5&8&9&10&11&12& 13\\ 6&0&1&8&11&12&13\\ 7&0&1&2&3&8&13 \\ 8&0&2&4&5&6&7\\ 9&0&1&2&3&4&5 \\ 10&0&1&2&3&4&5\\ 11&0&2&3&4&5&6 \\ 12&1&2&3&4&5&6\\ 13&1&3&4&5&6&7 \endmatrix \right] G(14,5,4 )= \left[ \matrix 0&5&7&8&9&13\\ 1&6&7&8&10&11 \\ 2&6&7&9&10&11\\ 3&9&10&11&12&13 \\ 4&9&10&11&12&13\\ 5&0&8&10&11&12 \\ 6&1&2&8&12&13\\ 7&0&1&2&12&13 \\ 8&0&1&5&6&9\\ 9&0&2&3&4&8 \\ 10&1&2&3&4&5\\ 11&1&2&3&4&5 \\ 12&3&4&5&6&7\\ 13&0&3&4&6&7 \endmatrix \right] $$ $$G(14,4,4 )= \left[ \matrix 0&7&8&9&10\\ 1&7&8&9&11 \\ 2&7&8&12&13\\ 3&7&8&12&13 \\ 4&9&10&11&12\\ 5&9&10&11&13 \\ 6&10&11&12&13\\ 7&0&1&2&3 \\ 8&0&1&2&3\\ 9&0&1&4&5 \\ 10&0&4&5&6\\ 11&1&4&5&6 \\ 12&2&3&4&6\\ 13&2&3&5&6 \endmatrix \right] G(14,7,3 )= \left[ \matrix 0&5&6&7&8&9&12&13\\ 1&6&8&9 &10&11&12&13\\ 2&7&8&9&10&11&12&13\\ 3&7&8 &9&10&11&12&13\\ 4&7&8&9&10&11&12&13\\ 5&0 &6&8&10&11&12&13\\ 6&0&1&5&7&9&10&11\\ 7&0 &2&3&4&6&10&11\\ 8&0&1&2&3&4&5&13\\ 9&0&1& 2&3&4&6&12\\ 10&1&2&3&4&5&6&7\\ 11&1&2&3&4 &5&6&7\\ 12&0&1&2&3&4&5&9\\ 13&0&1&2&3&4&5 &8 \endmatrix \right] $$ $$ G(14,8,3 )= \left[ \matrix \format \l&& \, \ \c \\ 0&4&5&6&7&8&11&12&13\\ 1&4 &5&6&7&9&10&11&13\\ 2&6&7&8&9&10&11&12&13 \\ 3&6&7&8&9&10&11&12&13\\ 4&0&1&6&8&9&10& 12&13\\ 5&0&1&7&8&9&10&11&12\\ 6&0&1&2&3&4 &10&11&12\\ 7&0&1&2&3&5&10&12&13\\ 8&0&2&3 &4&5&10&11&13\\ 9&1&2&3&4&5&11&12&13\\ 10& 1&2&3&4&5&6&7&8\\ 11&0&1&2&3&5&6&8&9\\ 12&0 &2&3&4&5&6&7&9\\ 13&0&1&2&3&4&7&8&9 \endmatrix \right] G(15,5,4)=\left[ \matrix \format \l&& \, \ \c \\ 0&7&8&9&5&14& \\ 1&7&8 &10&6&14& \\ 2&7&9&10 &11&6& \\ 3&9&10&11& 12&13& \\ 4&9&10&11& 12&13& \\ 5&0&8&10&11 &12& \\ 6&1&2&8&12&13 & \\ 7&0&1&2&12&13& \\ 8&0&1&9&5&6& \\ 9&0&2&8&3&4& \\ 10&1&2&3&4&5& \\ 11&2&3&4&5&14& \\ 12&3&4&5&6&7&14 \\ 13&7&3&4&6&14& \\ 14&0&1&11&12&13& \endmatrix \right ] $$ $$ G(15,6,3 )= \left[ \matrix \format \l&& \, \ \c \\ 0&7&8&9&10&11&12\\ 1&7&8&9& 12&13&14\\ 2&7&10&11&12&13&14\\ 3&8&9&10& 11&12&13\\ 4&8&9&10&11&12&14\\ 5&8&9&10&11 &13&14\\ 6&8&9&10&11&13&14\\ 7&0&1&2&12&13 &14\\ 8&0&1&3&4&5&6\\ 9&0&1&3&4&5&6 \\ 10&0&2&3&4&5&6\\ 11&0&2&3&4&5&6 \\ 12&0&1&2&3&4&7\\ 13&1&2&3&5&6&7 \\ 14&1&2&4&5&6&7 \endmatrix \right] G(15,7,3)= \left[ \matrix \format \l&& \, \ \c \\ 0&1&2&3&4&5&7&8& \\ 1&0&2&3&4&5&7&8& \\ 2&0&1&3&4&5&6&13& \\ 3&0&1&2&4&5&6&12& \\ 4&0&1&2&3&5&6&11& \\ 5&0&1&2&3&4&6&10& \\ 6&2&3&4&5&7&9&14& \\ 7&0&1&6&8&9&10&11&14\\ 8&0&1&7&9&12&13& 14& \\ 9&6&7&8&10&11&12&13& \\ 10&5&7&9&11 &12&13&14& \\ 11&4&7&9&10&12&13&14& \\ 12& 3&8&9&10&11&13&14& \\ 13&2&8&9&10&11&12&14& \\ 14&6&7&8&10&11&12&13& \endmatrix \right ] $$ $$ G(15,8,3)= \left[ \matrix \format \l&& \, \ \c \\ 0&5&7&9&10&11&12&13&14 \\ 1&6&7&8&9&10&11&12&13\\ 2&6&7&8&9&10&11 &12&13\\ 3&6&7&8&10&11&12&13&14\\ 4&6&7&8& 10&11&12&13&14\\ 5&0&8&9&10&11&12&13&14\\ 6&1&2&3&4&9&11&12&14\\ 7&0&1&2&3&4&9&10&14 \\ 8&1&2&3&4&5&9&13&14\\ 9&0&1&2&5&6&7&8& 14\\ 10&0&1&2&3&4&5&7&12\\ 11&0&1&2&3&4&5& 6&13\\ 12&0&1&2&3&4&5&6&10\\ 13&0&1&2&3&4& 5&8&11\\ 14&0&3&4&5&6&7&8&9\endmatrix \right] G(16,8,3)= \left[ \matrix \format \l&& \, \ \c \\ 0&5&7&9&10&11&12&13&14 \\ 1&6&7&8&9&10&11&12&13\\ 2&6&7&8&9&10& 11&12&13\\ 3&6&7&8&10&11&12&13&14\\ 4&6& 7&8&10&11&12&13&14\\ 5&0&8&9&10&11&13&14&15 \\ 6&1&2&3&4&9&12&14&15\\ 7&0&1&2&3&4&9& 14&15\\ 8&1&2&3&4&5&13&14&15\\ 9&0&1&2&5 &6&7&14&15\\ 10&0&1&2&3&4&5&12&15\\ 11&0 &1&2&3&4&5&13&15\\ 12&0&1&2&3&4&6&10&15 \\ 13&0&1&2&3&4&5&8&11\\ 14&0&3&4&5&6&7& 8&9\\ 15&5&6&7&8&9&10&11&12\endmatrix \right] $$ \enddocument