\documentstyle[12pt]{article} \textwidth=6.5in \textheight=8.9in \topmargin -0.5in \parskip 6pt \oddsidemargin=0.1in \evensidemargin=0.1in \newcommand{\B}{{\cal B}} \newcommand{\A}{{\cal A}} \newcommand{\C}{{\cal C}} \newcommand{\Hh}{{\cal H}} \newcommand{\Pp}{{\cal P}} \newcommand{\G}{{\cal G}} \newcommand{\Z}{{\bf Z}} \newcommand{\qed}{\hfill $\Box$} \newcommand{\U}{{\cal U}} \newcommand{\Proof}{{\em Proof.\ }} \newtheorem{theorem}{Theorem}[section] \newtheorem{definition}{Definition}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{construction}[theorem]{Construction} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{Theorem}{Theorem}[section] \newtheorem{Construction}[Theorem]{Construction} \newtheorem{Lemma}[Theorem]{Lemma} \newtheorem{Corollary}[Theorem]{Corollary} \newtheorem{Remark}[Theorem]{Remark} \def\whitebox{{\hbox{\hskip 1pt \vrule height 6pt depth 1.5pt \lower 1.5pt\vbox to 7.5pt{\hrule width 3.2pt\vfill\hrule width 3.2pt}% \vrule height 6pt depth 1.5pt \hskip 1pt } }} \def\qed{\ifhmode\allowbreak\else\nobreak\fi\hfill\quad\nobreak \whitebox\medbreak} \title{\LARGE\textbf{Decomposing Complete Graphs into $r\times 4$ Grid-Blocks with $r=3,4$}} \author{\small Rucong Zhang and Gennian Ge\thanks{Corresponding author. Email: gnge@zju.edu.cn} \thanks{Research supported by National Natural Science Foundation of China under Grant No.~10471127, Zhejiang Provincial Natural Science Foundation of China under Grant No.~R604001, and the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry}\\ %The Project-sponsored by SRF for ROCS, SEM. \small Department of Mathematics\\ \small Zhejiang University\\ \small Hangzhou 310027, Zhejiang, P. R. China\\ \and \small Hung-Lin Fu and Jyh-Ming Kuo\thanks{Research supported by NSC 94-2115-M-009-017}\\ \small Department of Applied Mathematics\\ \small National Chiao Tung University\\ \bigskip \small Hsin Chu, Taiwan 30050 \and \small Yukiyasu Mutoh\thanks{Research supported by JSPS Research Fellow 09978} \\ \small Department of Mathematics \\ \small Keio University \\ \small Yokohama, Kanagawa, Japan 223-8522\\ } \begin{document} \date{} \maketitle \section{\Large\textbf{$3\times 4$-Grid Block Design}} \begin{Lemma} \label{existence}The necessary conditions for the existence of a $D_{r\times c}$$(K_{v})$ are: \begin{enumerate} \item$(v - 1) \equiv 0\ (\bmod\ {r+c-2})$ and \\ \item$v(v - 1) \equiv 0\ (\bmod\ {rc(r+c-2)})$. \end{enumerate} \end{Lemma} \hspace*{1.5em}Hence, a routine verification shows the following fact. \begin{Lemma}If a $D_{3\times4}(K_{v})$ exists, then $v\equiv 1,16,21,36\ (\bmod\ {60})$. \end{Lemma} \hspace{1.5em}In this paper, we will prove that the necessary conditions $v\equiv 1,21\ (\bmod\ {60})$ are also sufficient. And the others remain unknown. In other words, in this paper we want to prove the following theorem. \begin{Theorem}The necessary conditions $v\equiv 1,21\ (\bmod\ {60})$ for the existence of a $D_{3\times4}(K_{v})$ are also sufficient. \end{Theorem} \subsection{\Large\textbf{$v\equiv 1\ (\bmod\ {60})$}} \hspace{1.5em}In this paper, the methods which we adopt are mainly direct constructions. These direct constructions are based on familiar difference method, where a finite abelian group is used to generate the set of grid-blocks for a given design. Thus, instead of listing all the grid-blocks of the design, we list a set of base grid-blocks and generate the others by an additive group and perhaps some further automorphisms.\\ \hspace*{1.5em}Before describing our result, we need several essential lemmas. Let $K_{m}(n)$ denote the balanced complete $m-$partite graph with each partite set of size n. Then, the following lemma holds. \begin{Lemma}The necessary conditions for the existence of a $D_{r\times c}(K_{m}(n))$ are: \begin{enumerate} \item$(m - 1)n \equiv 0\ (\bmod\ {r+c-2})$ and \\ \item$mn^2(m - 1) \equiv 0\ (\bmod\ {rc(r+c-2)})$. \end{enumerate} \end{Lemma} \hspace{1.5em}We list some recursive constructions obtained by FU et al.\cite{fu} and Mutoh et al.\cite{mutoh}. \begin{Lemma} \label{base}A $D_{r\times c}(K_{m\times n+1})$exists if a $D_{r\times c}(K_{n+1})$ and a $D_{r\times c}(K_{m}(n))$exists. \end{Lemma} \begin{Lemma} \label{gdd}There exists a $D_{r\times c}(K_{vt+1})$ if there exist a GDD(v,$\mathcal{K}$,$\mathcal{M}$), $D_{r\times c}(K_{mt+1})$ and $D_{r\times c}(K_{k}(t))$ for any m $\in \mathcal{M}$ and k $\in \mathcal{K}$. \end{Lemma} \begin{Lemma} \label{oa}There exists a $D_{r\times c}(K_{s}(tu))$ if there exists a $D_{r\times c}(K_{s}(t))$ and an OA(u,s), where OA(u,s) is an orthogonal array of order u, degree s and index 1. \end{Lemma} \begin{Lemma} \label{gdde}For any integer $v\ge$ 12, there exists a GDD(v,$\mathcal{K}$,$\mathcal{M}$), where $\mathcal{K}$ =\{4,5\} and $\mathcal{M}$=\{1,2,...,7\}. \end{Lemma} \hspace{1.5em}Lastly, we extend the construction in \cite{three} to grid-block designs to obtain such designs easily. For a positive integer e, let q be a prime power such that $q\equiv 1 (\bmod\ e)$ . The cyclic multiplicative subgroup of nonzero elements in GF(q) has a unique subgroup $C^e_0$ of index e. The multiplicative cosets $C^e_0$,$C^e_1$,...,$C^e_{e-1}$ of $C^e_0$ are called the cyclotomic classes of index e.\\ \hspace{1.5em}Let A=$(a_{ij})$ be a $r\times c$ grid-block designs with elements in GF(q). We define an ordered list of differences of A as follows:\\ \begin{center} $\vec{\partial} A$=$(a_{jl}-a_{il}:1\le i < j \le r,1\le l\le c)+(a_{lj}-a_{li}:1\le l \le r,1 \le i