\section{Introduction}
Let $\Sigma_{g,p}$ denote a connected orientable surface of genus-$g$ with $p$-punctures, when $p=0$ we write  $\Sigma_{g}$.
The \textit{mapping class group} of $\Sigma_{g,p}$ is the group of isotopy classes of orientation-preserving homeomorphisms of $\Sigma_{g,p}$ preserving the set of punctures.

Here is a brief history of generating sets for ${\rm Mod}(\Sigma_{g,p})$:
Dehn~\cite{de} showed that  ${\rm Mod}(\Sigma_{g})$ can be generated by $2g(g-1)$ Dehn twists. About a quarter century later, Lickorish~\cite{l3} gave a generating set  consisting of $3g-1$ Dehn twists.
Later, Humphries~\cite{H} reduced the number of Dehn twist generators to $2g+1$. He also proved that  the number $2g+1$ is minimal for $g\geq 2$.
Johnson~\cite{j} proved that  the same set of Dehn twists also generates ${\rm Mod}(\Sigma_{g,1})$.
In the presence of multiple punctures, Gervais~\cite{G} proved that ${\rm Mod}(\Sigma_{g,p})$ can be generated by $2g+p$ Dehn twists for $p\geq1$.

If it is not required that the generators are Dehn twists, then it is possible to obtain smaller generating sets for ${\rm Mod}(\Sigma_{g,p})$:
For $g\geq 3$ and $p=0$, Lu~\cite[Theorem~$1.3$]{lu} proved that
${\rm Mod}(\Sigma_{g})$ can be generated by three elements
For $g\geq 1$ and $p=0$ or $1$,
a minimal (since the group is not abelian) generating set of two elements, a product of two Dehn twists  and a product of $2g$ Dehn twists,
was first given by Wajnryb~\cite{w}.  Korkmaz~\cite[Theorem~$5$]{mk2} improved this result by showing that one of these two generators can be taken as a Dehn twist.
He also showed that this group is generated by two elements of finite order ~\cite[Theorem~$14$]{mk2}.
For $g\geq 3$, Kassabov obtained a generating set of  involution elements where the number of generators depends on $g$ and the parity of $p$  (see ~\cite[Theorem~1]{ka}).
Later, Monden~\cite{m1} removed the parity condition on $p$ for $g=7$ and $g=5$. For $g\geq1$ and $p\geq 2$, Monden~\cite{m2} also gave a generating set for ${\rm Mod}(\Sigma_{g,p})$
consisting of three elements.  Recently, he~\cite{m3} gave a minimal generating set for ${\rm Mod}(\Sigma_{g,p})$ containing two elements for $g\geq3$.

Note that any infinite group generated by two involutions must be isomorphic to the infinite dihedral group whose subgroups are either cyclic or dihedral.  Since
${\rm Mod}(\Sigma_{g,p})$ contains nonabelian free groups, it cannot be generated by two involutions.  In this paper, we obtain the following result (cf. ~\cite[Remark~5]{ka}):

\begin{thma}\label{thma}
For every even integer $p\geq 8$ and $g\geq 14$, ${\rm Mod}(\Sigma_{g,p})$ can be generated by three involutions.
Moreover, for every even integer $p\geq 4$ and for $g=3, 4, 5$ or $6$,  ${\rm Mod}(\Sigma_{g,p})$ can be generated by four involutions.
\end{thma}

At the end of the paper, we also show that Theorem~A also
holds for the cases $p=2$ or $p=3$.  For surfaces with odd number of punctures, we have the following result:

\begin{thmb}\label{thmb}
For every odd integer $p\geq 9$ and $g\geq 13$, ${\rm Mod}(\Sigma_{g, p})$ is generated by four involutions.
Moreover, for every odd integer $p\geq 5$ and for $g=3, 4, 5$ or $6$,  ${\rm Mod}(\Sigma_{g,p})$ can be generated by five involutions.
\end{thmb}

The paper is organized as follows: In Section~\ref{S2}, we quickly provide the necessary background on mapping class groups.
The proofs of Theorem~A  and Theorem~B  are given in Section~\ref{S3}.

\medskip

\noindent
{\bf Acknowledgements.}
This work was supported by the Scientific and Technological Research Council of Turkey (T\"{U}B\.{I}TAK)[grant number 120F118].

\par
\section{Background and Results on Mapping Class Groups} \label{S2}

 Let $\Sigma_{g,p}$ denote a connected orientable surface of genus $g$ with $p$ punctures specified by the set $P=\lbrace z_1,z_2,\ldots,z_p\rbrace$ of $p$ distinguished points. If $p$ is zero then we omit it from the notation and write $\Sigma_{g}$. {\textit{The mapping class group}}
 ${\rm Mod}(\Sigma_{g,p})$ of the surface $\Sigma_{g,p}$ is defined to be the group of the isotopy classes of orientation preserving
 self-diffeomorphisms of $\Sigma_{g,p}$ which fix the set $P$. {\textit{The mapping class group}} ${\rm Mod}(\Sigma_{g,p})$ of the surface $\Sigma_{g,p}$ is defined to be the group of isotopy classes of all orientation preserving self-diffeomorphisms of $\Sigma_{g,p}$ which fix the set $P$. Let ${\rm Mod}_{0}(\Sigma_{g,p})$ denote the subgroup of ${\rm Mod}(\Sigma_{g,p})$ consisting of elements which fix the set $P$ pointwise. It is obviuos that we have the following exact sequence:
 \[
1\longrightarrow {\rm Mod}_{0}(\Sigma_{g,p}) \longrightarrow {\rm Mod}(\Sigma_{g,p}) \longrightarrow Sym_{p}\longrightarrow 1,
\]
where $Sym_p$ denotes the symmetric group on the set $\lbrace1,2,\ldots,p\rbrace$ and the last projection is given by the restriction of the isotopy class of a diffeomorphism to its action on the punctures. \par
Let $\beta_{i,j}$ be an embedded arc that joins two punctures $z_i$ and $z_j$ and does not intersect $\delta$ on $\Sigma_{g,p}$.
Let $D_{i,j}$ denote a closed regular neighbourhood of $\beta_{i,j}$, which is a disk with two punctures.
There exists a diffeomorphism $H_{i,j}: D_{i,j} \to D_{i,j}$, which interchanges the punctures such that $H_{i,j}^{2}$ is equal to the right handed Dehn twist about $\partial D_{i,j}$ and is the identity on the complement of the interior of $D_{i,j}$. Such a diffeomorphism is said to be \textit{the (right handed) half twist} about $\beta_{i,j}$. It can be extended to a diffeomorphism of ${\rm Mod}(\Sigma_{g,p})$. Throughout the paper we do not distinguish a
 diffeomorphism from its isotopy class. For the composition of two diffeomorphisms, we
use the functional notation; if $f$ and $g$ are two diffeomorphisms, then
the composition $fg$ means that $g$ is applied first and then $f$.\\
\indent
 For a simple closed
curve $a$ on $\Sigma_{g,p}$, following ~\cite{apy,mk1}, we denote the right-handed
Dehn twist $t_a$ about $a$ by the corresponding capital letter $A$.
Let us also remind the following basic facts of Dehn twists that we use frequently throughout  the paper: Let $a$ and $b$ be
simple closed curves on $\Sigma_{g,p}$ and $f\in {\rm Mod}(\Sigma_{g,p})$.
\begin{itemize}
\item  If $a$ and $b$ are disjoint, then $AB=BA$ (\textit{Commutativity}).
\item If $f(a)=b$, then $fAf^{-1}=B$ (\textit{Conjugation}).
\end{itemize}
Let us finish this section by noting that we  denote the conjugation relation $fgf^{-1}$ by $f^{g}$ for any $f,g \in {\rm Mod}(\Sigma_{g,p})$.

\section{Involution generators for ${\rm Mod}(\Sigma_{g,p})$}\label{S3}
Let us start this section by recalling the following set of generators given by Korkmaz~\cite[Theorem~$5$]{mk1}.

\begin{theorem}\label{thm1}
If $g\geq3$, then the mapping class group ${\rm Mod}(\Sigma_g)$ can be generated by the four elements $R$, $A_1A_{2}^{-1}$, $B_1B_{2}^{-1}$, $C_1C_{2}^{-1}$.
\end{theorem}

Let us also recall the following well known result from algebra.
\begin{lemma}\label{lemma1}
Let $G$ and $K$ be groups. Suppose that the following short exact sequence holds,
\[
1 \longrightarrow N \overset{i}{\longrightarrow}G \overset{\pi}{\longrightarrow} K\longrightarrow 1.
\]
Then the subgroup $\Gamma$ contains $i(N)$ and has a surjection to $K$ if and only if $\Gamma=G$.
\end{lemma}
\par

In our case where $G={\rm Mod}(\Sigma_{g,p})$ and $N={\rm Mod}_{0}(\Sigma_{g,p})$,
we have the following short exact sequence:
\[
1\longrightarrow {\rm Mod}_{0}(\Sigma_{g,p})\longrightarrow {\rm Mod}(\Sigma_{g,p}) \longrightarrow Sym_{p}\longrightarrow 1.
\]
Therefore, we obtain the following useful result which follows immediately from Lemma~\ref{lemma1}. Let $\Gamma$ be a subgroup of ${\rm Mod}(\Sigma_{g,p})$. If the subgroup $\Gamma$ contains ${\rm Mod}_{0}(\Sigma_{g,p})$ and has a surjection to $Sym_p$ then $\Gamma={\rm Mod}(\Sigma_{g,p})$.

\begin{figure}[hbt!]
\begin{center}
\scalebox{0.3}{\includegraphics{gevenpeven.png}}
\caption{The involutions $\rho_1$ and $\rho_2$ if $g=2k$ and $p=2b$.}
\label{EE}
\end{center}
\end{figure}

Throughout the paper, we consider the embeddings of $\Sigma_{g,p}$ into $\mathbb{R}^{3}$ in such a way that it is invariant under the rotations
$\rho_1$ and $\rho_2$.  Here, $\rho_1$ and $\rho_2$ are the rotations by $\pi$ about the $z$-axis  (see Figures~\ref{EE} and~\ref{OE}).
Note that ${\rm Mod}(\Sigma_{g,p})$ contains the element $R=\rho_1\rho_2$ which satisfies the following:
\begin{itemize}
\item [(i)]   $R(a_i)=a_{i+1}$, $R(b_i)=b_{i+1}$ for $i=1,\ldots,g-1$ and $R(b_g)=b_{1}$,
\item [(ii)]  $R(c_i)=c_{i+1}$ for $i=1,\ldots,g-2$,
\item [(iii)] $R(z_1)=z_p$ and $R(z_i)=z_{i-1}$ for $i=2,\ldots,p$.
\end{itemize}

We want to note here that, in the following lemmata, where we present generating sets for surfaces with even number of punctures, we mainly follow the proof
of \cite[Theorem~$5$]{mk1}.   We use them in the proof of Theorem A and then for surfaces with odd number of punctures we explain how our arguments are modified.

\begin{lemma}\label{lemeven}
For every even integer $g=2k\geq14$ and every even integer $p=2b\geq 10$, the subgroup of ${\rm Mod}(\Sigma_{g,p})$ generated by the elements
\[
\rho_1, \rho_2 \textrm{ and }\rho_1H_{b-1,b}H_{b+1,b}^{-1}C_{k-3}B_{k-1}A_k
A_{k+2}^{-1}B_{k+3}^{-1}C_{k+4}^{-1}\]
contains the Dehn twists $A_i$, $B_i$ and $C_i$  for $i=1,\ldots,g$.
\end{lemma}

\begin{proof}

Consider the models of $\Sigma_{g,p}$ depicted in Figure~\ref{EE}. Let $F_1:=H_{b-1,b}H_{b+1,b}^{-1}C_{k-3}B_{k-1}A_k
A_{k+2}^{-1}B_{k+3}^{-1}C_{k+4}^{-1}$ and let $\Gamma$ be the subgroup of ${\rm Mod}(\Sigma_{g,p})$ generated by the elements
$\rho_1$, $\rho_2$ and $\rho_1F_1$. One can see that the elements $R=\rho_1\rho_2$ and $F_1=\rho_1 \rho_1 F_1$ are contained in
the subgroup $\Gamma$.
Let $F_2$ be the element obtained by the conjugation of $F_1$ by $R^{-3}$. Since
\[
R^{-3}(c_{k-3}, b_{k-1}, a_k, a_{k+2}, b_{k+3}, c_{k+4}) = (c_{k-6}, b_{k-4}, a_{k-3}, a_{k-1}, b_{k}, c_{k+1})
\]
and
\[
R^{-3}(z_{b-1},z_{b},z_{b+1})=(z_{b+2},z_{b+3},z_{b+4}),
\]
\[F_2=F_{1}^{R^{-3}}=H_{b+2,b+3}H_{b+4,b+3}^{-1}C_{k-6}B_{k-4}A_{k-3}A_{k-1}^{-1}B_{k}^{-1}C_{k+1}^{-1}\in \Gamma.
\]
\noindent
Let $F_3$ be the element $F_1^{F_1F_2^{-1}}$, that is
$
F_3=H_{b-1,b}H_{b+1,b}^{-1}C_{k-3}A_{k-1}B_k
A_{k+2}^{-1}B_{k+3}^{-1}C_{k+4}^{-1} \in \Gamma.
$

Since we use repeatedly similar calculations in the remaining parts of the paper, let us provide  some details here. It can be shown that the diffeomorphism $F_1F_2^{-1}$ maps the curves $\lbrace c_{k-3},b_{k-1},a_k,a_{k+2},b_{k+3},c_{k+4} \rbrace$ to the curves $\lbrace c_{k-3},b_{k-1},a_k,b_{k+2},a_{k+3},c_{k+4}  \rbrace$, respectively. Also it follows from the factorizations of half twists $H_{b-1,b}H_{b+1,b}^{-1}$ and $H_{b-4,b-3}H_{b-2,b-3}^{-1}$ commute and  we get
\begin{eqnarray*}
F_3&=&F_1^{F_1F_2^{-1}}\\
&=&(F_1F_2^{-1})(H_{b-1,b}H_{b+1,b}^{-1}C_{k-3}B_{k-1}A_k
A_{k+2}^{-1}B_{k+3}^{-1}C_{k+4}^{-1})(F_1F_2^{-1})^{-1}\\
&=&H_{b-1,b}H_{b+1,b}^{-1}C_{k-3}A_{k-1}B_k
A_{k+2}^{-1}B_{k+3}^{-1}C_{k+4}^{-1}.
\end{eqnarray*}
 The subgroup $\Gamma$ contains the following elements:
\begin{eqnarray*}
F_4&=&F_{3}^{R^{-3}}=H_{b+2,b+3}H_{b+4, b+3}^{-1}C_{k-6}A_{k-4}B_{k-3}A_{k-1}^{-1}B_{k}^{-1}C_{k+1}^{-1},\\
F_5&=&F_{3}^{F_3F_4}=H_{b-1,b}H_{b+1,b}^{-1}B_{k-3}A_{k-1}B_k
A_{k+2}^{-1}B_{k+3}^{-1}C_{k+4}^{-1}.
\end{eqnarray*}
 From these, we obtain the element
 $F_5F_3^{-1}=B_{k-3}C_{k-3}^{-1}$, which is contained in $\Gamma$. By conjugating this element with powers of $R$, we conclude that
 \[
 B_{i}C_{i}^{-1}\in \Gamma \  \textrm{for}  \ i=1, \ldots, g-1.
 \]
The subgroup $\Gamma$ also contains the element $F_1F_3^{-1}=B_{k-1}A_{k}B_{k}^{-1}A_{k-1}^{-1}$.
After conjugating with $R^3$ and considering the inverse, we have $A_{k+2}B_{k+3}A_{k+3}^{-1}B_{k+1}^{-1} \in \Gamma$.
This in turn  implies that for $i=1,\ldots,g-1$, the elements
\[
A_iB_{i+1}A_{i+1}^{-1}B_i^{-1}\in \Gamma.
\]
We also have the following elements in $\Gamma$:
\begin{eqnarray*}
F_6&=&F_1 (A_{k+2}B_{k+3}A_{k+3}^{-1}B_{k+2}^{-1})=H_{b-1,b}H_{b+1,b}^{-1}C_{k-3}B_{k-1}A_{k}
B_{k+2}^{-1}A_{k+3}^{-1}C_{k+4}^{-1},\\
F_7&=&F_{6}^{R^{-3}}=H_{b+2,b+3}H_{b+4,b+3}^{-1}C_{k-6}B_{k-4}A_{k-3}
B_{k-1}^{-1}A_{k}^{-1}C_{k+1}^{-1} \textrm{ and }\\
F_8&=&F_{6}^{F_6F_7}=H_{b-1,b}H_{b+1,b}^{-1}C_{k-3}B_{k-1}A_k
C_{k+1}^{-1}A_{k+3}^{-1}C_{k+4}^{-1},
\end{eqnarray*}
Hence, we can conclude that $F_8^{-1}F_6=C_{k+1}B_{k+2}^{-1}\in \Gamma$. Again conjugating with $R$  implies that
\[
C_iB_{i+1}^{-1}\in \Gamma, \ \textrm{for all} \  i=1,\ldots,g-1.
\]
Furthermore, we can see that  $\Gamma$  contains the following elements:
\begin{eqnarray*}
F_9&=&(B_{k-3}C_{k-3}^{-1})F_3(C_{k+4}B_{k+5}^{-1})=H_{b-1,b}H_{b+1,b}^{-1}B_{k-3}A_{k-1}B_kA_{k+2}^{-1}B_{k+3}^{-1}B_{k+5}^{-1},\\
F_{10}&=&F_{9}^{R^{-3}}=H_{b+2,b+3}H_{b+4,b+3}^{-1}B_{k-6}A_{k-4}B_{k-3}A_{k-1}^{-1}B_{k}^{-1}B_{k+2}^{-1},\\
F_{11}&=&F_{9}^{F_9F_{10}}=H_{b-1,b}H_{b+1,b}^{-1}B_{k-3}A_{k-1}B_kB_{k+2}^{-1}B_{k+3}^{-1}B_{k+5}^{-1}.
\end{eqnarray*}
From these, we obtain $F_{11}F_{9}^{-1}=B_{k+2}^{-1} A_{k+2} \in \Gamma$. By the action of $R$, we can conclude that
\[
A_iB_i^{-1}\in \Gamma \ \textrm{for all}  \ i=1, \ldots, g.
\]
This completes the proof by  Theorem~\ref{thm1} since the subgroup $\Gamma$ contains the elements
\begin{eqnarray*}
A_1A_{2}^{-1}&=&(A_1B_1^{-1})(B_1C_1^{-1})(C_1B_{2}^{-1})(B_{2}A_{2}^{-1}),\\
B_1B_{2}^{-1}&=&(B_1C_1^{-1})(C_1B_{2}^{-1}) \textrm{ and }\\
C_1C_{2}^{-1}&=&(C_1B_{2}^{-1})(B_{2}C_{2}^{-1}).
\end{eqnarray*}
\end{proof}

\begin{figure}[hbt!]
\begin{center}
\scalebox{0.2}{\includegraphics{goddpeven.png}}
\caption{The involutions $\rho_1$ and $\rho_2$ for $g=2k+1$ and $p=2b$.}
\label{OE}
\end{center}
\end{figure}

If $g$ is  odd and $p$ is even, we have the following result:
\begin{lemma}\label{lemodd}
For every odd integer $g=2k+1 \geq15$ and even integer $p=2b \geq 10$, the subgroup of ${\rm Mod}(\Sigma_{g,p})$  generated by the elements
\[
\rho_1,\rho_2 \textrm{ and }\rho_1H_{b-1,b}H_{b+1,b}^{-1}C_{k-3}B_kA_{k+1}A_{k+2}^{-1}B_{k+3}^{-1}C_{k+5}^{-1}
\]
 contains the Dehn twists $A_i$, $B_i$ and $C_i$  for $i=1,\ldots,g$.
\end{lemma}

\begin{proof}
Consider the models for $\Sigma_{g,p}$ as shown in Figure~\ref{OE}. Let $\Gamma$ denote the subgroup of ${\rm Mod}(\Sigma_{g,p})$
generated by the elements $\rho_1$, $\rho_2$ and $\rho_1G_1$, where $G_1=H_{b-1,b}H_{b+1,b}^{-1}C_{k-3}B_kA_{k+1}A_{k+2}^{-1}B_{k+3}^{-1}C_{k+5}^{-1}$.
The elements $R=\rho_1\rho_2$ and $G_1=\rho_1 \rho_1 G_1$ belong to the subgroup $\Gamma$.
Let $G_2$ denote the conjugation of $G_1$ by $R^{-3}$,
\[
G_2=G_{1}^{R^{-3}}=H_{b+2,b+3}H_{b+4,b+3}^{-1}C_{k-6}B_{k-3}A_{k-2}A_{k-1}^{-1}B_{k}^{-1}C_{k+2}^{-1}.
\]
It is easy to verify that the element
\begin{eqnarray*}
G_3&=&G_{1}^{G_1G_2}\\
&=&H_{b-1,b}H_{b+1,b}^{-1}B_{k-3}B_kA_{k+1}A_{k+2}^{-1}C_{k+2}^{-1}C_{k+5}^{-1}
\end{eqnarray*}
is contained in $\Gamma$.
Let
\[
G_4=G_{3}^{R^{-3}}=H_{b+2,b+3}H_{b+4,b+3}^{-1}B_{k-6}B_{k-3}A_{k-2}A_{k-1}^{-1}C_{k-1}^{-1}C_{k+2}^{-1}.
\]
Thus we get the element
\begin{eqnarray*}
G_5=G_3^{G_3G_4^{-1}}
=H_{b-1,b}H_{b+1,b}^{-1}B_{k-3}C_{k-1}A_{k+1}A_{k+2}^{-1}C_{k+2}^{-1}C_{k+5}^{-1},
\end{eqnarray*}
which is contained in $G$. This implies that $G_3G_5^{-1}=B_kC_{k-1}^{-1}\in \Gamma$. By conjugating $B_kC_{k-1}^{-1}$ with powers of $R$, we see that
\[
B_{i+1}C_{i}^{-1}\in \Gamma,
\]
for all $i=1,\ldots,g-1$. In particular, the element $C_{k+5}B_{k+6}^{-1}\in \Gamma$. Hence, the subgroup $\Gamma$ contains the following element:
\[
G_6=G_1(C_{k+5}B_{k+6}^{-1})=H_{b-1,b}H_{b+1,b}^{-1}C_{k-3}B_kA_{k+1}A_{k+2}^{-1}B_{k+3}^{-1}B_{k+6}^{-1}.
\]
Then, we see that the elements
\begin{eqnarray*}
G_7&=&G_6^{R^{-3}}=H_{b+2,b+3}H_{b+4,b+3}^{-1}C_{k-6}B_{k-3}A_{k-2}A_{k-1}^{-1}B_{k}^{-1}B_{k+3}^{-1} \textrm{ and}\\
G_8&=&G_6^{G_6G_7}=H_{b-1,b}H_{b+1,b}^{-1}B_{k-3}B_kA_{k+1}A_{k+2}^{-1}B_{k+3}^{-1}B_{k+6}^{-1}
\end{eqnarray*}
are contained in $\Gamma$, which implies that the subgroup $\Gamma$ contains the element $G_6G_8^{-1}=C_{k-3}B_{k-3}^{-1}$. By the action of $R$ we see that
\[
C_iB_i^{-1} \in \Gamma
\]
for all $i=1,\ldots, g-1$.  Moreover, we get
\begin{eqnarray*}
G_9&=&(B_{k-2}C_{k-3}^{-1})G_6=H_{b-1,b}H_{b+1,b}^{-1}B_{k-2}B_kA_{k+1}A_{k+2}^{-1}B_{k+3}^{-1}B_{k+6}^{-1} \in \Gamma,\\
G_{10}&=&G_9^{R^{-3}}=H_{b+2,b+3}H_{b+4,b+3}^{-1}B_{k-5}B_{k-3}A_{k-2}A_{k-1}^{-1}B_{k}^{-1}B_{k+3}^{-1}\in \Gamma \textrm{ and}\\
G_{11}&=&G_9^{G_9G_{10}}=H_{b-1,b}H_{b+1,b}^{-1}A_{k-2}B_kA_{k+1}A_{k+2}^{-1}B_{k+3}^{-1}B_{k+6}^{-1}\in \Gamma.
\end{eqnarray*}
From these, we have $G_9G_{11}^{-1}=B_{k-2}A_{k-2}^{-1}\in \Gamma$ so that
\[
B_iA_i^{-1}\in \Gamma,
\]
for $i=1,\ldots,g$, by the action of $R$. The remaining part of the proof can be completed as in the proof of Lemma~\ref{lemeven}.
\end{proof}

In the following four lemmata, we give generating sets for smaller genera
\begin{lemma}\label{lem6}
For $g=6$ and every even integer $p\geq4$, the group generated by the elements
\[
\rho_1,\rho_2, \rho_2B_2A_3A_4^{-1}B_5^{-1} \textrm{ and }\rho_1H_{b-1,b}H_{b+1,b}^{-1}C_{3}C_{4}^{-1}
\]
 contains the Dehn twists $A_i$, $B_i$ and $C_i$  for $i=1,\ldots,g$.
\end{lemma}
\begin{proof}
Consider the models for $\Sigma_{6,p}$ as shown in Figure~\ref{EE}. Let $\Gamma$ be the subgroup of ${\rm Mod}(\Sigma_{6,p})$ generated by the elements $\rho_1$, $\rho_2$, $\rho_2F_1$ and $\rho_1E_1$ where $F_1=B_2A_3A_4^{-1}B_5^{-1}$ and $E_1=H_{b-1,b}H_{b+1,b}^{-1}C_{3}C_{4}^{-1}$. Hence the elements $R=\rho_1\rho_2$, $F_1=\rho_2 \rho_2 F_1$ and $E_1=\rho_1\rho_1E_1$ are contained in the subgroup $\Gamma$.

The subgroup $\Gamma$ contains the following elements:
\begin{eqnarray*}
F_2&=&F_1^{R}=B_3A_4A_5^{-1}B_6^{-1} \in \Gamma,\\
F_{3}&=&F_{1}^{F_1F_2}=B_2B_3A_4^{-1}A_5^{-1}\in \Gamma\\
F_4&=&F_3^{R}=B_3B_4A_5^{-1}A_6^{-1}\in \Gamma
\textrm{ and}\\
F_{5}&=&F_3^{F_3F_{4}^{-1}}=B_2B_3B_4^{-1}A_5^{-1}\in \Gamma.
\end{eqnarray*}
Hence we get the element $F_5^{-1}F_3=B_4A_4^{-1}\in \Gamma$. By the action of $R$, for all $i=1,\ldots,6$,
\[
A_iB_i^{-1}\in \Gamma.
\]
Moreover, we have
\begin{eqnarray*}
F_6&=&E_1^{E_1F_3}=H_{b-1,b}H_{b+1,b}^{-1}B_{3}C_{4}^{-1} \in \Gamma
\textrm{ and}\\
F_{7}&=&E_1^{E_1F_{1}}=H_{b-1,b}H_{b+1,b}^{-1}C_{3}B_{5}^{-1}\in \Gamma.
\end{eqnarray*}
This implies that $F_6E_1^{-1}=B_3C_3^{-1}\in \Gamma$ and $F_7^{-1}E_1=B_5C_4^{-1}\in \Gamma$ and so
\[
B_iC_i^{-1}\in \Gamma \textrm{ and } B_{i+1}C_{i}^{-1}\in \Gamma,
\]
for all $i=1,\ldots,5$, by conjugating these elements with powers of $R$. The proof can be completed as in the proof of Lemma~\ref{lemeven}.
\end{proof}

\begin{lemma}\label{lem5}
For $g=5$ and every even integer $p\geq4$, the group generated by the elements
\[
\rho_1,\rho_2, \rho_1H_{b-1,b}H_{b+1,b}^{-1}A_{3}A_{4}^{-1} \textrm{ and }\rho_2A_2B_2C_2C_3^{-1}B_4^{-1}A_4^{-1}
\]
 contains the Dehn twists $A_i$, $B_i$ and $C_i$  for $i=1,\ldots,g$.
\end{lemma}
\begin{proof}
Consider the models for $\Sigma_{5,p}$ as shown in Figure~\ref{OE}. Let $\Gamma$ denote the subgroup of ${\rm Mod}(\Sigma_{5,p})$ generated by the elements $\rho_1$, $\rho_2$, $\rho_1F_1$ and $\rho_2E_1$ where $F_1=H_{b-1,b}H_{b+1,b}^{-1}A_{3}A_{4}^{-1}$ and $E_1=A_2B_2C_2C_3^{-1}B_4^{-1}A_4^{-1}$. Thus the elements $R=\rho_1\rho_2$, $F_1=\rho_1 \rho_1 F_1$ and $E_1=\rho_2\rho_2E_1$ are in the subgroup $\Gamma$.

One can obtain the following elements:
\begin{eqnarray*}
F_2&=&F_1^{R^{-1}}=H_{b,b+1}H_{b+2,b+1}^{-1}A_{2}A_{3}^{-1}
\\
F_{3}&=&F_2^{E_1}=H_{b,b+1}H_{b+2,b+1}^{-1}B_{2}A_{3}^{-1} \textrm{ and}\\
F_4&=&F_3^{E_1}=H_{b,b+1}H_{b+2,b+1}^{-1}C_{2}A_{3}^{-1},
\end{eqnarray*}
which are contained in $\Gamma$. Thus we get that $F_2F_3^{-1}=A_2B_2^{-1}\in \Gamma$ and $F_3F_4^{-1}=B_2C_2^{-1}\in \Gamma$. By conjugating these elements with powers of $R$, we see that
\[
A_iB_i^{-1}\in \Gamma \textrm{ and }B_jC_j^{-1}\in \Gamma,
\]
which also implies that $A_iC_i^{-1}\in \Gamma$ for all $i=1,\ldots, 5$ and $j=1,\ldots, 4$.
Finally, it can be verified that
\[
E_1(a_3,c_3)=(a_3,b_4)
\]
so that the group $\Gamma$ contains the element
\[
(A_3C_3^{-1})^{E_1}=A_3B_4^{-1}.
\]
Hence $A_iB_{i+1}^{-1}\in \Gamma$ for all $i=1,\ldots,5$ by the action of $R$. The rest of the proof is similar to that of Lemma~\ref{lemeven}.
\end{proof}

\begin{lemma}\label{lem4}
For $g=4$ and every even integer $p\geq4$, the group generated by the elements
\[
\rho_1,\rho_2, \rho_2B_1A_2A_3^{-1}B_4^{-1} \textrm{ and }\rho_1H_{b-1,b} H_{b+1,b}^{-1}C_{2}C_{3}^{-1}
\]
 contains the Dehn twists $A_i$, $B_i$ and $C_i$  for $i=1,\ldots,g$.
\end{lemma}
\begin{proof}
Let us consider the models for $\Sigma_{4,p}$ as shown in Figure~\ref{EE} and let $\Gamma$ be the subgroup of ${\rm Mod}(\Sigma_{4,p})$ generated by the elements $\rho_1$, $\rho_2$, $\rho_2F_1$ and $\rho_1E_1$ where $F_1=B_1A_2A_3^{-1}B_4^{-1}$ and $E_1=H_{b-1,b} H_{b+1,b}^{-1}C_{2}C_{3}^{-1}$. Thus it is clear that the elements $R=\rho_1\rho_2$, $F_1=\rho_2 \rho_2 F_1$ and $E_1=\rho_1\rho_1E_1$ belong to the subgroup $\Gamma$.   We have the element
\[
F_2=E_1^{E_1F_1}=H_{b-1,b} H_{b+1,b}^{-1}C_{2}B_{4}^{-1}\in \Gamma.
\]
Thus the subgroup $\Gamma$ contains the elements $F{_2}^{-1} E_1=B_4C_3^{-1}$ and $\rho_1(B_4C_3^{-1})\rho_1=B_2C_2^{-1}$. By conjugating these elements with powers of $R$, we get
\[
B_{i+1}C_i^{-1}\in \Gamma \textrm{ and } B_iC_i^{-1}\in \Gamma
\]
for all $i=1,2,3$.  One can also obtain that the subgroup $\Gamma$ contains the following elements:
\begin{eqnarray*}
F_3&=&(C_1B_1^{-1})F_1=C_1A_2A_3^{-1}B_4^{-1},\\
F_4&=&F_3^{R}(B_1C_1^{-1})=C_2A_3A_4^{-1}B_1^{-1}(B_1C_1^{-1})=C_2A_3A_4^{-1}C_1^{-1}\textrm{ and}\\
F_5&=&F_3^{F_3F_4}=C_1A_2A_3^{-1}A_4^{-1}.
\end{eqnarray*}
Thus we obtain that $F_5F_3^{-1}=A_4B_4^{-1}\in \Gamma$. By the action of $R$, $A_iB_i^{-1}\in \Gamma$ for all $i=1,2,3,4$.
The remaining part of the proof is very similar to that of Lemma~\ref{lemeven}.
\end{proof}

\begin{lemma}\label{lem3}
For $g=3$ and every even $p\geq4$, the group generated by the elements
\[
\rho_1,\rho_2, \rho_1H_{b-1,b} H_{b+1,b}^{-1}A_{2}A_{3}^{-1}
\textrm{ and }\rho_2A_1B_1C_1C_2^{-1}B_3^{-1}A_3^{-1}
\]
 contains the Dehn twists $A_i$, $B_i$ and $C_i$  for $i=1,2,3$.
\end{lemma}
\begin{proof}
Consider the models for $\Sigma_{3,p}$ as shown in Figure~\ref{OE}. Let $\Gamma$ be the subgroup of ${\rm Mod}(\Sigma_{3,p})$ generated by the elements $\rho_1$, $\rho_2$, $\rho_1F_1$ and $\rho_2E_1$ where $F_1=H_{b-1,b} H_{b+1,b}^{-1}A_{2}A_{3}^{-1}$ and $E_1=A_1B_1C_1C_2^{-1}B_3^{-1}A_3^{-1}$. Thus the elements $R=\rho_1\rho_2$, $F_1=\rho_1 \rho_1 F_1$ and $E_1=\rho_2\rho_2E_1$ are contained in the subgroup $\Gamma$. We get the elements
\begin{eqnarray*}
F_2&=&F_1^{R^{-1}}=H_{b,b+1} H_{b+2,b+1}^{-1}A_{1}A_{2}^{-1}\in \Gamma,\\
F_3&=&F_2^{E_1}=H_{b,b+1} H_{b+2,b+1}^{-1}B_{1}A_{2}^{-1}\in \Gamma \textrm{ and}\\
F_4&=&F_3^{E_1}=H_{b,b+1} H_{b+2,b+1}^{-1}C_{1}A_{2}^{-1}\in \Gamma.
\end{eqnarray*}
From these, the subgroup $\Gamma$ contains the elements $F_2F_3^{-1}=A_1B_1^{-1}$ and $F_3F_4^{-1}=B_1C_1^{-1}$, which implies that $A_1C_1^{-1}\in \Gamma$. Hence
\[
A_iB_i^{-1}\in \Gamma, B_jC_j^{-1}\in \Gamma \textrm{ and } A_jC_j^{-1}\in \Gamma
\]
for all $i=1,2,3$ and $j=1,2$, by the action of $R$.  We also have the following element
\[
(A_2C_2^{-1})^{E_1}=A_2B_3^{-1},
\]
which is contained in $\Gamma$. This implies that
\[
A_iB_{i+1}^{-1}\in \Gamma
\]
for $i=1,2$ by the action of $R$. One can complete the proof as in the proof of Lemma~\ref{lemeven}.
\end{proof}

\begin{remark}\label{podd}
Our results in lemmata~\ref{lemeven}--\ref{lem3}  are also valid for surfaces with odd number of punctures.  To see that our proofs also work
for such surfaces we refer the reader to Figures~$3$ and $5$ in \cite{apy1}.
\end{remark}

\begin{figure}[hbt!]
\begin{center}
\scalebox{0.3}{\includegraphics{curves.png}}
\caption{The curves $e_{i,j}$ and $\gamma_i$ on the surface $\Sigma_{g,p}$.}
\label{C}
\end{center}
\end{figure}

Now, in the remainder of the paper let $\Gamma$ be the subgroup of ${\rm Mod}(\Sigma_{g,p})$
generated by the elements given explicitly in lemmata~\ref{lemeven}--\ref{lem3} with the conditions mentioned in these lemmata.
The proof of the following lemma is similar to that of ~ \cite[Lemma~$4.6$]{apy1}, nevertheless we give a proof for the sake of completeness of the paper.

\begin{lemma}\label{lemma4}
The group ${\rm Mod}_{0}(\Sigma_{g,p})$ is contained in the group $\Gamma$.
\end{lemma}

\begin{proof}
It follows from the subgroup $\Gamma$ contains the elements $A_i$, $B_i$ and $C_j$ for all $i=1,\ldots,g$ and $j=1,\ldots,g-1$ by lemmata~\ref{lemeven}--\ref{lem3} that
it is sufficient to prove that $\Gamma$ contains the Dehn twists $E_{i.j}$ for some fixed $i$ ($j=1,2,\ldots,p-1$). Let us first note that $\Gamma$ contains $A_{g}$ and $R=\rho_1\rho_2$. Consider the models for $\Sigma_{g,p}$ as shown in Figures~\ref{EE} and~\ref{OE}. By the fact that the diffeomorphism $R$ maps $a_{g}$ to $e_{1,p-1}$, we get
\[
RA_{g}R^{-1}=E_{1,p-1} \in \Gamma.
\]
The diffeomorphism $\phi_{i}=B_{i+1}\Gamma_i^{-1}C_iB_i$ which maps each $e_{i,j}$ to $e_{i+1,j}$ for $j=1,2,\ldots,p-1$ (see Figure~\ref{C}).
By the proof of~ \cite[Lemma~$4.5$]{apy1}, the group $\Gamma$ contains the element $\phi_{g}$. Thus we have
\[
\phi_{g-1}\cdots \phi_2\phi_1E_{1,p-1}(\phi_{g-1}\cdots \phi_2\phi_1)^{-1}=E_{g,p-1}\in H.
\]
Likewise, the diffeomorphism $R$ sends $e_{g,p-1}$ to $e_{1,p-2}$. Then we obtain
\[
RE_{g,p-1}R^{-1}=E_{1,p-2}\in \Gamma.
\]
It follows from
\[
\phi_{g-1}\cdots \phi_2\phi_1E_{1,p-2}(\phi_{g-1}\cdots \phi_2\phi_1)^{-1}=E_{g,p-2}\in \Gamma
\]
 that
 \[
 R(E_{g,p-2})R^{-1}=E_{1,p-3}\in \Gamma
 \]
 Continuing in this way, we conclude that the elements $E_{1,1},E_{1,2},$ $\ldots,E_{1,p-1}$ belong to $\Gamma$, which completes the proof.
\end{proof}

\begin{proofa}
Consider the surface $\Sigma_{g,p}$ as in Figures~\ref{EE} and~\ref{OE}.

\underline{ If $g=2k\geq 14$ and $p=2b\geq 10$}: In this case, consider the surface $\Sigma_{g,p}$ as in Figure~\ref{EE}. Since
\[
\rho_1(c_{k-3})=c_{k+4}, \rho_1(b_{k-1})=b_{k+3} \textrm{ and }\rho_1(a_{k})=a_{k
+2},
\]
 we get
\[
\rho_1C_{k-3}\rho_1=C_{k+4},
\rho_1B_{k-1}\rho_1=B_{k+3} \textrm{ and }
\rho_1A_{k}\rho_1=A_{k+2}.
\]
Also, since  $\rho_1H_{b-1,b}\rho_1=H_{b+1,b}$,
it is easy to see that $\rho_1H_{b-1,b}H_{b+1,b}^{-1}C_{k-3}B_{k-1}A_k
A_{k+2}^{-1}B_{k+3}^{-1}C_{k+4}^{-1}$ is an involution. Therefore, the generators of the subgroup $\Gamma$ given in Lemma~\ref{lemeven} are involutions.

\underline{ If $g=2k+1\geq 13$ and $p=2b\geq10$}: In this case, consider the surface $\Sigma_{g,p}$ as in Figure~\ref{OE}. It follows from
\[
\rho_1(c_{k-3})=c_{k+5}, \rho_1(b_{k})=b_{k+3} \textrm{ and }\rho_1(a_{k+1})=a_{k
+2},
\]
 that we have
\[
\rho_1C_{k-3}\rho_1=C_{k+5},
\rho_1B_{k}\rho_1=B_{k+3} \textrm{ and }
\rho_1A_{k+1}\rho_1=A_{k+2}.
\]
Also, by the fact that $\rho_1H_{b-1,b}\rho_1=H_{b+1,b}$,
it is easy to see that the element $\rho_1H_{b-1,b}H_{b+1,b}^{-1}C_{k-3}B_kA_{k+1}A_{k+2}^{-1}B_{k+3}^{-1}C_{k+5}^{-1}$ is an involution.
We conclude that the generators of the subgroup $\Gamma$ given in Lemma~\ref{lemodd} are involutions.

\underline{ If $g=3,4,5$ or $g=6$ and $p=2b\geq4$}:
It follows from
\begin{itemize}
\item $\rho_2(b_2)=b_5$,  $\rho_2(a_3)=a_4$ and $\rho_1(c_3)=c_4$ if $g=6$,
\item $\rho_1(a_3)=a_4$,  $\rho_2(a_2)=a_4,\rho_2(b_2)=b_4$ and $\rho_2(c_2)=c_3$ if $g=5$,
\item $\rho_2(b_1)=b_4$,  $\rho_2(a_2)=a_3$ and $\rho_1(c_2)=c_3$ if $g=4$
\item $\rho_1(a_2)=a_3$,  $\rho_2(a_1)=a_3,\rho_2(b_1)=b_3$ and $\rho_2(c_1)=c_2$ if $g=3$ and
\item $\rho_1H_{b-1,b}\rho_1=H_{b+1,b}$ if $g=3,4,5$ or $g=6$
\end{itemize}
that the following elements:
\begin{itemize}
\item  $\rho_2B_2A_3A_4^{-1}B_5^{-1}$ and $\rho_1H_{b-1,b}H_{b+1,b}^{-1}C_{3}C_{4}^{-1}$ if $g=6$,
\item $\rho_1H_{b-1,b}H_{b+1,b}^{-1}A_{3}A_{4}^{-1}$ and $\rho_2A_2B_2C_2C_3^{-1}B_4^{-1}A_4^{-1}$  if $g=5$,
\item $\rho_2B_1A_2A_3^{-1}B_4^{-1}$ and $\rho_1H_{b-1,b} H_{b+1,b}^{-1}C_{2}C_{3}^{-1}$ if $g=4$ and
\item $\rho_1H_{b-1,b} H_{b+1,b}^{-1}A_{2}A_{3}^{-1}$
 and $\rho_2A_1B_1C_1C_2^{-1}B_3^{-1}A_3^{-1}$ if $g=3$
\end{itemize}
given in lemmata~\ref{lem6}--\ref{lem3} are involutions.

Next, we show that the subgroup $\Gamma$ is equal to the mapping class group ${\rm Mod}(\Sigma_{g,p})$.
By Lemma~\ref{lemma4}, the group ${\rm Mod}_{0}(\Sigma_{g,p})$ is contained in the group $\Gamma$. Hence, by Lemma~\ref{lemma1}, we need to prove that
$\Gamma$ is mapped surjectively onto $Sym_p$. The element $\rho_1\rho_2 \in \Gamma$ has the image $(1,2,\ldots,p)\in Sym_p$.

As proven above,  the Dehn twists $A_i$, $B_i$ and $C_i$ belong to the subgroup $\Gamma$. Thus, it can be easily observed that the factorization of half twists $H_{b-1,b}H_{b+1,b}^{-1}$ are contained in subgroup $\Gamma$. Therefore, the group $\Gamma$ also contains the following element:
\[
R^{b-2}(H_{b-1,b}H_{b+1,b}^{-1})R^{2-b}=H_{1,2}H_{3,2}^{-1},
\]
which has the image $(1,2,3)\in Sym_p$. This completes the proof since the elements $(1,2,\ldots,p)$ and $(1,2,3)$ of $Sym_p$ generate the whole group $Sym_p$ if $p$ is even~\cite[Theorem B]{iz}.

\end{proofa}

When the number of punctures is odd, we introduce an additional involution $\rho_3$ (depicted in Figure~\ref{rho3})  to our generating set.  The main reason behind adding an extra involution is for generating
the symmetric group $Sym_p$.  We want to point out that aside from generating $Sym_p$, all of our proofs in the case of even number of punctures work for odd number of punctures.
For $\rho_1$ and $\rho_2$, we distribute punctures as in Figures $3$ and $5$ in \cite{apy1} (see also Remark~\ref{podd}).

\begin{figure}[hbt!]
\begin{center}
\scalebox{0.35}{\includegraphics{rho3.png}}
\caption{The involution $\rho_3$  on the surface $\Sigma_{g,p}$ for $p=2b+1$.}
\label{rho3}
\end{center}
\end{figure}

\begin{proofb}
For the first part of the proof we show that
\begin{itemize}
\item [(i)] For every even integer $g=2k\geq14$ and every odd integer $p=2b+1\geq 9$, the subgroup ${\rm Mod}_{0}(\Sigma_{g,p})$ of ${\rm Mod}(\Sigma_{g,p})$ generated by the elements
\[
\rho_1, \rho_2 \textrm{ and }\rho_1H_{b-1,b}H_{b+1,b}^{-1}C_{k-3}B_{k-1}A_k
A_{k+2}^{-1}B_{k+3}^{-1}C_{k+4}^{-1}, \rho_3.
\]

\item[(ii)] For every odd integer $g=2k+1 \geq15$ and odd integer $p=2b+1 \geq 9$, the subgroup ${\rm Mod}_{0}(\Sigma_{g,p})$ of ${\rm Mod}(\Sigma_{g,p})$  generated by the elements
\[
\rho_1,\rho_2 \textrm{ and }\rho_1H_{b-1,b}H_{b+1,b}^{-1}C_{k-3}B_kA_{k+1}A_{k+2}^{-1}B_{k+3}^{-1}C_{k+5}^{-1},  \rho_3.
\]
\end{itemize}
Note that, it is enough to prove that the subgroup generated by the elements above mapped surjectively onto $Sym_p$.
For this, consider the images of the elements $\rho_1$, $\rho_2$ and $\rho_3$
\begin{align*}
&(1, p-1) (2, p-2) \ldots (b, b+1),\\
&(1,p) (2, p-1) \ldots (b, b+2), \\
&(2, p-1) (3, p-2) \ldots (b, b+2).
\end{align*}
This finishes the proof for the first part,since these elements generate $Sym_p$, see \cite[Lemma 6]{m1}.  For the second part of the theorem, note that adding $\rho_3$ to the corresponding
generating set given in Theorem A, finishes the proof.
\end{proofb}

As a last observation, one can prove that Theorem~A also holds  for the cases $p=2$ or $p=3$.
In theses cases, the generating set of $\Gamma$ can be chosen as
\[
\begin{array}{lll}
\lbrace \rho_1,\rho_2,\rho_1C_{k-3}B_{k-1}A_k
A_{k+2}^{-1}B_{k+3}^{-1}C_{k+4}^{-1} \rbrace & \textrm{if} & g=2k\geq14,\\
\lbrace \rho_1,\rho_2,\rho_1C_{k-3}B_kA_{k+1}A_{k+2}^{-1}B_{k+3}^{-1}C_{k+5}^{-1} \rbrace & \textrm{if} & g=2k+1\geq13.\\
\lbrace \rho_1,\rho_2,\rho_2B_2A_3A_4^{-1}B_5^{-1},\rho_1C_{3}C_{4}^{-1} \rbrace & \textrm{if} & g=6.\\
\lbrace \rho_1,\rho_2,\rho_1A_{3}A_{4}^{-1},\rho_2A_2B_2C_2C_3^{-1}B_4^{-1}A_4^{-1} \rbrace & \textrm{if} & g=5.\\
\lbrace \rho_1,\rho_2,\rho_2B_1A_2A_3^{-1}B_4^{-1},\rho_1C_{2}C_{3}^{-1} \rbrace & \textrm{if} & g=4.\\
\lbrace \rho_1,\rho_2,\rho_1A_{2}A_{3}^{-1},\rho_2A_1B_1C_1C_2^{-1}B_3^{-1}A_3^{-1} \rbrace & \textrm{if} & g=3.\\
\end{array}.
\]
It can be easily proven that the group $\Gamma$ contains ${\rm Mod}_{0}(\Sigma_{g,p})$ by the similar arguments in the proofs of  lemmata~\ref{lemeven}--\ref{lem3}.
The element $\rho_1\rho_2 \in \Gamma$ has the image $(1,2,\ldots,p)\in Sym_p$. Hence, this element generates $Sym_p$ for $p=2$. If $p=3$, we distribute the punctures
as in ~ \cite[Figure~$1$]{ka}. Then the element $\rho_1$ has the image $(1,3)$, which generate $Sym_p$ together with the element $(1,2,3)$. Therefore, the group $\Gamma$
is mapped surjectively onto $Sym_p$ for $p=2,3$. One can conclude that the group $\Gamma$ is equal to ${\rm Mod}(\Sigma_{g,p})$.


\section{Introduction}
A linear \textbf{single change covering design} (\sccd($v,k,t,b$)) $(V,\mathcal{L})$ is a $v$-set $V$ and an ordered list of blocks $\mathcal{L}= (B_1,B_2,...,B_b)$ of size $k$  where every $t$-set, $T$, must occur in at least one block. Additionally each pair of consecutive blocks differs by exactly one element. A \textbf{circular singe change covering design} (CSCCD($v,k,t,b$)) is a \sccd ~where the first and last blocks also differ by one element. If no \dccd($v,k,t,b')$ exists for all $b' < b$ then a \dccd($v,k,t,b$) is called \textbf{{minimal}}

The earliest discussion of \sccd s was in 1968 and focused on applications to efficient computing \cite{Nelder}. The calculation of $AA^T$ for some matrix requires processing all pairs of rows. In 1968 a limited number of rows could be stored in core memory at one time and updating RAM from a tape was slow. Therefore, visiting all pairs with the smallest number of accesses to the tape improves running time significantly. Similar constraints apply today with respect to CPU cache v.s. RAM access \cite{Tape_Drive, Core_Memory}.

Gower, Preece, Constable, Zhang, Yucas, Wallis, McSorley and Phillips substantially developed the theory in the 1990s. For a summarized history please see \cite{Chafee_sccd} and \cite{inside}. Today we know constructions for all minimum designs of block size 2,3 and 4 as well as four classes modulo sixteen for block size 5. We also have difference constructions for circular \sccd ~for families with arbitrary $k$ \cite{Chafee_sccd}.

This previous research only considered changing a single element. This prompts the question,``Could we instead change other fixed numbers of elements between blocks". We call such a design an $m$-change covering design. When $m=2$, these are called \textbf{double change covering designs (DCCD)}. These designs would prove useful in component testing for balancing costs of both testing a configuration and changing the components between tests. Given enough known $m$-change designs, one may choose the most cost efficient testing method.

Preece et al. introduce the concept of linear double change covering designs and produce an example of a \dccd(9,3,2,12). Nirosh Gangoda Gamachchige and John McSorley begin a formal exploration of double change covering designs in Gangoda Gamachchige's M.Sc and Ph.D. these \cite{gangoda_gamachchige_double-change_2014, gangoda_gamachchige_double-change_2017}. In the M.Sc, Gangoda Gamachchige gives a construction for {\rm tight~CDCCD}($v,3,2,b$) developed using Bose and Skolem sequences on STS. He also gives constructions for {\rm CDCCD}($v,3,2,b$) when $v\equiv 0,2,4,5 \pmod{6}$. During his Ph.D. he examines the regularity of elements in a \dccd.
He finds that for a fixed $k$, linear \dccd($3k-5,k,2,2k-4)$ are minimal and if $2k-3=p^n$ for some prime $p\neq 2$, and $n\geq 1$ then $v-3k-5$ is the smallest $v$ where a linear \dccd($v,k,2,b)$ is minimal.
He shows fixed elements do not exist in economical linear \dccd($v,k,2,b)$ for $v\geq 3k-6$.
He shows that a minimal {\rm CDCCD}($v,k,2,b$) has a fixed element if and only if $v=2k-3$.
He shows all \dccd($v,2,2,b$) are minimal when $v\geq 6$
He shows there are no fixed elements in minimal \dccd($v,4,2,b$) for $v\geq 6$.
He constructs a minimal \dccd($v,4,2,b$) for $v=6,...,14$.
He gives some alternative constructions that take minimal {\rm CDCCD}($v,4,2,b)$ to minimal {\rm CDCCD}($v',4,2,b')$ and ends by giving some general constructions for {\rm CDCCD}($v,4,2,b$) that are not necessarily minimal.

In this paper we further explore linear and circular double change covering designs and discuss their constructions using expansion sets and 1-factorizations of complete graphs and difference families.

\section{Background}

We will be using some graph theory in this work.  A \textbf{{perfect matching} or {1-factor}} of a graph $G$ is a subset of edges $M$ such that every vertex $v\in V$ is adjacent to exactly one edge $e \in M$. A partition of the edges of a graph into perfect matchings is a \textbf{{1-factorization}}. Each color in Figure~\ref{Figure: tikz K_6 1-factor} is a 1-factor in a 1-factorization of $K_6$. A 1-factorization of $K_n$ exists for all even $n$\cite{Factors_and_Factorizations}.

\begin{figure}[H]
\begin{center}
\begin{tikzpicture}
    \graph[circular placement, radius=2cm,
           empty nodes, nodes={circle,draw}]
    {
     \foreach \x in {a,...,f} {
        \foreach \y in {\x,...,f} {
          \x -- \y;
        };
      };

    };

    \draw [-,cap=rect,line width=1mm,draw=orange] (a)--(d);
    \draw [-,cap=rect,line width=1mm,draw=orange] (b)--(f);
    \draw [-,cap=rect,line width=1mm,draw=orange] (e)--(c);

    \draw [-,cap=rect,line width=1mm,draw=magenta] (b)--(d);
    \draw [-,cap=rect,line width=1mm,draw=magenta] (a)--(c);
    \draw [-,cap=rect,line width=1mm,draw=magenta] (e)--(f);

    \draw [-,cap=rect,line width=1mm,draw=green] (c)--(d);
    \draw [-,cap=rect,line width=1mm,draw=green] (b)--(e);
    \draw [-,cap=rect,line width=1mm,draw=green] (a)--(f);

    \draw [-,cap=rect,line width=1mm,draw=black] (e)--(d);
    \draw [-,cap=rect,line width=1mm,draw=black] (a)--(b);
    \draw [-,cap=rect,line width=1mm,draw=black] (c)--(f);

    \draw [-,cap=rect,line width=1mm,draw=cyan] (f)--(d);
    \draw [-,cap=rect,line width=1mm,draw=cyan] (a)--(e);
    \draw [-,cap=rect,line width=1mm,draw=cyan] (b)--(c);

    \foreach \x [count=\idx from 0] in {a,...,f} {
      \pgfmathparse{90 + \idx * (360 /6)}
      \node at (\pgfmathresult:2.0cm) [circle,draw=black,fill=white, line width=0.75mm] {\x};
      };

    \end{tikzpicture}
    \end{center}
\caption{1-factorization of $K_6$}
\label{Figure: tikz K_6 1-factor
\end{figure}

Let $(G,+,0)$ be a finite group of order $v$. For $D\subseteq G$ let $\partial D = \{d_1-d_2 : d_1 \neq d_2 \in D\}$.
A  \textbf{($v,k,\lambda$)-{difference family}} is a collection $\{D_1,...,D_c\}$ of $k$-subsets of $G$, $|G|=v$, where $\partial D_1 \cup ... \cup \partial D_c=\lambda G\backslash\{0\}$. A difference family with $c=1$ is a $(v,k,\lambda)-${difference set}.

\begin{example} \label{Example: (7,3,1)-difference set} \label{Example: (13,3,1)-difference family}
$D= \{1,3,4\}$ is a (7,3,1)-difference set in $\mathbb{Z}_7$.

$D = \big\{\{0,1,4\}, \{0,2,8\}\big\}$ is a (13,3,1)-difference family over $\mathbb{Z}_{13}$.
\end{example}

\section{Double Change Covering Designs}

A \textbf{double change covering design} (\dccd($v,k,t,b$)) $(V,\mathcal{L})$ is a $v$-set $V$ and an ordered list of blocks $\mathcal{L}= (B_1,B_2,...,B_b)$ of size $k$  where every $t$-set must occur in at least one block. Each pair of consecutive blocks differs by exactly two elements. A \dccd~ is \textbf{circular} if the first and last blocks also differ by two elements. The double change property requires that $v\geq k+2$ if $b>1$. An element $x\in V$ is \textbf{introduced} in a block if $x\in B_i$ and $x \not\in B_{i-1}$. As no block precedes $B_1$ in a linear \dccd~ every element is introduced here. A $t$-set is \textbf{covered} in $B_i$ if at least one element in the $t$-set was introduced in $B_i$.

\sccd~ and \dccd~ can optimize costs in component testing \cite{sccd}. For example, consider testing a device where running a test will cost \$10 and swapping components between tests costs \$1. Using the covering design with 7 blocks, {(1,2,3), (1,4,7), (1,5,6), (3,5,7), (3,4,6), (2,4,5), (2,6,7)} would cost \$91 to run, a SCCD(7,3,2,10) would cost \$112, and a DCCD(7,3,2,7) would cost \$85. If instead, it costs \$1 to run a test and \$5 to switch components these tests cost \$112, \$67, and \$77 respectively. \cite{sccd}

\begin{theorem}
    There are at least $g_1(v,k,t)=\ceiling{\frac{\binom{v}{t}-\binom{k}{t}}{2\binom{k-2}{t-1}+\binom{k-2}{t-2}}}+1$ blocks in a linear \dccd~ and $g_2(v,k,t)=\ceiling{\frac{\binom{v}{t}}{2\binom{k-2}{t-1}+\binom{k-2}{t-2}}}$ blocks in a {\rm CDCCD}.
\end{theorem}
\begin{proof}
    The first block of a linear \dccd~ will cover $\binom{k}{t}$ $t$-sets. Every other block will have two elements introduced. The number of $t$-sets that contain $i$ of the two introduced elements and $t-i$ of the remaining $k-2$ points is $\binom{2}{i}\binom{k-2}{t-i}$. Hence $\sum\limits_{i=1}^{t}\binom{2}{i}\binom{k-2}{t-i}$ $t$-sets are introduced in each block after the first. There are $\binom{v}{t}$ $t$-sets to cover, so $\binom{v}{t}\leq \binom{k}{t}+(b-1)\bigg(\sum\limits_{i=1}^s \binom{2}{i}\binom{k-2}{t-i}\bigg)$. In the circular case, each block covers at most $\sum\limits_{i=1}^t\binom{2}{i}\binom{k-2}{t-i}$ and the calculation is similar.
\end{proof}

We will be focusing on strength $t=2$ designs for this paper so will drop the parameter $t$ and write \dccd($v,k,b$). If no \dccd($v,k,b')$ exists for all $b' < b$ then a \dccd($v,k,b$) is called \textbf{{minimal}}.  A (circular) \dccd($v,k,b$) is \textbf{{economical}} if it has $\ceiling{g'_1(v,k,2)}$ $\big(\ceiling{g'_2(v,k,2)}\big)$ blocks and \textbf{{tight}} if it is economical and $g_1(v,k,2)$ $\big(g_2(v,k,2)\big)$ is an integer. Any economical \dccd ~is minimum. In a tight \dccd ~every pair is covered exactly once. For some $v,k$ combinations tight \dccd ~can not exist because $g_1$ or $g_2$ do not have integer values, but economical designs can exist. An example of a {\rm CDCCD}(7,3,7) is given in Table~\ref{Table: dccd(7,3,2)}. The blocks are those of $STS(7)$. It is tight as either a \dccd ~or {\rm CDCCD}.

The elements $U_i = x \in B_i \cap B_{i+1}$ form the $i_{th}$ \textbf{unchanged subset}. Since no block proceeds $B_1$ or follows $B_b$ in linear \dccd~ we may consider any $k-2$ subset to be the unchanged subset $U_0$ and $U_b$ respectively. However, circular \dccd~ must maintain the double change between the first and last block, so $U_0=U_b= B_1 \cap B_b$ so we loose any free choice we had. For example the linear \dccd(7,3,7) has the unchanged subsets $U_1 = \{0\}, U_2 = \{4\}, U_3 = \{3\}, U_4 = \{6\}, U_5 = \{6\}, U_6 = \{5\}$ where $U_0$ can be any of $\{0\},\{1\},$ of $\{2\}$ and $U_7$ can be any of $\{1\},\{3\},$ or $\{5\}$. The {\rm CDCCD}(7,3,7) has the same $U_1,...,U_6$ however, $U_0 = U_7 =\{1\}$. If we can partition $V$ into a collection of unchanged subsets, we say the design has an \textbf{expansion set}. In Table~\ref{Table: dccd(7,3,2)}, only the linear \dccd(7,3,7) has an expansion set indicated by carrots, $\land$.

\begin{table}[H]
\centering
\begin{tabular}{lllllll}
\hspace{.5em}B$_1$    & B$_2$    & B$_3$    & B$_4$    & B$_5$    & B$_6$    & B$_7$    \\
\hspace{.5em}0$^*$ & 0     & 2$^*$ & 0$^*$ & 1$^*$ & 5$^*$ & 5     \\
\hspace{.5em}1 & 4$^*$ & 4     & 6$^*$ & 6     & 6     & 3$^*$ \\
$_{\land}$2$^*$$_{\land}$  & 5$^*$$_{\land}$ & 3$^*$$_{\land}$ & 3     & 4$^*$$_{\land}$ & 2$^*$$_{\land}$ & 1$^*$$_{\land}$
\end{tabular}
\caption{A {\rm tight~CDCCD}(7,3,7)}
\label{Table: dccd(7,3,2)}\label{Table: dccd(7,3,2,7)}
\end{table}

\subsection{Expansion Set Recursion}

Preece et al. use expansion sets to construct a \sccd($v+1,k,b$) from a \sccd($v,k,b$) \cite{tsccd}. This has been extended to CSCCD \cite{circular}. We can do something similar with double change covering designs by utilizing 1-factorizations of a complete graph.

\begin{theorem}\label{Theorem: dccd(v+1,k,2) increase}
Let $(V,\mathcal{B})$ be a \text{\dccd}($v,k,b$) with $v$ an odd multiple of $k-2$ and expansion set. Then a \dccd($v^*, k,b^*$), ($V^*,\mathcal{B}^*$) exists for $v^*=v+\frac{v}{k-2}+1$ and $b^*= b+\frac{v}{k-2}\frac{v+k-2}{2k-4}$. Moreover, if ($V,\mathcal{B}$) is tight, economic or circular then ($V^*,\mathcal{B}^*$) is too.
\end{theorem}

\begin{proof}
Let ($V,\mathcal{B})$ be a \dccd($v,k,b$) with the expansion set $\mathcal{E} = \{U_{i_j} : 1 \leq j \leq l = \frac{v}{k-2}\}$. Let $\{F_j\}_1^l$ be a 1-factorization of $K_{l+1}$ on set $X$ disjoint from $V$ \cite{Factors_and_Factorizations}.

For each edge $e\in F_j$ let $B_{j,e}= U_{i_j}\cup e$ for each $j$. Insert all the $B_{j,e}$ in any order at each expansion location ${i_j} \in \mathcal{E}$. These insertions maintain the double change property. All the pairs that were covered in $(V,\mathcal{B})$ are still covered in $\mathcal{B}$. Since each pair of elements from $X$ is in exactly one 1-factor all the pairs in $X$ are covered. The blocks inserted at expansion set locations ensure each pair of elements $\{x,y\}$, $x\in X$, $y\in V$ is covered. So $(V^*,\mathcal{B}^*)$ is a \dccd($v^*,k,b^*$) with $v^*v+\frac{v}{k-2}+1$ and $b^*=b+\frac{v(v+k-2)}{2(k-2)^2}$.

Each $B_{j,e}$ only covers new pairs and does not effect introductions in preexisting blocks, so if ($V,\mathcal{B}$) was tight or economical so is $(V^*,\mathcal{B}^*)$. The block insertions do not affect the double change between the first and last block, so if $(V,\mathcal{B})$ was circular so is ($V^*,\mathcal{B}^*$).
\end{proof}

For example consider the linear \dccd(7,3,7) and expansion set in Table~\ref{Table: dccd(7,3,2,7)}. We may insert four new blocks at each expansion set location that consist of the unchanged subset and the vertices of an edge in a 1-factor of $K_8$ in Figure~\ref{Figure: K8} to construct a \dccd(13,3,35) as seen in Table~\ref{Table: DCCD(15,3,2,3)}.

\begin{figure}[H]
    \centering
    \begin{tikzpicture}
        \node[circle,draw=black,fill=white,line width=0.75mm] (15) at (0:0) {15};
        \pgfmathparse{90 + (0 * (360 /7))}
        \node[{minimum size=8mm, circle,draw}] (8) at (\pgfmathresult:2.7) {8};
        \pgfmathparse{90 + (1 * (360 /7))}
        \node[{minimum size=8mm, circle,draw}] (9) at (\pgfmathresult:2.7) {9};
        \pgfmathparse{90 + (2 * (360 /7))}
        \node[{minimum size=8mm, circle,draw}] (10) at (\pgfmathresult:2.7) {10};
        \pgfmathparse{90 + (3 * (360 /7))}
        \node[{minimum size=8mm, circle,draw}] (11) at (\pgfmathresult:2.7) {11};
        \pgfmathparse{90 + (4 * (360 /7))}
        \node[{minimum size=8mm, circle,draw}] (12) at (\pgfmathresult:2.7) {12};
        \pgfmathparse{90 + (5 * (360 /7))}
        \node[{minimum size=8mm, circle,draw}] (13) at (\pgfmathresult:2.7) {13};
        \pgfmathparse{90 + (6 * (360 /7))}
        \node[{minimum size=8mm, circle,draw}] (14) at (\pgfmathresult:2.7) {14};

        {
        \draw [-,cap=rect,line width=1mm,draw=black] (8)--(9);
        \draw [-,cap=rect,line width=1mm,draw=black] (10)--(14);
        \draw [-,cap=rect,line width=1mm,draw=black] (11)--(13);
        \draw [-,cap=rect,line width=1mm,draw=black] (12)--(15);

        \draw [-,cap=rect,line width=1mm,draw=black] (8)--(10);
        \draw [-,cap=rect,line width=1mm,draw=black] (11)--(14);
        \draw [-,cap=rect,line width=1mm,draw=black] (12)--(13);
        \draw [-,cap=rect,line width=1mm,draw=black] (9)--(15);

        \draw [-,cap=rect,line width=1mm,draw=black] (8)--(11);
        \draw [-,cap=rect,line width=1mm,draw=black] (9)--(10);
        \draw [-,cap=rect,line width=1mm,draw=black] (12)--(14);
        \draw [-,cap=rect,line width=1mm,draw=black] (13)--(15);

        \draw [-,cap=rect,line width=1mm,draw=black] (8)--(15);
        \draw [-,cap=rect,line width=1mm,draw=black] (9)--(14);
        \draw [-,cap=rect,line width=1mm,draw=black] (10)--(13);
        \draw [-,cap=rect,line width=1mm,draw=black] (11)--(12);

        \draw [-,cap=rect,line width=1mm,draw=black] (8)--(12);
        \draw [-,cap=rect,line width=1mm,draw=black] (13)--(14);
        \draw [-,cap=rect,line width=1mm,draw=black] (9)--(11);
        \draw [-,cap=rect,line width=1mm,draw=black] (10)--(15);

        \draw [-,cap=rect,line width=1mm,draw=black] (8)--(13);
        \draw [-,cap=rect,line width=1mm,draw=black] (9)--(12);
        \draw [-,cap=rect,line width=1mm,draw=black] (10)--(11);
        \draw [-,cap=rect,line width=1mm,draw=black] (14)--(15);

        \draw [-,cap=rect,line width=1mm,draw=black] (8)--(14);
        \draw [-,cap=rect,line width=1mm,draw=black] (9)--(13);
        \draw [-,cap=rect,line width=1mm,draw=black] (10)--(12);
        \draw [-,cap=rect,line width=1mm,draw=black] (11)--(15);
        }

        {
        \draw [-,cap=rect,line width=1mm,draw=colour1] (8)--(9);
        \draw [-,cap=rect,line width=1mm,draw=colour1] (10)--(14);
        \draw [-,cap=rect,line width=1mm,draw=colour1] (11)--(13);
        \draw [-,cap=rect,line width=1mm,draw=colour1] (12)--(15);
        }

        {
        \draw [-,cap=rect,line width=1mm,draw=colour2] (8)--(10);
        \draw [-,cap=rect,line width=1mm,draw=colour2] (11)--(14);
        \draw [-,cap=rect,line width=1mm,draw=colour2] (12)--(13);
        \draw [-,cap=rect,line width=1mm,draw=colour2] (9)--(15);
        }

        {
        \draw [-,cap=rect,line width=1mm,draw=colour3] (8)--(11);
        \draw [-,cap=rect,line width=1mm,draw=colour3] (9)--(10);
        \draw [-,cap=rect,line width=1mm,draw=colour3] (12)--(14);
        \draw [-,cap=rect,line width=1mm,draw=colour3] (13)--(15);
        }

        {
        \draw [-,cap=rect,line width=1mm,draw=colour4] (8)--(15);
        \draw [-,cap=rect,line width=1mm,draw=colour4] (9)--(14);
        \draw [-,cap=rect,line width=1mm,draw=colour4] (10)--(13);
        \draw [-,cap=rect,line width=1mm,draw=colour4] (11)--(12);
        }

        {
        \draw [-,cap=rect,line width=1mm,draw=colour5] (8)--(12);
        \draw [-,cap=rect,line width=1mm,draw=colour5] (13)--(14);
        \draw [-,cap=rect,line width=1mm,draw=colour5] (9)--(11);
        \draw [-,cap=rect,line width=1mm,draw=colour5] (10)--(15);
        }

        {
        \draw [-,cap=rect,line width=1mm,draw=colour6] (8)--(13);
        \draw [-,cap=rect,line width=1mm,draw=colour6] (9)--(12);
        \draw [-,cap=rect,line width=1mm,draw=colour6] (10)--(11);
        \draw [-,cap=rect,line width=1mm,draw=colour6] (14)--(15);
        }

        {
        \draw [-,cap=rect,line width=1mm,draw=colour7] (8)--(14);
        \draw [-,cap=rect,line width=1mm,draw=colour7] (9)--(13);
        \draw [-,cap=rect,line width=1mm,draw=colour7] (10)--(12);
        \draw [-,cap=rect,line width=1mm,draw=colour7] (11)--(15);
        }

        \node[circle,draw=black,fill=white,line width=0.75mm] (15) at (0:0) {15};
        \foreach \x [count=\idx from 0] in {8,...,14} {
            \pgfmathparse{90 + (\idx * (360 /7))}
            \node at (\pgfmathresult:2.7 cm) [circle,draw=black,fill=white, minimum size=8mm,line width=0.75mm] {\x};
        };

    \end{tikzpicture}
\caption{K$_8$}
\label{Figure: K8}
\end{figure}

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{.5\tabcolsep}
    \begin{tabular}{llllllllllllllllll}

    \tiny{B$_1$} & \tiny{B$_{2}$} & \tiny{B$_{3}$} & \tiny{B$_{4}$} & \tiny{B$_{5}$} & \tiny{B$_{6}$} & \tiny{B$_{7}$} & \tiny{B$_{8}$} & \tiny{B$_{9}$}  & \tiny{B$_{10}$}  & \tiny{B$_{11}$} & \tiny{B$_{12}$} & \tiny{B$_{13}$} & \tiny{B$_{14}$} & \tiny{B$_{15}$} & \tiny{B$_{16}$} & \tiny{B$_{17}$} & \tiny{B$_{18}$}
    \\

    \textcolor{colour1}{8} & \textcolor{colour1}{10} & \textcolor{colour1}{11} & \textcolor{colour1}{12} & 0$^*$
    & {0}  & {0}  & {0}  & {0} & 0
    & \textcolor{colour3}{8}  & \textcolor{colour3}{9}  & \textcolor{colour3}{12} & \textcolor{colour3}{13} & 2$^*$
    & \textcolor{colour4}{8}  & \textcolor{colour4}{9} & \textcolor{colour4}{10} \\

    \textcolor{colour1}{9} & \textcolor{colour1}{14} & \textcolor{colour1}{13} & \textcolor{colour1}{15} & 1$^*$
    & \textcolor{colour2}{8}  & \textcolor{colour2}{11} & \textcolor{colour2}{12} & \textcolor{colour2}{9} & 4$^*$
    & {4}  & {4}  & {4} & {4}  & 4
    &\textcolor{colour4}{15} & \textcolor{colour4}{14} & \textcolor{colour4}{13}
     \\

    {2} & {2}  & {2}  & {2} & 2
    & \textcolor{colour2}{10} & \textcolor{colour2}{14} & \textcolor{colour2}{13} & \textcolor{colour2}{15} & 5$^*$
    & \textcolor{colour3}{11} & \textcolor{colour3}{10} & \textcolor{colour3}{14} & \textcolor{colour3}{15} & 3$^*$
    & {3}  & {3} & {3}
    \\ \hline

    \tiny{B$_{19}$} & \tiny{B$_{20}$} & \tiny{B$_{21}$}  & \tiny{B$_{22}$} & \tiny{B$_{23}$} & \tiny{B$_{24}$} & \tiny{B$_{25}$} & \tiny{B$_{26}$} & \tiny{B$_{27}$} & \tiny{B$_{28}$} & \tiny{B$_{29}$} & \tiny{B$_{30}$} & \tiny{B$_{31}$} & \tiny{B$_{32}$} & \tiny{B$_{33}$} & \tiny{B$_{34}$} & \tiny{B$_{35}$} \\

    \textcolor{colour4}{11} & 0$^*$ & 1$^*$
    & \textcolor{colour5}{8}  & \textcolor{colour5}{13} & \textcolor{colour5}{9}  & \textcolor{colour5}{10} & 5$^*$
    & {5}  & {5}  & {5}  & {5} & 5
    & \textcolor{colour7}{8}  & \textcolor{colour7}{9}  & \textcolor{colour7}{10} & \textcolor{colour7}{11} \\

    \textcolor{colour4}{12} & 6$^*$ & 6
    & {6}  & {6}  & {6} & {6} & 6
    & \textcolor{colour6}{8}  & \textcolor{colour6}{9}  & \textcolor{colour6}{10} & \textcolor{colour6}{14} & 3$^*$
    & \textcolor{colour7}{14} & \textcolor{colour7}{13} & \textcolor{colour7}{12} & \textcolor{colour7}{15} \\

    {3}  & 3 & 4$^*$
    & \textcolor{colour5}{12} & \textcolor{colour5}{14} & \textcolor{colour5}{11} & \textcolor{colour5}{15} & 2$^*$
    & \textcolor{colour6}{13} & \textcolor{colour6}{12} & \textcolor{colour6}{11} & \textcolor{colour6}{15} & 1$^*$
    & {1}  & {1}  & {1}  & {1}

    \end{tabular}
    \caption{A \dccd(15,3,35) built from the \dccd(7,3,2) and $K_8$}
    \label{Table: DCCD(15,3,2,3)}\label{Table: DCCD(15,3,2,35)} \label{Table: DCCD(15,3,35}
\end{table}

We note that every new element $x\in X \backslash V$ in Theorem~\ref{Theorem: dccd(v+1,k,2) increase} is always removed one block after it is introduced. Consequently, $x$ is never in an unchanged subset so $\mathcal{B}^*$ never has an expansion set.

\subsection{Difference Methodology}

We can construct {\rm CDCCD}($v,k,b$) using a construction similar to difference sets and families. McSorley proved that $\{0,1,...,k-1\}$ is a base block of a CSCCD$(2k-1,k,2k-1)$ over $\mathbb{Z}_{2k-1}$ in \cite{circular}. This theorem is not stated in terms of difference methods but is equivalent to a difference method construction. In \cite{Chafee_sccd} we use difference methods to construct tight~CSCCD$(2c(k-1)+1,k,c^2 (2 k - 2) + c + 1)$ for all $c\geq 1, k\geq 2$. Here we extend these methods to {\rm CDCCD}.

Every element in the tight~CSCCD$(2k'-1,k',2k'-1)$ is introduced exactly once. If we replace $x\in \mathbb{Z}_{2k'-1}$ in each block with $2x$ and $2x+1$ in $\mathbb{Z}_{4k'-2}$ to produce a list of $2k'-1$ blocks $B_i$ of size $k=2k'$ from $\mathbb{Z}_{2k-2}$ the design is double change. The pairs $\{2x,2x+1\}$ are covered when introduced other pairs $\{y,z\} \subset \mathbb{Z}_{2k-2}$  are covered in the block where $\{\floor{\frac{y}{2}},\floor{\frac{z}{2}}\}$ are covered in the CSCCD. Thus,

\begin{theorem}\label{Theorem: tdcccd(4k-2,2k,2,2k-1) exist}
\label{Theorem: tdcccd(4k-2,2k,2k-1) exist}
\label{Theorem: tdcccd(2k-2,k,2,k-1) exist, k=2k'}
\label{Theorem: tdcccd(2k-2,k,k-1) exist, k=2k'}
A {\rm tight~CDCCD}$(2k-2,k,k-1)$ exists for all $k\geq 2$ if and only if $k$ is even.
\end{theorem}
\begin{proof}
Suppose that $k$ is odd, then $g_2(2k-1,k,2)=\ceiling{\frac{\binom{2k-2}{2}}{2\binom{k-2}{1}+\binom{k-2}{0}}}=k-1$. The discussion before this Theorem constructs these for $k$ even. We know show that $k$ odd cannot exist. Suppose there exists a point, $x$, in every block. There are $2(k-1)=v$ introductions so at least one point $y$ is introduced at least twice, so the pair $x,y$ is covered more then once, a contradiction to tightness. So no point may be in every block. However, there are not enough introductions for any point to be introduced more then once, so each point is introduced exactly once.

When a point is introduced it covers $k-1$ pairs and each time it persists it covers $2$ more pairs. Thus each point is in $r$ blocks where $k-1+(r-1)2\geq v-1$ so we find $r\geq \frac{k-2}{2}$. Now when $r$ is odd, $r\geq \ceiling{\frac{k-2}{2}}$ which forces repeated pairs, a contradiction. Thus tight~CSCCD(2k-2,k,k-1) do not exist when $k$ is odd.
\end{proof}
For example the {\rm tight~CDCCD}(6,4,3) in Table~\ref{Table: tdcccd(6,4,2,3)} is constructed from the tight~CSCCD(3,2,3) to its left.

\begin{table}[H]
\centering
\begin{tabular}{llllllllll}
B'$_1$ & B'$_2$ & B'$_3$   &&&&&B$_1$ & B$_2$ & B$_3$\\
0 & 2$^*$ &2            &&&&& 0 & 4$^*$ & 4 \\
1$^*$ & 1 & 0$^*$       &&&&&  1 & 5$^*$ & 5 \\
&&&&&&&                        2$^*$ & 2 & 0$^*$ \\
&&&&&&&                        3$^*_{\land}$ & 3$_{\land}$ & 1$^*_{\land}$
\end{tabular}
\caption{A tight~CSCCD(3,2,3) and tight~CSCCD(6,4,3)}
\label{tdcccd(6,4,2,3)}
\label{Table: tdcccd(6,4,2,3)} \label{Table: tscccd(3,2,2,3)}
\end{table}

\begin{proposition}
A {\rm CDCCD}($2k-2,k,k-1)$ has an expansion set if and only if $k=4$.
\end{proposition}
\begin{proof}
We have $v=2k-2=2(k-2)+2$, so $(k-2)|v$ if and only if $k=3,4$. When $k=3$ the \dccd~ cannot exist as $k$ is odd. When $k=4$ the {\rm CDCCD}(6,4,3) has an expansion set as shown in Table~\ref{Table: tdcccd(6,4,2,3)}.
\end{proof}

Using this in conjunction with the 1-factorization of $K_4$ on points $\{a,b,c,d\}$ and Theorem~\ref{Theorem: dccd(v+1,k,2) increase} we build the {\rm CDCCD}(10,4,9) seen in Table~\ref{Table: tdcccd(10,4,2,9)}.

\begin{table}[H]
\centering
\begin{tabular}{lllllllll}
0 & a$^*$ & c$^*$ & 4$^*$ & 4 & 4 & 4 & a$^*$ & b$^*$ \\
1 & b$^*$ & d$^*$ & 5$^*$ & 5 & 5 & 5 & d$^*$ & c$^*$ \\
2$^*$ & 2 & 2 & 2 & a$^*$ & b$^*$ & 0$^*$ & 0 & 0 \\
3$^*$ & 3 & 3 & 3 & c$^*$ & d$^*$ & 1$^*$ & 1 & 1
\end{tabular}
\caption{A {\rm tight~CDCCD}(10,4,9)}
\label{tdcccd(10,4,2,9)}
\label{Table: tdcccd(10,4,2,9)}
\end{table}

Adding a single new point to every block in the \dccd ~constructed in Theorem~\ref{Theorem: tdcccd(4k-2,2k,2k-1) exist} yields

\begin{theorem}
A {\rm tight~CDCCD}$(2k-3,k,k-2)$ exists for all odd $k\geq 3$.
\end{theorem}

Beyond manipulating the CSCCD ~by doubling elements, we can directly construct difference sets for {\rm CDCCD}. Example~\ref{Example: dcccd(10,4,9), c=1} will help us gain some intuition for doing this.

\begin{example}\label{Example: dcccd(10,4,9), c=1}
Consider a {\rm CDCCD}(11,4,11). In Figure~\ref{Figure: K11} we show a base block $\{0,1,2,5\}$ and its successor after incrementing by $1$. The vertices only in the first block are highlighted in blue, the vertices only on the second block are highlighted in pink, and the vertices in the unchanged subset in black. We place a line between each introduced element and the other elements in the block, blue for the first block and pink for the second; these are the covered pairs and every difference in $\mathbb{Z}_{11}$ appears. Each subsequent block is obtained by rotating the previous block by one. After developing the blocks fully in $\mathbb{Z}_{11}$ all pairs will be covered. We also see pictorially that there will be double changes between consecutive blocks. Table~\ref{Table: dcccd(11,4,2,11)} shows the table form the {\rm CDCCD}(11,4,11).

\begin{figure}[H]
    \centering
    \begin{tikzpicture}
        \pgfmathparse{90 + (0 * (360 /11))}
        \node[{minimum size=1mm, circle,draw}] (0) at (\pgfmathresult:2.7) {0};
        \pgfmathparse{90 + (10 * (360 /11))}
        \node[{minimum size=1mm, circle,draw}] (1) at (\pgfmathresult:2.7) {1};
        \pgfmathparse{90 + (9 * (360 /11))}
        \node[{minimum size=1mm, circle,draw}] (2) at (\pgfmathresult:2.7) {2};
        \pgfmathparse{90 + (8 * (360 /11))}
        \node[{minimum size=1mm, circle,draw}] (3) at (\pgfmathresult:2.7) {3};
        \pgfmathparse{90 + (7 * (360 /11))}
        \node[{minimum size=1mm, circle,draw}] (4) at (\pgfmathresult:2.7) {4};
        \pgfmathparse{90 + (6 * (360 /11))}
        \node[{minimum size=1mm, circle,draw}] (5) at (\pgfmathresult:2.7) {5};
        \pgfmathparse{90 + (5 * (360 /11))}
        \node[{minimum size=1mm, circle,draw}] (6) at (\pgfmathresult:2.7) {6};
        \pgfmathparse{90 + (4 * (360 /11))}
        \node[{minimum size=1mm, circle,draw}] (7) at (\pgfmathresult:2.7) {7};
        \pgfmathparse{90 + (3 * (360 /11))}
        \node[{minimum size=1mm, circle,draw}] (8) at (\pgfmathresult:2.7) {8};
        \pgfmathparse{90 + (2 * (360 /11))}
        \node[{minimum size=1mm, circle,draw}] (9) at (\pgfmathresult:2.7) {9};
        \pgfmathparse{90 + (1 * (360 /11))}
        \node[{minimum size=1mm, circle,draw}] (10) at (\pgfmathresult:2.7) {\tiny{10}};

        \draw [-,cap=rect,line width=0.3mm,draw=cyan] (0)--(2);
        \draw [-,cap=rect,line width=0.3mm,draw=cyan] (0)--(5);
        \draw [-,cap=rect,line width=0.3mm,draw=cyan] (1)--(2);
        \draw [-,cap=rect,line width=0.3mm,draw=cyan] (1)--(5);
        \draw [-,cap=rect,line width=0.3mm,draw=cyan] (2)--(5);

        \draw [-,cap=rect,line width=0.3mm,draw=magenta] (1)--(3);
        \draw [-,cap=rect,line width=0.3mm,draw=magenta] (1)--(6);
        \draw [-,cap=rect,line width=0.3mm,draw=magenta] (2)--(3);
        \draw [-,cap=rect,line width=0.3mm,draw=magenta] (2)--(6);
        \draw [-,cap=rect,line width=0.3mm,draw=magenta] (3)--(6);

        {
        \pgfmathparse{90 + (0 * (360 /11))}
        \node[{minimum size=1mm, circle, draw, fill=black, text=white}] (0) at (\pgfmathresult:2.7) {0};
        \pgfmathparse{90 + (10 * (360 /11))}
        \node[{minimum size=1mm, circle, draw, fill=black, text=white}] (1) at (\pgfmathresult:2.7) {1};
        \pgfmathparse{90 + (9 * (360 /11))}
        \node[{minimum size=1mm, circle, draw, fill=cyan, text=white}] (2) at (\pgfmathresult:2.7) {2};
        \pgfmathparse{90 + (6 * (360 /11))}
        \node[{minimum size=1mm, circle, draw, fill=cyan, text=white}] (5) at (\pgfmathresult:2.7) {5};
        }
        {
        \pgfmathparse{90 + (0 * (360 /11))}
        \node[{minimum size=1mm, circle, draw, fill=cyan, text=white}] (0) at (\pgfmathresult:2.7) {0};
        \pgfmathparse{90 + (6 * (360 /11))}
        \node[{minimum size=1mm, circle, draw, fill=cyan, text=white}] (5) at (\pgfmathresult:2.7) {5};
        \pgfmathparse{90 + (10 * (360 /11))}
        \node[{minimum size=1mm, circle, draw, fill=black, text=white}] (1) at (\pgfmathresult:2.7) {1};
        \pgfmathparse{90 + (9 * (360 /11))}
        \node[{minimum size=1mm, circle, draw, fill=black, text=white}] (2) at (\pgfmathresult:2.7) {2};
        \pgfmathparse{90 + (8 * (360 /11))}
        \node[{minimum size=1mm, circle, draw, fill=magenta, text=white}] (3) at (\pgfmathresult:2.7) {3};
        \pgfmathparse{90 + (5 * (360 /11))}
        \node[{minimum size=1mm, circle, draw, fill=magenta, text=white}] (6) at (\pgfmathresult:2.7) {6};
        }

    \end{tikzpicture}
\caption{Difference construction for \dccd(11,4,11)}
\label{Figure: K11}
\end{figure}

\end{example}

\begin{table}[H]
    \centering
    \begin{tabular}{lllllllllll}
    \small{B$_1$} & \small{B$_{2}$} & \small{B$_{3}$} & \small{B$_{4}$} & \small{B$_{5}$} & \small{B$_{6}$} & \small{B$_{7}$} & \small{B$_{8}$} & \small{B$_{9}$}  & \small{B$_{10}$}  & \small{B$_{11}$} \\
    0 & 3$^*$ & 3 & 3 & 6$^*$ & 6  & 6 & 9$^*$ & 9  & 9  & 1$^*$  \\
    1 & 1 & 4$^*$ & 4 & 4 & 7$^*$  & 7 & 7 & 10$^*$ & 10 & 10 \\
    2$^*$ & 2 & 2 & 5$^*$ & 5 & 5  & 8$^*$ & 8 & 8  & 0$^*$  & 0  \\
    5$^*$ & 6$^*$ & 7$^*$ & 8$^*$ & 9$^*$ & 10$^*$ & 0$^*$ & 1$^*$ & 2$^*$  & 3$^*$  & 4$^*$
    \end{tabular}
    \caption{A {\rm CDCCD}(11,4,11) }
    \label{Table: DCCCD(11,4,2,11)}\label{Table: dcccd(11,4,2,11)}\label{Table: dcccd(11,4,11)}
\end{table}

We can construct difference families with up to $5$ base blocks for all $k$.

\begin{theorem}[{\rm CDCCD}~ difference families with $c$ initial blocks]
\label{Theorem: Initial c blocks for all k >= 3}

A {\rm tight~CDCCD}$(c(4k-6)+1,k,c^2(4k-6)+c)$ exists for all $k\geq 3$ when $c \leq 5$
\end{theorem}

\begin{proof}
To build each of the {\rm tight~CDCCD}$(c(4k-6)+1,k,c^2(4k-6)+c)$, let $A= \{0,1,...,(k-3)\}$ and consider the initial blocks labeled $B_{0,1},...,B_{0,c}$ in order, given in Table~\ref{Table: initial blocks for dcccd(c(4k-6)+1,k,c^2(4k-6)+c)}.

\begin{table}[H]
    \centering
    \begin{tabular}{|l|l|}
        \hline
        \textbf{$c$} & \textbf{Initial Blocks} \\ \hline

        1 & $A \cup \{(k-2),2(k-2)+1\}$               \\ \hline
        2 & $A \cup \{2(k-2),5(k-2)+2\}, A \cup \{(k-2),3(k-2)+1\}$               \\ \hline

        3 & $A \cup \{2(k-2),7(k-2)+3\}, A \cup \{3(k-2)+1,5(k-2)+2\},$ \\ & $A \cup \{(k-2),4(k-2)+2\}$              \\ \hline

        4 & $ A \cup \{2(k-2),8(k-2)+4\},
        A \cup \{3(k-2)+1,5(k-2)+2\},$ \\ & $
        A \cup \{4(k-2)+2,7(k-2)+4\},
        A \cup \{(k-2),6(k-2)+3\}$    \\ \hline

        5 & $ A \cup \{2(k-2),6(k-2)+3\},
        A \cup \{3(k-2)  , 9(k-2)+4\},$ \\ & $
        A \cup \{4(k-2)+2, 7(k-2)+4\},
        A \cup \{5(k-2)+3, 8(k-2)+4\},$ \\ & $
        A \cup \{ (k-2)  ,10(k-2)+5\}$      \\ \hline

    \end{tabular}
    \caption{Families of base blocks for {\rm CDCCD}}
    \label{Table: initial blocks for dcccd(c(4k-6)+1,k,c^2(4k-6)+c)}
\end{table}

Each block contains $A$ in addition to two distinct elements. Additionally, $B_{0,c}$ contains $A \cup \{(k-2)\}$, which contains $A$ incremented by 1, thus $(B_{0,1},B_{0,2},...,B_{0,c}, B_{1,1},...,B_{1,c},...,B_{v,c})$ is double change.

Each $B_{0,i}= \{0,1,...,k-3,x,y\}$ covers differences $\pm \{y-x,x-k+3,...,x,y-k+3,...,y\}$, which will cover all the differences $\mathbb{Z}_{v}$. Developing in $\mathbb{Z}_v$ covers all pairs.
\end{proof}

Example~\ref{Example: dcccd(10,4,9), c=1} is an example of Theorem~\ref{Theorem: Initial c blocks for all k >= 3} when $c=1$ and $k=4$. Let us examine what happens when $c=2$.

\begin{example}\label{Example: dcccd(21,4,42) when c=2}
When $k=4$ and $c=2$ we construct the {\rm tight~CDCCD}(21,4,42) in Table~\ref{Table: tdcccd(21,4,2,42) highlighted}. In this Table we highlight every $x\in X$ such that the pair $(0,x)$ is covered.

\begin{table}[H]
\centering
\setlength{\tabcolsep}{.5\tabcolsep}
\begin{tabular}{lllllllllllllllllllll}
\small{B}\tiny{$_{0,1}$} & \small{B}\tiny{$_{0,2}$} & \small{B}\tiny{$_{1,1}$} & \small{B}\tiny{$_{1,2}$} & \small{B}\tiny{$_{2,1}$} & \small{B}\tiny{$_{2,2}$} & \small{B}\tiny{$_{3,1}$} & \small{B}\tiny{$_{3,2}$} & \small{B}\tiny{$_{4,1}$} & \small{B}\tiny{$_{4,2}$} & \small{B}\tiny{$_{5,1}$} & \small{B}\tiny{$_{5,2}$} & \small{B}\tiny{$_{6,1}$} & \small{B}\tiny{$_{6,2}$} \\

{0}      & {0}      & {5$^*$}  & {3$^*$}  & {3}      & {3}      & {3}      & {3}      & {8$^*$}  & {6$^*$}  & {6}      & {6}      & {6}      & {6}      \\
{1}      & {1}      & {1}      & {1}      & {6$^*$}  & {4$^*$}  & {4}      & {4}      & {4}      & {4}      & {9$^*$}  & {7$^*$}  & {7}      & {7}      \\
\textcolor{cyan}{4$^*$}  & \textcolor{cyan}{2$^*$}  & {2}      & {2}      & {2}      & {2}      & {7$^*$}  & {5$^*$}  & {5}      & {5}      & {5}      & {5}      & {10$^*$} & {8$^*$}  \\
\textcolor{cyan}{12$^*$} & \textcolor{cyan}{7$^*$}  & {13$^*$} & {8$^*$}  & {14$^*$} & {9$^*$}  & {15$^*$} & {10$^*$} & {16$^*$} & {11$^*$} & {17$^*$} & {12$^*$} & {18$^*$} & {13$^*$} \\
\hline

\small{B}\tiny{$_{7,1}$} & \small{B}\tiny{$_{7,2}$} & \small{B}\tiny{$_{8,1}$} & \small{B}\tiny{$_{8,2}$} & \small{B}\tiny{$_{9,1}$} & \small{B}\tiny{$_{9,2}$} & \small{B}\tiny{$_{10,1}$} & \small{B}\tiny{$_{10,2}$} & \small{B}\tiny{$_{11,1}$} & \small{B}\tiny{$_{11,2}$} & \small{B}\tiny{$_{12,1}$} & \small{B}\tiny{$_{12,2}$} & \small{B}\tiny{$_{13,1}$} & \small{B}\tiny{$_{13,2}$} \\
{11$^*$} & {9$^*$}  & {9}      & {9}      & \textcolor{cyan}{9}      & {9}      & {14$^*$} & {12$^*$} & {12}     & {12}     & {12}     & {12}     & {17$^*$} & {15$^*$} \\

{7}      & {7}      & {12$^*$} & {10$^*$} & \textcolor{cyan}{10}     & {10}     & {10}     & {10}     & {15$^*$} & {13$^*$} & {13}     & {13}     & {13}     & {13}     \\

{8}      & {8}      & {8}      & {8}      & \textcolor{cyan}{13$^*$} & {11$^*$} & {11}     & {11}     & {11}     & {11}     & {16$^*$} & {14$^*$} & {14}     & {14}     \\

{19$^*$} & {14$^*$} & {20$^*$} & {15$^*$} & {0$^*$}  & {16$^*$} & {1$^*$}  & {17$^*$} & {2$^*$}  & {18$^*$} & {3$^*$}  & {19$^*$} & {4$^*$}  & {20$^*$} \\
\hline

\small{B}\tiny{$_{14,1}$} & \small{B}\tiny{$_{14,2}$} & \small{B}\tiny{$_{15,1}$} & \small{B}\tiny{$_{15,2}$} & \small{B}\tiny{$_{16,1}$} & \small{B}\tiny{$_{16,2}$} & \small{B}\tiny{$_{17,1}$} & \small{B}\tiny{$_{17,2}$} & \small{B}\tiny{$_{18,1}$} & \small{B}\tiny{$_{18,2}$} & \small{B}\tiny{$_{19,1}$} & \small{B}\tiny{$_{19,2}$} & \small{B}\tiny{$_{20,1}$} & \small{B}\tiny{$_{20,2}$} \\

{15}     & \textcolor{cyan}{15}     & {15}     & {15}     & {20$^*$} & {18$^*$} & \textcolor{cyan}{18}     & {18}     & {18}     & {18}     & {2$^*$}  & {0$^*$}  & {0}      & {0}      \\
{18$^*$} & \textcolor{cyan}{16$^*$} & {16}     & {16}     & {16}     & {16}     & {0$^*$}  & {19$^*$} & {19}     & {19}     & {19}     & \textcolor{cyan}{19}     & \textcolor{cyan}{3$^*$}  & \textcolor{cyan}{1$^*$}  \\
{14}     & \textcolor{cyan}{14}     & {19$^*$} & {17$^*$} & {17}     & {17}     & \textcolor{cyan}{17}     & {17}     & {1$^*$}  & {20$^*$} & {20}     & \textcolor{cyan}{20}     & {20}     & {20}     \\
{5$^*$}  & {0$^*$}  & {6$^*$}  & {1$^*$}  & {7$^*$}  & {2$^*$}  & \textcolor{cyan}{8$^*$}  & {3$^*$}  & {9$^*$}  & {4$^*$}  & {10$^*$} & \textcolor{cyan}{5$^*$}  & \textcolor{cyan}{11$^*$} & \textcolor{cyan}{6$^*$}
\end{tabular}
\caption{A Tight {\rm CDCCD}(21,4,2,42)}
\label{tdcccd(21,4,2,42)}
\label{Table: tdcccd(21,4,2,42)}
\label{tdcccd(21,4,2,42) highlighted}
\label{Table: tdcccd(21,4,2,42) highlighted}
\end{table}
\end{example}

\begin{example} \label{Example: dcccd(13,3,2,26) pictorially}
We may also visualize
multiple base blocks pictorially as we did in Example~\ref{Example: dcccd(10,4,9), c=1}. Consider the base blocks $\{0,1,4\}$ and $\{0,2,7\}$ of a {\rm tight~CDCCD}(13,3,26). These blocks are highlighted light blue and dark blue respectively in Figure~\ref{Figure: tdcccd(13,3,2,26)} and the unchanged subset is highlighted black. All differences are covered in these two blocks, and in any two consecutive blocks. Figure~\ref{Figure: dcccd(13,3,2,26) Step 2} shows how we increment Figure~\ref{Figure: dcccd(13,3,2,26) Step 1} by one to move from block 1 to block 3. The light blue highlighting $B_1$ is incremented by 1 to form the light red $B_3$.

\begin{figure}[H]
    \centering
    \begin{tikzpicture}
        \pgfmathparse{90 + (0 * (360 /13))}
        \node[{minimum size=1mm, circle,draw}] (0) at (\pgfmathresult:2.65) {};
        \pgfmathparse{90 + (12 * (360 /13))}
        \node[{minimum size=1mm, circle,draw}] (1) at (\pgfmathresult:2.65) {};
        \pgfmathparse{90 + (11 * (360 /13))}
        \node[{minimum size=1mm, circle,draw}] (2) at (\pgfmathresult:2.65) {};
        \pgfmathparse{90 + (10 * (360 /13))}
        \node[{minimum size=1mm, circle,draw}] (3) at (\pgfmathresult:2.65) {};
        \pgfmathparse{90 + (9 * (360 /13))}
        \node[{minimum size=1mm, circle,draw}] (4) at (\pgfmathresult:2.65) {};
        \pgfmathparse{90 + (8 * (360 /13))}
        \node[{minimum size=1mm, circle,draw}] (5) at (\pgfmathresult:2.65) {};
        \pgfmathparse{90 + (7 * (360 /13))}
        \node[{minimum size=1mm, circle,draw}] (6) at (\pgfmathresult:2.65) {};
        \pgfmathparse{90 + (6 * (360 /13))}
        \node[{minimum size=1mm, circle,draw}] (7) at (\pgfmathresult:2.65) {};
        \pgfmathparse{90 + (5 * (360 /13))}
        \node[{minimum size=1mm, circle,draw}] (8) at (\pgfmathresult:2.65) {};
        \pgfmathparse{90 + (4 * (360 /13))}
        \node[{minimum size=1mm, circle,draw}] (9) at (\pgfmathresult:2.65) {};
        \pgfmathparse{90 + (3 * (360 /13))}
        \node[{minimum size=1mm, circle,draw}] (10) at (\pgfmathresult:2.65) {};
        \pgfmathparse{90 + (2 * (360 /13))}
        \node[{minimum size=1mm, circle,draw}] (11) at (\pgfmathresult:2.65) {};
        \pgfmathparse{90 + (1 * (360 /13))}
        \node[{minimum size=1mm, circle,draw}] (12) at (\pgfmathresult:2.65) {};

        \draw [-,cap=rect,line width=0.3mm,draw=cyan] (0)--(1);
        \draw [-,cap=rect,line width=0.3mm,draw=cyan] (0)--(4);
        \draw [-,cap=rect,line width=0.3mm,draw=cyan] (1)--(4);

        \draw [-,cap=rect,line width=0.3mm,draw=blue] (0)--(2);
        \draw [-,cap=rect,line width=0.3mm,draw=blue] (0)--(7);
        \draw [-,cap=rect,line width=0.3mm,draw=blue] (2)--(7);

        \foreach \x [count=\idx from 0] in {12,...,0} {
            \pgfmathparse{90 + ((\idx+1) * (360 /13))}
            \node at (\pgfmathresult:2.8 cm) [circle,draw=black,fill=white, minimum size=1mm,line width=0.2mm] {\x};
        };

        \pgfmathparse{90 + (0 * (360 /13))}
        \node[{minimum size=1mm, circle, draw, fill=cyan, text=white}] (0) at (\pgfmathresult:2.8) {0};
        \pgfmathparse{90 + (12 * (360 /13))}
        \node[{minimum size=1mm, circle, draw, fill=black, text=white}] (1) at (\pgfmathresult:2.8) {1};
        \pgfmathparse{90 + (9 * (360 /13))}
        \node[{minimum size=1mm, circle, draw, fill=cyan, text=white}] (4) at (\pgfmathresult:2.8) {4};

        \pgfmathparse{90 + (0 * (360 /13))}
        \node[{minimum size=1mm, circle, draw, fill=black, text=white}] (0) at (\pgfmathresult:2.8) {0};
        \pgfmathparse{90 + (12 * (360 /13))}
        \node[{minimum size=1mm, circle, draw, fill=cyan, text=white}] (1) at (\pgfmathresult:2.8) {1};
        \pgfmathparse{90 + (9 * (360 /13))}
        \node[{minimum size=1mm, circle, draw, fill=cyan, text=white}] (4) at (\pgfmathresult:2.8) {4};
        \pgfmathparse{90 + (11 * (360 /13))}
        \node[{minimum size=1mm, circle, draw, fill=blue, text=white}] (2) at (\pgfmathresult:2.8) {2};
        \pgfmathparse{90 + (6 * (360 /13))}
        \node[{minimum size=1mm, circle, draw, fill=blue, text=white}] (7) at (\pgfmathresult:2.8) {7};

    \end{tikzpicture}
\caption{$c=2$, $k=3$ {\rm tight~CDCCD}(13,3,2,26) initial blocks $B_1$ and $B_2$}
\label{Figure: dcccd(13,3,2,26) Step 1}\label{Figure: dcccd(13,3,2,26)} \label{Figure: tdcccd(13,3,2,26)}
\end{figure}

\begin{figure}[H]
    \centering
    \begin{tikzpicture}
        \pgfmathparse{90 + (0 * (360 /13))}
        \node[{minimum size=1mm, circle,draw}] (0) at (\pgfmathresult:2.65) {};
        \pgfmathparse{90 + (12 * (360 /13))}
        \node[{minimum size=1mm, circle,draw}] (1) at (\pgfmathresult:2.65) {};
        \pgfmathparse{90 + (11 * (360 /13))}
        \node[{minimum size=1mm, circle,draw}] (2) at (\pgfmathresult:2.65) {};
        \pgfmathparse{90 + (10 * (360 /13))}
        \node[{minimum size=1mm, circle,draw}] (3) at (\pgfmathresult:2.65) {};
        \pgfmathparse{90 + (9 * (360 /13))}
        \node[{minimum size=1mm, circle,draw}] (4) at (\pgfmathresult:2.65) {};
        \pgfmathparse{90 + (8 * (360 /13))}
        \node[{minimum size=1mm, circle,draw}] (5) at (\pgfmathresult:2.65) {};
        \pgfmathparse{90 + (7 * (360 /13))}
        \node[{minimum size=1mm, circle,draw}] (6) at (\pgfmathresult:2.65) {};
        \pgfmathparse{90 + (6 * (360 /13))}
        \node[{minimum size=1mm, circle,draw}] (7) at (\pgfmathresult:2.65) {};
        \pgfmathparse{90 + (5 * (360 /13))}
        \node[{minimum size=1mm, circle,draw}] (8) at (\pgfmathresult:2.65) {};
        \pgfmathparse{90 + (4 * (360 /13))}
        \node[{minimum size=1mm, circle,draw}] (9) at (\pgfmathresult:2.65) {};
        \pgfmathparse{90 + (3 * (360 /13))}
        \node[{minimum size=1mm, circle,draw}] (10) at (\pgfmathresult:2.65) {};
        \pgfmathparse{90 + (2 * (360 /13))}
        \node[{minimum size=1mm, circle,draw}] (11) at (\pgfmathresult:2.65) {};
        \pgfmathparse{90 + (1 * (360 /13))}
        \node[{minimum size=1mm, circle,draw}] (12) at (\pgfmathresult:2.65) {};

        \draw [-,cap=rect,line width=0.3mm,draw=magenta] (1)--(2);
        \draw [-,cap=rect,line width=0.3mm,draw=magenta] (1)--(5);
        \draw [-,cap=rect,line width=0.3mm,draw=magenta] (2)--(5);

        \draw [-,cap=rect,line width=0.3mm,draw=blue] (0)--(2);
        \draw [-,cap=rect,line width=0.3mm,draw=blue] (0)--(7);
        \draw [-,cap=rect,line width=0.3mm,draw=blue] (2)--(7);

        \foreach \x [count=\idx from 0] in {12,...,0} {
            \pgfmathparse{90 + ((\idx+1) * (360 /13))}
            \node at (\pgfmathresult:2.8 cm) [circle,draw=black,fill=white, minimum size=1mm,line width=0.2mm] {\x};
        };

        \pgfmathparse{90 + (0 * (360 /13))}
        \node[{minimum size=1mm, circle, draw, fill=cyan, text=white}] (0) at (\pgfmathresult:2.8) {0};
        \pgfmathparse{90 + (12 * (360 /13))}
        \node[{minimum size=1mm, circle, draw, fill=black, text=white}] (1) at (\pgfmathresult:2.8) {1};
        \pgfmathparse{90 + (8 * (360 /13))}
        \node[{minimum size=1mm, circle, draw, fill=cyan, text=white}] (5) at (\pgfmathresult:2.8) {5};

        \pgfmathparse{90 + (0 * (360 /13))}
        \node[{minimum size=1mm, circle, draw, fill=blue, text=white}] (0) at (\pgfmathresult:2.8) {0};
        \pgfmathparse{90 + (12 * (360 /13))}
        \node[{minimum size=1mm, circle, draw, fill=magenta, text=white}] (1) at (\pgfmathresult:2.8) {1};
        \pgfmathparse{90 + (8 * (360 /13))}
        \node[{minimum size=1mm, circle, draw, fill=magenta, text=white}] (5) at (\pgfmathresult:2.8) {5};
        \pgfmathparse{90 + (11 * (360 /13))}
        \node[{minimum size=1mm, circle, draw, fill=black, text=white}] (2) at (\pgfmathresult:2.8) {2};
        \pgfmathparse{90 + (6 * (360 /13))}
        \node[{minimum size=1mm, circle, draw, fill=blue, text=white}] (7) at (\pgfmathresult:2.8) {7};
    \end{tikzpicture}
\caption{$c=2$, $k=3$ {\rm tight~CDCCD}(13,3,2,26) $B_2$ and $B_3$ which is $B_1$ incremented by 1}
\label{Figure: dcccd(13,3,2,26) Step 2}
\end{figure}

\iffalse
Reading the light blue block first and then the dark blue block, we increment both blocks by one and repeat the colouring order. Note that taking every difference in B$_1$ and B$_2$ involving at least one introduced point produces the differences $1,2,...,12 \pmod{13}$. When we increment the base blocks we always have these differences in consecutive blocks. This produces the {\rm tight~CDCCD}(13,3,26) as seen in Table~\ref{Table: tdcccd(13,3,2,26)}. Note here that light blue and dark blue blocks increments to the pink and red blocks respectively.

\begin{table}[H]
    \centering
    \setlength{\tabcolsep}{.5\tabcolsep}
    \begin{tabular}{lllllllllllllllll}

    \tiny{\textcolor{cyan}{B$_1$}} & \tiny{\textcolor{blue}{B$_{2}$}} & \tiny{\textcolor{magenta}{B$_{3}$}} & \tiny{\textcolor{red}{$B_{4}$}} & \tiny{B$_{5}$} & \tiny{B$_{6}$} & \tiny{B$_{7}$} & \tiny{B$_{8}$} & \tiny{B$_{9}$}  & \tiny{B$_{10}$}  & \tiny{B$_{11}$} & \tiny{B$_{12}$} & \tiny{B$_{13}$} & \tiny{B$_{14}$} & \tiny{B$_{15}$} & \tiny{B$_{16}$} & \tiny{B$_{17}$}  \\

    \textcolor{cyan}{0}$^*$ & \textcolor{blue}{0} & \textcolor{magenta}{1}$^*$ & \textcolor{red}{1} & 2$^*$ & 2 & 3$^*$ & 3 & 4$^*$ & 4 & 5$^*$ & 5 & 6$^*$ & 6 & 7$^*$ & 7 & 8$^*$ \\

    \textcolor{cyan}{1} & \textcolor{blue}{2}$^*$ & \textcolor{magenta}{2} & \textcolor{red}{3}$^*$ & 3 & 4$^*$ & 4 & 5$^*$ & 5 & 6$^*$ & 6 & 7$^*$ & 7 & 8$^*$ & 8 & 9$^*$ & 9   \\

    \textcolor{cyan}{4}$^*$ & \textcolor{blue}{7}$^*$ & \textcolor{magenta}{5}$^*$ & \textcolor{red}{8}$^*$ & 6$^*$ & 9$^*$ & 7$^*$ & 10$^*$ & 8$^*$ & 11$^*$ & 9$^*$ & 12$^*$ & 10$^*$ & 0$^*$ & 11$^*$ & 1$^*$ & 12$^*$ \\ \hline

   \tiny{B$_{18}$} & \tiny{B$_{19}$} & \tiny{B$_{20}$} & \tiny{B$_{21}$}  & \tiny{B$_{22}$} & \tiny{B$_{23}$} & \tiny{B$_{24}$} & \tiny{B$_{25}$} & \tiny{B$_{26}$}\\

    8 & 9$^*$ & 9 & 10$^*$ & 10$^*$ & 11$^*$ & 11 & 12$^*$ & 12 \\

    10$^*$ & 10 & 11$^*$ & 11 & 12$^*$ & 12 & 0$^*$ & 0 & 1$^*$ \\

    2$^*$ & 0 & 3 & 1 & 4 & 2 & 5 & 3 & 6
    \end{tabular}
    \caption{Tight {\rm CDCCD}(13,3,26)}
    \label{Table: tdcccd(13,3,2,26)}\label{Table: tdcccd(13,3,26)}
\end{table}
\fi

\end{example}

\begin{proposition}
When $(k-2) | 2c+1 $, a {\rm CDCCD} ~constructed via Theorem~\ref{Theorem: Initial c blocks for all k >= 3} has an expansion set.
\end{proposition}

\begin{proof}
In Theorem~\ref{Theorem: Initial c blocks for all k >= 3} the unchanged subsets are all $A+i$, $i\in \mathbb{Z}_v$. When $(k-2)|2c+1$ then $(k-1)|v$. Taking $i\in \{0,k-2,2k-4,...\}$ partitions $\mathbb{Z}_v$ giving the
expansion set $\mathcal{E} = \bigcup\limits_{i=0}^{\frac{4ck-6c+1}{k-2}} \{ U_{ic(k-2)} \}$.
\end{proof}

\begin{corollary} \label{Corollary: Odd number of expansion sets}
If $\frac{2c+1}{k-2}$ is odd, then a {\rm tight~CDCCD}$(c(4k-6)+|\mathcal{E}|+2,k,c^2(4k-6)+c+|\mathcal{E}|\frac{|\mathcal{E}|+1}{2})$ exists.
\end{corollary}
\begin{proof}
The order of the expansion set is $|\mathcal{E}|=\frac{4ck-6c+1}{k-2}=4c+\frac{2c+1}{k-2}$. This is odd if and only if $\frac{2c+1}{k-2}$ is odd then we apply Theorem~\ref{Theorem: dccd(v+1,k,2) increase}.
\end{proof}

\begin{corollary}
\label{Corollary: tdcccd(15,3,2,35) exists}
\label{Corollary: tdcccd(15,3,35) exists}
\label{Corollary: tdcccd(21,5,30) exists}
\label{Corollary: 11 additional tdcccd using recusion on diff families}

The following tight {\rm CDCCD}~ exist: {\rm CDCCD}(15,3,35), {\rm CDCCD}(21,5,30), {\rm CDCCD}(27,3,117), {\rm CDCCD}(55,7,135), {\rm CDCCD}(39,3,247), {\rm CDCCD}(105,9,364), {\rm CDCCD}(67,3,489), {\rm CDCCD}(77,5,418), {\rm CDCCD}(161,11,640), {\rm CDCCD}(63,3,651),  {\rm CDCCD}(253,13,1386)
\end{corollary}

\begin{proposition}
\label{Proposition: tdcccd(61,4,366) exists}
A {\rm tight~CDCCD}$(61,4,366)$ exists.
\end{proposition}

\begin{proof}
Consider the initial blocks in order as shown in Table~\ref{Table: c=6, k=4 dcccd(61,4,366) example}. Each contains $A=\{0,1\}$ and $B_{0,c}$ contains $A$ and $A+1$ thus $(B_{0,1},B_{0,2},...,B_{0,c}, $ $B_{1,1},...,B_{1,c},...,B_{v,c})$ is double change. $B_{0,i}= \{0,1,x,y\}$ covers differences $\pm \{y-x,x-1,x,y-1,y\}$ and as $x,y$ range over values in Table~\ref{Table: c=6, k=4 dcccd(61,4,366) example} these cover all differences in $\mathbb{Z}_6$
\end{proof}

\begin{table}[H]
    \centering
    \begin{tabular}{|l|l|l|}
        \hline
        \textbf{$k$}  & \textbf{$c$} & \textbf{Initial Blocks}
        \\ \hline
         4  & 6 & $ \{0, 1, 4, 19\}, \{0, 1, 6, 22\}, \{0, 1, 8, 25\},\{0, 1, 10, 48\}, \{0, 1, 12, 32\},$ \\
         && $\{0, 1, 2, 28\}$ \\ \hline

    \end{tabular}
    \caption{Base Blocks for a {\rm CDCCD}(61,4,366)}
    \label{Table: c=6, k=4 dcccd(61,4,366) example}
\end{table}

\section{Conclusion}
We have proved a recursion that uses 1-factorizations and expansion sets to construct \dccd($v+\frac{v}{k-2}+1,k,b+\frac{v}{k-2}\frac{v+k-2}{2k-4}$) from \dccd($v,k,b$) when $\frac{v}{k-2}$ is odd.
We use the family of tight~CSCCD($2k'-1,k',2k'-1)$ to build {\rm tight~CDCCD}($2k-2,k,k-1$) and {\rm CDCCD}($2k-3,k,k-2$).
We use difference methods to construct {\rm tight~CDCCD}(61,4,366) and {\rm tight~CDCCD}($c(4k-6)+1,k,c^2(4k-6)+c$) for $k\geq 3$, $1\leq c\leq 5$. When possible we apply the recursion to these to construct eleven additional {\rm CDCCD}.

There are several directions to explore next. Can we develop a version of Theorem~\ref{Theorem: dccd(v+1,k,2) increase} that works when the size of the expansion set is even?
Can we develop a version of Theorem~\ref{Theorem: dccd(v+1,k,2) increase} to build economic \dccd~ from tight \dccd~ as in \cite{Chafee_sccd}.
Does there exist recursive construction that uses expansion sets and two \dccd~ to build tight \dccd~ or {\rm CDCCD}~ as in \cite{sccd,Chafee_sccd} respectively?
McSorely proved  the number of blocks in minimum CSCCD~ as long as $v\leq 2k-1$ \cite{circular}. Can we solve the existence of minimum {\rm CDCCD}~ when $v\leq 2k-2$? Finally, can we find more linear \dccd~ beyond when $k=4$?

\bibliographystyle{plain}