% EJC papers must begin as follows \documentclass[12pt]{article} \usepackage{e-jc} % only use standard LaTeX packages % only include essential packages % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; i.e. there must be no text protruding into the margins % use \sloppy to avoid overly wide text \sloppy % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf The existence of NGBTDs and its application} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Chengmin Wang, Jie Yan\footnote{Corresponding author. Email: jyan7906@yahoo.com.cn}\\ \small School of Science, Jiangnan University,\\[-0.8ex] \small Wuxi 214122, China \\ } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{XXX, XXX}{XXX, XXX}\\ \small Mathematics Subject Classifications: 05B05, 94B25} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} In this paper, we complete the existence of near generalized balanced tournament designs (NGBTDs) with block size 3 and 5. As its application, we obtain new classes of optimal constant composition codes. % keywords are optional \bigskip\noindent \textbf{Keywords:} near generalized balanced tournament design; constant composition codes; optimal; existence \end{abstract} \section{Introduction} Let $X$ be a set of $v$ {\em points}, and ${\cal A}$ a collection of subsets (called {\em blocks}) of $X$. A $(v, k, \lambda)$ {\em balanced incomplete block design} (BIBD), or a $(v, k, \lambda)$-BIBD, is a pair $(X,{\cal A})$ such that any pair of distinct points of $X$ occurs in precisely $\lambda$ blocks. A $(km+1, k, k - 1)$-BIBD $(X, {\cal A})$ is called a {\em near generalized balanced tournament design} (NGBTD), or an NGBTD$(k,m)$ in short, if its blocks can be arranged into an $m\times (km+1)$ array in such a way that (1) the blocks in each column form a partial parallel class which partition $X\backslash \{x\}$ for some point $x\in X$; (2) each point of $X$ is contained in precisely $k$ cells of each row.\\ By the definition, any NGBTD can be identified with its corresponding block array defined above. NGBTDs are a generalization of odd balanced tournament designs (OBTDs). Particularly, an NGBTD$(2, m)$ is an OBTD$(m)$ whose existence was completed in \cite{LV}. Lamken \cite{Lamken} almost finished the existence of NGBTD$(3, m)$ with four possible exceptions. Recently, Shan \cite{Shan} presented a nearly complete solution for the existence of NGBTD$(k, m)$'s for $k=4$ and 5 with four possible exceptions. We collect the existence of NGBTD$(k, m)$'s for $2\leq k \leq5$ as follows. \begin{theorem}\label{old NGBTD}{\rm (\cite{Lamken,LV,Shan})}\\ {\rm (1)} There exists an NGBTD$(2,m)$ for any positive integer $m$;\\ {\rm (2)} There exists an NGBTD$(3,m)$ for any positive integer $m$ and $m\not\in \{3, 38, 39, 118\}$;\\ {\rm (3)} There exists an NGBTD$(4,m)$ for any positive integer $m$;\\ {\rm (4)} There exists an NGBTD$(5,m)$ for any positive integer $m$ and $m\not\in \{15,32,40,45\}$. \end{theorem} A {\em group divisible design} of block size $k$ and index $\lambda$, or a $(k,\lambda)$-GDD, is a triple $(X, {\cal G}, {\cal B})$ where $X$ is a finite set of ({\em points}), ${\cal G}$ is a partition of $X$ into subsets (called {\em groups}), and ${\cal B}$ is a set of subsets of size $k$ (called {\em blocks}) of $X$, such that every pair of points from distinct groups occurs in exactly $\lambda$ blocks, and any pair of points from the same group occur in no block. The type of the GDD is defined to be the multiset $T = \{|G| : G \in {\cal G}\}$, which is usually denoted by an ``exponential" notation: a type $g_1^{u_1}g_2^{u_2}\cdots g_s^{u_s}$ means $u_i$ occurrences of $g_i$ for $1\leq i\leq s$. A set of blocks of a GDD $(X, {\cal G}, {\cal B})$ is called a {\em partial $\alpha$-parallel class} over $X\backslash S$ if each point of $X\backslash S$ occurs in exactly $\alpha$ blocks, while any point of $S$ occurs in no block. If $S =\emptyset$, it is called an {\em $\alpha$-parallel class} over $X$. Whenever $\alpha = 1$, we simply say a (partial) parallel class, instead of a (partial) $\alpha$-parallel class. A GDD is called {\em resolvable} if its blocks can be partitioned into parallel classes. We need a special type of GDDs, called {\em frame generalized doubly resolvable packings} (FGDRPs), which was first introduced in \cite{YY1} to construct optimal constant composition codes. Let $(X, {\cal G}, {\cal B})$ be a $(k,k-1)$-GDD of type $g^u$ where $g=kh$. Suppose that the group set ${\cal G}=\{G_1,G_2,\cdots, G_{u}\}$. Define {\small \begin{center} \tabcolsep 0.3 cm \begin{tabular}{l} $R_i=\{(i-1)h+j:j=1,\cdots, h\}$\\ $C_i=\{(i-1)kh+j:j=1,\cdots, kh\}$ \end{tabular} \end{center}} \noindent for $1\leq i\leq u$. The blocks of the GDD can be arranged into an $hu\times gu$ array $F$ which satisfies the following properties: \noindent (1) Each cell of $F$ is either empty or contains a block of ${\cal B}$;\\ (2) Let $F_t$ be the subarray indexed by the elements of $R_t$ and $C_t$. Then $F_t$ is empty for $t = 1, 2, \cdots, u$, i.e., the main diagonal of $F$ consists of $u$ empty subarrays of size $h\times kh$;\\ (3) For any $x \in R_i$ $(1\leq i\leq u)$, the blocks in row $x$ form a partial $k$-parallel class over $X\backslash G_i$;\\ (4) For any $y\in C_j$ $(1\leq j\leq u)$, the blocks in column $y$ form a partial parallel class over $X\backslash G_j$. Then we refer to this GDD as an FGDRP$(k, g^u)$. Actually, FGDRPs can be defined in a more general way in which all the groups are not necessarily the same size. Nevertheless, we use the definition here for our purpose. The interest reader may refer to \cite{YW,YY1} for more details on FGDRPs. In this note, we completely establish the existence of NGBTD$(k,m)$'s for $k=3$ and 5 by removing all the remaining cases in Theorem \ref{old NGBTD}. We also present an application of NGBTDs to optimal constant composition codes. \section{The Existence of NGBTDs with Block Size 3} In this section, we give a complete solution to the existence of NGBTDs with block size 3. \begin{theorem}\label{FGBTD to NGBTD}{\rm \cite{Shan,Yan}} Suppose that there exists an FGDRP$(k,g^u)$ where $g=kh$. Let $w$ be any nonnegative integer. If there exists an NGBTD$(k,h+w)$ which contains an NGBTD$(k,w)$ as a subarray, then an NGBTD$(k,hu+w)$ exists. \end{theorem} \begin{theorem}\label{FGBTD(3,g^u)} {\rm \cite{Yan,YW}} Let $g$ and $u$ be positive integers with $g\equiv 0$ $(mod\ 3)$ and $u\geq 5$. Then an FGDRP$(3, g^u)$ exists except possibly for $(g, u)\in \{(6, 15), (9, 18), (9, 28), (9, 34),(30, 15)\}$. \end{theorem} \begin{theorem}\label{NGBTD(3,m)} For any integer $m\geq 1$ and $m\neq 3$, there exists an NGBTD$(3, m)$. There does not exist an NGBTD$(3, 3)$. \end{theorem} $Proof:$ By Theorem \ref{FGBTD(3,g^u)}, there exists an FGDRP$(3, 3^m)$ for any $m\geq 5$. An NGBTD$(3,1)$ exists trivially with all the subsets containing any three points as blocks. Then we apply Theorem \ref{FGBTD to NGBTD} with $k=3,h=1,u=m,w=0$ to obtain an NGBTD$(3,m)$ for any $m\geq 5$. We know that there does not exist an NGBTD$(3, 3)$ definitely by an exhaustive search with the aid of a computer. Combining with Theorem \ref{old NGBTD}, we complete the proof. \qed \noindent {\bf Remark:} Here we have fixed the four possible exceptions in \cite {Lamken} and complete the existence of NGBTD$(3,m)$'s. Moreover, Theorem \ref{NGBTD(3,m)} actually provides an alternative proof for the existence of NGBTD$(3, m)$'s. \section{The Existence of NGBTDs with Block Size 5} This section serves to complete the existence of NGBTDs with block size 5, by removing the four outstanding cases in Theorem \ref{old NGBTD}. \begin{lemma}\label{$NGBTD(5,15)$} There exists an NGBTD$(5,15)$. \end{lemma} $Proof:$ We construct the desired NGBTD on the Abelian group $X=\mathbb{Z}_{19}\times \mathbb{Z}_2\times \mathbb{Z}_2$. Here we write the element $(a,b,c)$ of $X$ as $\underline{a}bc$ for brevity. The following blocks form a partial parallel class which partitions $X\backslash \{\underline{18}11\}$. {\small $$ \begin{array}{llllllllllll} \{\underline{ 0}01,\underline{ 0}00,\underline{ 0}10,\underline{ 0}11,\underline{ 1}00\}&\{\underline{16}01,\underline{ 3}01,\underline{12}10,\underline{ 9}10,\underline{14}01\}&\{\underline{14}11,\underline{13}11,\underline{ 7}01,\underline{17}01,\underline{ 2}00\}\\ \{\underline{15}01,\underline{12}00,\underline{18}01,\underline{ 3}11,\underline{11}01 \}&\{\underline{14}00,\underline{ 9}11,\underline{13}00,\underline{12}11,\underline{ 8}10\}&\{\underline{13}01,\underline{15}00,\underline{ 4}00,\underline{11}11,\underline{ 2}10 \}\\ \{\underline{ 1}01,\underline{ 3}00,\underline{10}11,\underline{11}00,\underline{17}11\}&\{\underline{ 1}11,\underline{ 4}01,\underline{ 6}11,\underline{ 9}01,\underline{14}10 \}&\{\underline{ 3}10,\underline{16}11,\underline{ 7}11,\underline{10}00,\underline{ 5}01\}\\ \{\underline{ 5}00,\underline{ 6}10,\underline{12}01,\underline{ 2}11,\underline{17}00 \}&\{\underline{ 4}11,\underline{ 7}00,\underline{ 1}10,\underline{16}10,\underline{ 8}11\}&\{\underline{ 5}10,\underline{10}10,\underline{ 6}00,\underline{ 7}10,\underline{11}10\}\\ \{\underline{ 6}01,\underline{ 4}10,\underline{15}10,\underline{ 8}00,\underline{17}10\}&\{\underline{18}00,\underline{16}00,\underline{ 9}00,\underline{ 8}01,\underline{ 2}01 \}& \{\underline{18}10,\underline{15}11,\underline{13}10,\underline{10}01,\underline{ 5}11\}\\ \end{array} $$ } It is easy to check that the desired design is produced by the action of the group $X$ on above partial parallel class. \qed Before we move to the next construction, we need the well-known starter-adder method, which is widely used to produce some designs with orthogonal properties (see, for example, \cite{CD,CLLM,LV,RV,Shan,YYW}). Let $G$ be an additively Abelian group of order $u$. Let $g=kt$. A {\em starter} $S$ for an FGDRP$(k,g^u)$ over $\mathbb{Z}_g\times G$ with groups $G_x=\mathbb{Z}_g\times \{x\}$ $(x\in G)$ consists of $t$ sets of $k$-tuples (base blocks), $S_1,S_2,\cdots, S_t$, which satisfies the following properties: (1) For any $i$ $(1\leq i\leq t)$, $S_i$ contains exactly $u-1$ base blocks $B_{ij}$, $j=1,2,\cdots, u-1$; (2) $S=\bigcup_{i=1}^{t} S_i$ forms a partition of $\mathbb{Z}_g\times (G\backslash \{0\})$ and every element of $\mathbb{Z}_g\times (G\backslash \{0\})$ occurs exactly $k-1$ times in the difference list of $S$. A corresponding {\em adder} $A(S)$ for the starter $S$ consists $t$ permutations (not necessarily distinct) of $G\backslash \{0\}$ $$ A(S_i)=(a_{i1},a_{i2}, \cdots, a_{i(u-1)}), 1\leq i\leq t $$ such that for any $i$ $(1\leq i\leq t)$, $\bigcup_{j=1}^{u-1} (B_{ij}+(0,a_{ij}))$ contains exactly $k$ elements (not necessarily distinct) from each group $G_x$ for $x\in G\backslash \{0\}$ and no element of $G_0$. \begin{theorem}\label{starter-adder-type1}{\rm{\cite {YW}}} If there exists a starter-adder pair $(S,A(S))$ for an FGDRP$(k,g^u)$ over $\mathbb{Z}_g\times G$ defined above, then there exists an FGDRP$(k,g^u)$. \end{theorem} \begin{lemma}\label{$FGDRP(25^9)$} There exists an FGDRP$(5,25^9)$. \end{lemma} $Proof:$ We take $\mathbb{Z}_{25}\times GF(9)$ as the point set and $\{\mathbb{Z}_{25}\times \{x\}\mid x\in GF(9)\}$ as the groups. Let $GF(9)^*=GF(9)\backslash\{0\}$. Suppose that ${\omega}$ is a primitive element of $GF(9)$ satisfying ${\omega}^2={\omega}+1$ and $C_0^2$ is the square residue of $GF(9)^*$. We display the starter $S$ and the corresponding adder $A(S)$ in Table \ref{25^9}. Then we apply Theorem \ref{starter-adder-type1} to produce the desired design. \begin{table}[htbp] \begin{center} \caption{The starters and corresponding adders for an $FGDRP(25^9)$}\label{25^9} {\small \begin{tabular}{|ccc|c|} \hline &$S$ &$A(S)$&\\ \hline $S_1:$ &\{(0,${\omega}^1$), (8,${\omega}^5$), (8,${\omega}^2$), (13,${\omega}^3$), (14,${\omega}^7$)\}$\cdot(1,h)$ &(0,1)$\cdot(1,h)$& \\ &\{(9,${\omega}^0$), (10,${\omega}^7$), (21,${\omega}^1$), (23,${\omega}^2$), (15,${\omega}^6$)\}$\cdot(1,h)$ &(0,${\omega}$)$\cdot(1,h)$&\\ $S_2:$ &\{(2,${\omega}^6$), (11,${\omega}^5$), (12,${\omega}^2$), (14,${\omega}^0$), (15,${\omega}^1$)\}$\cdot(1,h)$ &(0,1)$\cdot(1,h)$&\\ &\{(5,${\omega}^4$), (6,${\omega}^6$), (17,${\omega}^3$), (20,${\omega}^7$), (24,${\omega}^1$)\}$\cdot(1,h)$ &(0,${\omega}$)$\cdot(1,h)$& \\ $S_3:$ &\{(10,${\omega}^0$), (18,${\omega}^1$), (18,${\omega}^6$), (19,${\omega}^3$), (23,${\omega}^7$)\}$\cdot(1,h)$ &(0,1)$\cdot(1,h)$ &$h\in C_0^2$ \\ &\{(2,${\omega}^1$), (4,${\omega}^3$), (4,${\omega}^6$), (11,${\omega}^2$), (13,${\omega}^4$)\}$\cdot(1,h)$ &(0,${\omega}$)$\cdot(1,h)$&\\ $S_4:$ &\{(3,${\omega}^6$), (7,${\omega}^1$), (19,${\omega}^0$), (22,${\omega}^2$), (22,${\omega}^7$)\}$\cdot(1,h)$ &(0,1)$\cdot(1,h)$&\\ &\{(1,${\omega}^2$), (6,${\omega}^1$), (9,${\omega}^7$), (16,${\omega}^0$), (24,${\omega}^6$)\}$\cdot(1,h)$ &(0,${\omega}$)$\cdot(1,h)$&\\ $S_5:$ &\{(1,${\omega}^1$), (12,${\omega}^5$), (16,${\omega}^3$), (17,${\omega}^6$), (20,${\omega}^0$)\}$\cdot(1,h)$ &(0,1)$\cdot(1,h)$ &\\ &\{(0,${\omega}^0$), (3,${\omega}^1$), (5,${\omega}^3$), (7,${\omega}^2$), (21,${\omega}^4$)\}$\cdot(1,h)$ &(0,${\omega}$)$\cdot(1,h)$ &\\ \hline \end{tabular} } \end{center} \end{table} \qed The second type of starter-adder construction is called intransitive starter-adder method, which involves infinite points. The reader may refer to \cite{CLLM,LV,RV,Shan,YW,YYW} for more details. Let $GF(u-1)$ be the Galois field with $u-1$ elements and $X=\mathbb{Z}_g\times$ $(GF{(u-1)}\bigcup \{\infty\})$ where $g=kt$. Let $G=\mathbb{Z}_g\times GF{(u-1)}$. An {\em intransitive starter} $S$ for an FGDRP$(k,g^u)$ over $X$ with groups $\{G_x=\mathbb{Z}_g\times \{x\}\mid x\in GF(u-1)\bigcup \{\infty\}\}$ is defined as a triple $(S,R,C)$ satisfying the following properties. (1) $S$ consists of $t$ sets of $k$-tuples (base blocks), $S_1,S_2,\cdots, S_t$. For any $i$ $(1\leq i\leq t)$, $S_i$ contains precisely $u-2$ base blocks, $B_{ij}$ $(1\leq i\leq u-2)$, in which there exist exactly $k$ base blocks containing one infinite point each from $G_{\infty}$; (2) $R$ consists of $t$ base blocks over $G$, denoted by $R_1,R_2\cdots, R_t$, in which each contains no infinite points; (3) $C$ consists of $t$ base blocks over $G$, denoted by $C_1,C_2\cdots, C_t$, in which each contains no infinite points; (4) $S\bigcup R$ forms a partition of $X\backslash G_0$; (5) the difference list from the base blocks of $S\bigcup R\bigcup C$ contains every element of $G\backslash G_0$ precisely $k -1$ times, and no element in $G_0$. A corresponding {\em adder} $A(S)$ for $S$ consists of $t$ permutations on $GF(u-1)\backslash \{0\}$, $$ A(S_i) = (a_{i1}, a_{i2},\cdots, a_{i(u-2)})\ (1\leq i\leq t) $$ For any $i$ $(1\leq i\leq t)$, the multiset $\bigcup_{j=1}^{u-2} (B_{ij}+(0,a_{ij}))\bigcup \{C_i\}$ contains exactly $k$ elements (not necessarily distinct) from each group $G_x$ for $x\in GF(u-1)\backslash \{0\}$ and no element of $G_0$. \begin{theorem}\label{starter-adder-type2} {\rm \cite{YW}} If there exists an intransitive starter $(S,R,C)$ over $X$ defined above and a corresponding adder $A(S)$, then there exists an FGDRP$(k,g^u)$. \end{theorem} \begin{lemma}\label{$FGDRP(20^{8})$} There exists an FGDRP$(5,20^{8})$. \end{lemma} $Proof:$ Let $X=\mathbb{Z}_{20} \times (\mathbb{Z}_{7}\cup \{\infty\})$ be the point set and $\{\mathbb{Z}_{20}\times \{x\}\mid x\in \mathbb{Z}_7\bigcup \{\infty\}\}$ the group set. Here we apply Theorem \ref{starter-adder-type2} with $k=5,t=4$. In the following table, we present $S_i,R_i,C_i$ and $A(S_i)$ for $i=1$ and 2. %\begin{table}[htbp] \begin{center} %\caption{$S_i,R_i,C_i$ and $A(S_i)$ $(i=1,2)$ for an $FGDRP(20^{8})$}\label{20^8} {\small \begin{tabular}{|cc||cc|} \hline $A(S_1)$ &$S_1$ & $A(S_2)$ &$S_2$\\ \hline (0,6) & \{(3,3), (19,6), (0,2), (17,5), (2,4)\} & (0,6) &\{(4,5), (17,4), (9,2), (12,3), (15,6)\} \\ (0,5) & \{$-$, (7,5), (14,3), (13,1), (4,6)\} & (0,5) &\{$-$, (15,5), (2,6), (11,3), (19,4)\} \\ (0,4) & \{$-$, (2,5), (0,4), (9,6), (1,2)\} & (0,4) &\{$-$, (4,4), (6,6), (12,1), (13,2)\} \\ (0,3) & \{$-$, (8,1), (3,6), (19,2), (10,5)\} & (0,3) &\{$-$, (18,3), (11,1), (12,2), (7,6)\} \\ (0,2) & \{$-$, (16,2), (16,4), (1,6), (8,3)\} & (0,2) &\{$-$, (3,2), (5,4), (9,3), (16,6)\} \\ (0,1) & \{$-$, (5,1), (5,5), (10,4), (14,2)\} & (0,1) &\{$-$, (6,3), (6,5), (14,1), (18,2)\} \\ \hline\hline $C_1:$&\{(4,2), (14,4), (14,3), (0,6), (0,5)\} & $C_2:$&\{(6,3), (5,1), (8,6), (8,2), (7,5)\} \\ $R_1:$&\{(7,4), (11,5), (1,3), (17,1), (0,6)\} & $R_2:$&\{(10,6), (18,1), (15,4), (13,3), (8,2)\} \\ \hline \end{tabular} } \end{center} For $i=3$ and 4, let $S_{i}=S_{i-2}\cdot (1,-1)$, $R_{i}=R_{i-2}\cdot (1,-1)$, $C_{i}=C_{i-2}\cdot (1,-1)$ and $A(S_{i})=A(S_{i-2})\cdot (1,-1)$. Then it is easy to check that $(\cup_{i=1}^4S_i,\cup_{i=1}^4R_i,\cup_{i=1}^4C_i)$ is an intransitive starter and $A(S)=\cup_{i=1}^4A(S_i)$ is the corresponding adder for an FGDRP$(5,20^{8})$. Here the twenty points from $\mathbb{Z}_{20}\times \{\infty\}$ can be distributed to the five blocks of size four in each $S_i$ for $1\leq i \leq 4$ in an arbitrary way. So we use the symbol ``$-$" to denote any point from $\mathbb{Z}_{20}\times \{\infty\}$. \qed \begin{lemma}\label{$FGDRP(20^{10})$} There exists an FGDRP$(5,20^{10})$. \end{lemma} $Proof:$ Here we take $\mathbb{Z}_{20} \times (GF(9)\cup \{\infty\})$ as the point set and $\{\mathbb{Z}_{20}\times \{x\}\mid x\in GF(9)\cup \{\infty\}\}$ as the group set. Suppose that ${\omega}$ is a primitive element of $GF(9)$ satisfying ${\omega}^2={\omega}+1$. We apply Theorem \ref{starter-adder-type2} with $k=5,t=4$. First we display $S_1$, $R_1$, $C_1$ and $A(S_1)$ in the following table. \begin{center} % \caption{$S_1,R_1,C_1$ and $A(S_1)$ for an $FGDRP(20^{10})$}\label{20^10} {\small \begin{tabular}{|cc|} \hline $A(S_1)$ &$S_1$ \\ \hline (0,$1$) &\{(16,${\omega}^0$), (7,${\omega}^6$), (14,${\omega}^2$), (10,${\omega}^7$), (1,${\omega}^1$)\} \\ (0,${\omega}$) &\{(3,${\omega}^0$), (18,${\omega}^1$), (18,${\omega}^2$), (6,${\omega}^3$), (4,${\omega}^7$)\} \\ (0,${\omega}^2$) &\{(6,${\omega}^0$), (14,${\omega}^1$), (2,${\omega}^2$), (3,${\omega}^3$), (1,${\omega}^4$)\} \\ (0,${\omega}^3$) &\{$-$, (4,${\omega}^0$), (13,${\omega}^1$), (0,${\omega}^4$), (9,${\omega}^5$)\} \\ (0,${\omega}^4$) &\{$-$, (8,${\omega}^4$), (15,${\omega}^2$), (8,${\omega}^5$), (11,${\omega}^6$)\} \\ (0,${\omega}^5$) &\{$-$, (12,${\omega}^5$), (16,${\omega}^3$), (15,${\omega}^7$), (17,${\omega}^6$)\} \\ (0,${\omega}^6$) &\{$-$, (0,${\omega}^7$), (9,${\omega}^6$), (19,${\omega}^4$), (19,${\omega}^5$)\} \\ (0,${\omega}^7$) &\{$-$, (2,${\omega}^1$), (10,${\omega}^2$), (12,${\omega}^0$), (17,${\omega}^5$)\} \\ \hline \hline $C_1$: &\{(15,${\omega}^7$), (2,${\omega}^3$), (14,${\omega}^0$), (5,${\omega}^5$), (11,${\omega}^4$)\} \\ $R_1$: &\{(11,${\omega}^5$), (5,${\omega}^2$), (5,${\omega}^7$), (13,${\omega}^6$), (7,${\omega}^1$)\} \\ \hline \end{tabular} } \end{center} % \end{table} Then, for $1\leq i \leq 4$, let $S_i=S_1 \cdot (1,{\omega}^{2(i-1)})$, $R_i=R_1 \cdot (1,{\omega}^{2(i-1)})$, $C_i=C_1 \cdot (1,{\omega}^{2(i-1)})$ and $A(S_i)=A(S_1) \cdot (1,{\omega}^{2(i-1)})$. It is an easy matter to verify that $(\cup_{i=1}^4S_i,\cup_{i=1}^4R_i,\cup_{i=1}^4C_i)$ is the required intransitive starter and $A(S)=\cup_{i=1}^4A(S_i)$ is the corresponding adder. Similarly with Lemma \ref{$FGDRP(20^{8})$}, the twenty points from $\mathbb{Z}_{20}\times \{\infty\}$ can be distributed to the five blocks of size four in each $S_i$ for $1\leq i \leq 4$ in an arbitrary way. So we still use the symbol ``$-$" to denote any point from $\mathbb{Z}_{20}\times \{\infty\}$. \qed %\begin{table}[htbp] % \begin{center} % \caption{$S_1,R_1,C_1$ and $A(S_1)$ for an $FGDRP(20^{10})$}\label{20^10} % {\small % \begin{tabular}{|cc|} % \hline % $A(S_1)$ &$S_1$ \\ % \hline % (0,$1$) &\{(16,${\omega}^0$), (7,${\omega}^6$), (14,${\omega}^2$), (10,${\omega}^7$), (1,${\omega}^1$)\} \\ % (0,${\omega}$) &\{(3,${\omega}^0$), (18,${\omega}^1$), (18,${\omega}^2$), (6,${\omega}^3$), (4,${\omega}^7$)\} \\ % (0,${\omega}^2$) &\{(6,${\omega}^0$), (14,${\omega}^1$), (2,${\omega}^2$), (3,${\omega}^3$), (1,${\omega}^4$)\} \\ % (0,${\omega}^3$) &\{$-$, (4,${\omega}^0$), (13,${\omega}^1$), (0,${\omega}^4$), (9,${\omega}^5$)\} \\ % (0,${\omega}^4$) &\{$-$, (8,${\omega}^4$), (15,${\omega}^2$), (8,${\omega}^5$), (11,${\omega}^6$)\} \\ % (0,${\omega}^5$) &\{$-$, (12,${\omega}^5$), (16,${\omega}^3$), (15,${\omega}^7$), (17,${\omega}^6$)\} \\ % (0,${\omega}^6$) &\{$-$, (0,${\omega}^7$), (9,${\omega}^6$), (19,${\omega}^4$), (19,${\omega}^5$)\} \\ % (0,${\omega}^7$) &\{$-$, (2,${\omega}^1$), (10,${\omega}^2$), (12,${\omega}^0$), (17,${\omega}^5$)\} \\ % \hline \hline % $C_1$: &\{(15,${\omega}^7$), (2,${\omega}^3$), (14,${\omega}^0$), (5,${\omega}^5$), (11,${\omega}^4$)\} \\ % $R_1$: &\{(11,${\omega}^5$), (5,${\omega}^2$), (5,${\omega}^7$), (13,${\omega}^6$), (7,${\omega}^1$)\} \\ % \hline % \end{tabular} % } % \end{center} % \end{table} Now we are in a position to complete the existence of NGBTDs with block size five. \begin{theorem}\label{NGBTD(5,m)} For any positive integer $m$, there exists an NGBTD$(5,m)$. \end{theorem} $Proof:$ By Theorem \ref{old NGBTD}, we need only to show an NGBTD$(5,m)$ exists for each $m\in \{15,32,40,45\}$. An NGBTD$(5,15)$ is given in Lemma \ref{$NGBTD(5,15)$}. For $m\in \{32,40,45\}$, we apply Theorem \ref{FGBTD to NGBTD} with $k=5,w=0$ and other suitable parameters displayed in the following table to obtain the desired NGBTD$(5,m)$. {\small \begin{center} \tabcolsep 0.3 cm \begin{tabular}{ccccccccccccccccccc} \hline $m$ &&&$g$ && &$h$ & & &$u$ & & &the source of an FGDRP$(k,g^{u})$ \\\hline 32 &&&20 && &4 & & &8 & & &Lemma \ref{$FGDRP(20^{8})$} \\ 40 &&&20 && &4 & & &10 & & & Lemma \ref{$FGDRP(20^{10})$} \\ 45 &&&25 && &5 & & &9 & & & Lemma \ref{$FGDRP(25^9)$} \\\hline \end{tabular} \end{center}} \section{Applications to Constant Composition Codes} Let $Q =\{a_t:0\leq t\leq m-1\}$ be an arbitrary alphabet set with $m$ elements. A code $C\subseteq Q^n$ over $Q$ with size $M$ and minimum distance $d$ is referred to as a {\it constant composition code} (CCC), or an $(n, M, d, [w_0,w_1,\cdots ,w_{m-1}])_m$-CCC, if each codeword has precisely $w_i$ occurrences of $a_i$ for any $i$ $(0\leq i\leq m-1)$. Here the definition implies $n=\sum_{0\leq i\leq m-1}w_i$. Since the constant composition $[w_0,w_1,\cdots ,w_{m-1}]$ is essentially an unordered multiset, we usually write it in an exponential notation: a constant composition $[a_1^{u_1}a_2^{u_2}\cdots a_s^{u_s}]$ indicates $u_i$ occurrences of $a_i$ for $1\leq i\leq s$ for brevity. We denote the maximum size $M$ of an $(n, M, d, [w_0,w_1,\cdots ,w_{m-1}])_m$-CCC by $A_m(n,$ $d, [w_0,w_1,\cdots, w_{m_1}])$. A CCC with this size is called {\it optimal}. The following upper bound was established by Luo et al. \cite{LFHC}. \begin{theorem}\label{CCC Bound} {\rm{\cite{LFHC}}} If $nd-n^2+(w_0^2 + w_1^2 +\cdots+w_{m-1}^2)>0$, then $$ A_m(n, d, [w_0,w_1,\cdots, w_{m_1}])\leq \frac{nd}{nd-n^2+(w_0^2 + w_1^2 +\cdots+w_{m-1}^2)}. $$ \end{theorem} The study of optimal CCCs has attracted extensive attention due to their numerous applications (see, for example, \cite{DY1,LFHC} and the references therein). Particularly, Ding and Yin \cite{DY1} presented a combinatorial characterization of constant composition codes and established an equivalent relationship between CCCs and a class of designs called generalized doubly resolvable packings (GDRPs) which are defined below. Let $X$ be a set of $v$ elements (called points) and ${\cal A}$ be a collection of subsets (called blocks) of $X$. Then the pair $(X,{\cal A})$ is called a {\em $\lambda$-packing} of order $v$, if every pair of distinct points of $X$ occurs in at most $\lambda$ blocks. Furthermore, it is termed a {\em generalized doubly resolvable packing} (GDRP), if the blocks of ${\cal A}$ can be arranged into an $m\times n$ array ${\cal R}$ which satisfies the following properties: (1) Each cell of ${\cal R}$ is either empty or contains one block; (2) For $0\leq i\leq m-1$, the blocks in row $i$ of ${\cal R}$ form a $w_i$-parallel class, that is, every point occurs in exactly $w_i$ blocks; (3) The blocks in every column of ${\cal R}$ form a parallel class, that is, every point occurs in exactly one block. We denote such a GDRP by a GDRP$(m\times n,\lambda; v)$. The multiset $T = \{w_0,w_1,\cdots, w_{m-1}\}$ is called the type of the GDRP. For more details, the interested reader may refer to \cite{DY1,YY1,YY2}. \begin{theorem}\label{optimal CCC}{\rm {\cite{DY1,YY2}}} The existence of a GDRP$(m\times n,\lambda;v)$ of type $\{w_0,w_1,\cdots,w_{m-1}\}$ is equivalent to an $(n, M, d, [w_0,w_1,\cdots, w_{m-1}])_m$-CCC, where $M=v$ and $d=n-\lambda$. \end{theorem} \begin{theorem}\label{CCC+GDRP} If there exists an NGBTD$(k,m)$, then there exists an optimal $(km+1,km+1,k(m-1)+2,[1^1k^m])_{m+1}$-CCC. \end{theorem} $Proof:$ It is readily checked that an NGBTD$(k,m)$ is a GDRP$(m\times (km+1),k-1;km+1)$ of type $\{1,k,\cdots, k\}$. By Theorem \ref{optimal CCC}, we have an $(n, M, d, [w_0,w_1,\cdots, w_{m-1}])_m$-CCC with $n=M=km+1, d=k(m-1)+2, w_0=1, w_1=w_2=\cdots=w_{m-1}=k$. In addition, by Theorem \ref{CCC Bound}, we have \begin{align*} &\ \ \ \ \ A_m(km+1, k(m-1)+2, [1^1k^m])\\ &\ \ \ \ \ \leq \displaystyle\frac{(km+1)(k(m-1)+2)}{(km+1)(k(m-1)+2)-(km+1)^2+(1^2 + k^2+\cdots+k^2)}\\ &\ \ \ \ \ =\displaystyle\frac{(km+1)(k(m-1)+2)}{(km+1)(1-k)+(1+mk^2)}\\ &\ \ \ \ \ =km+1 \end{align*} Hence the obtained CCC is optimal. Then the proof is complete. \qed \begin{theorem}\label{New optimal CCC} Let $m,k$ be integers satisfying $m\geq 1$, $2 \leq k\leq 5$ and $(k,m)\not\in (3,3)$. Then there exists an optimal $(km+1,km+1,k(m-1)+2,[1^1k^m])_{m+1}$-CCC. \end{theorem} $Proof:$ By Theorem \ref{old NGBTD}, \ref{NGBTD(3,m)} and \ref{NGBTD(5,m)}, there exists an NGBTD$(k,m)$ for any integers $m$ and $k$ where $m\geq 1$, $2 \leq k\leq 5$ and $(k,m)\not\in (3,3)$. Then the conclusion follows from Theorem \ref{CCC+GDRP}. \qed \vspace{0.3cm} \noindent{\bf Acknowledgement} The authors thank the referees for their valuable comments and suggestions. This work is supported by NSFC under Grants No. 10801064, 11001109, and 10926103, and by the Program for Innovative Research Team of Jiangnan University. \begin{thebibliography}{99} \bibitem{CD} C. J. Colbourn and J. H. Dinitz. The CRC Handbook of Combinatorial Designs. CRC Press, Boca Raton, FL, 2007. \bibitem{CLLM} C. J. Colbourn, E. R. Lamken, A. C. H. Ling and W. H. Mills. The existence of Kirkman squares-doubly resolvable $(v, 3, 1)$-BIBDs. {\it Des. Codes Cryptogr.} 26:169--196, 2002. \bibitem{DY1} C. Ding and J. Yin. Combinatorial constructions of optimal constant composition codes. {\it IEEE Trans. Inf. Theory}, 51:3671--3674, 2005. %\bibitem{DY2} C. Ding and J. Yin, A construction % of optimal constant composition codes, {\it Des. Codes Cryptogr.}, % {\bf 40}, (2006), 157-165. % \bibitem{FMY} S. Furino, Y. Miao and J. Yin, Frames and Resolvable Designs, CRC Press, Boca Raton, % FL, 1996. %\bibitem{GO} E. N. Gelling and R. E. Odeh, On 1-factorizations of % the complete graph and the relationship to round robin schedules, % {\it Congr. Number}, {\bf 9} (1974), 213-221. \bibitem{Lamken} E. R. Lamken. On near generalized balanced tournament designs, {\it Discrete Math.}, 97:279--294, 1991. \bibitem{LV} E. R. Lamken and S. A. Vanstone. Orthogonal resolutions in odd balanced tournament designs. {\it Graphs Combin.}, 4:241--255, 1988. \bibitem{LFHC} Y. Luo, F. W. Fu, A. J. Han Vinck and W. Chen. On constant composition codes over $Z_q$. {\it IEEE Trans. Inf. Theory}, 49:3010--3016, 2003. \bibitem{RV} A. Rosa and S. A. Vanstone. Starter-adder techniques for Kirkman squares and Kirkman cubes of small sides. {\it Ars Combinatoria}, 14:199--212, 1982. \bibitem{Shan} X. Shan. Near generalized balanced tournament designs with block sizes 4 and 5. {\it Sci. China Ser. A}, 50:1382--1388, 2007. \bibitem{Yan} J. Yan. Generalized doubly resolvable packings and the corresponding codes. Ph.D thesis, Suzhou, Suzhou University, 2007. \bibitem{YW} J. Yan and C. Wang. The existence of FGDRP$(3, g^u)$'s. {\it Electronic Journal of Combinatorics}, 16, 2009. \bibitem{YY1} J. Yan and J. Yin. Constructions of optimal GDRP$(n,\lambda; v)$ of type $\lambda^1\mu^{m-1}$. {\it Discrete Appl. Math.}, 156:2666--2678, 2008. \bibitem{YY2} J. Yan and J. Yin. A class of optimal constant composition codes from GDRPs. {\it Des. Codes Cryptogr.}, 50:61--76, 2009. \bibitem{YYW} J. Yin, J. Yan and C. Wang. Generalized balanced tournament designs and related codes. {\it Des. Codes Cryptogr.}, 46:211--230, 2008. \end{thebibliography} %\begin{thebibliography}{10} % %\bibitem{Bollobas} B{\'e}la Bollob{\'a}s. \newblock Almost every % graph has reconstruction number three. \newblock {\em J. Graph % Theory}, 14(1):1--4, 1990. % %\bibitem{WikipediaReconstruction} Wikipedia contributors. \newblock % Reconstruction conjecture. \newblock {\em Wikipedia, the free % encyclopedia}, 2011. % %\bibitem{FGH} J.~Fisher, R.~L. Graham, and F.~Harary. \newblock A % simpler counterexample to the reconstruction conjecture for % denumerable graphs. \newblock {\em J. Combinatorial Theory Ser. B}, % 12:203--204, 1972. % %\bibitem{HHRT} Edith Hemaspaandra, Lane~A. Hemaspaandra, % Stanis{\l}aw~P. Radziszowski, and Rahul Tripathi. \newblock % Complexity results in graph reconstruction. \newblock {\em Discrete % Appl. Math.}, 155(2):103--118, 2007. % %\bibitem{Kelly} Paul~J. Kelly. \newblock A congruence theorem for % trees. \newblock {\em Pacific J. Math.}, 7:961--968, 1957. % %\bibitem{KSU} Masashi Kiyomi, Toshiki Saitoh, and Ryuhei Uehara. % \newblock Reconstruction of interval graphs. \newblock In {\em % Computing and combinatorics}, volume 5609 of {\em Lecture Notes in % Comput. Sci.}, pages 106--115. Springer, 2009. % %\bibitem{RM} S.~Ramachandran and S.~Monikandan. \newblock Graph % reconstruction conjecture: reductions using complement, connectivity % and distance. \newblock {\em Bull. Inst. Combin. Appl.}, % 56:103--108, 2009. % %\bibitem{RR} David Rivshin and Stanis{\l}aw~P. Radziszowski. % \newblock The vertex and edge graph reconstruction numbers of small % graphs. \newblock {\em Australas. J. Combin.}, 45:175--188, 2009. % %\bibitem{Stockmeyer} Paul~K. Stockmeyer. \newblock The falsity of the % reconstruction conjecture for tournaments. \newblock {\em J. Graph % Theory}, 1(1):19--25, 1977. % %\bibitem{Ulam} S.~M. Ulam. \newblock {\em A collection of % mathematical problems}. \newblock Interscience Tracts in Pure and % Applied Mathematics, no. 8. Interscience Publishers, New % York-London, 1960. % %\end{thebibliography} \end{document}