% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P24}{20(1)}{2013} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % 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 % 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} % MATH ----------------------------------------------------------- \newcommand{\F}{\mathcal{F}} \newcommand{\ES}{\mathcal{S}} \newcommand{\ER}{\mathcal{R}} \newcommand{\PP}{\mathcal{P}} \newcommand{\C}{\mathcal{C}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\ol}{\overline} % MATH end ------------------------------------------------------ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf On a class of highly symmetric $k$--factorizations} % 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{Tommaso Traetta\\ \small Dipartimento di Matematica\\[-0.8ex] \small Universit\`a degli Studi di Roma ``La Sapienza''\\[-0.8ex] \small 00185 Roma, Italy\\ \small\tt traetta@mat.uniroma1.it\\ } \date{\dateline{Mar 20, 2012}{Aug 23, 2012}{Feb 5, 2013}\\ \small Mathematics Subject Classifications: 05C70, 20B25} \begin{document} \maketitle \begin{abstract} A $k$--factorization of $K_v$ of type $(r,s)$ consists of $k$--factors each of which is the disjoint union of $r$ copies of $K_{k+1}$ and $s$ copies of $K_{k,k}$. By means of what we call the {\it patterned} $k$--factorization $\F_k(D)$ over an arbitrary group $D$ of order $2s+1$, it is shown that a $k$-factorization of type $(1,s)$ exists for any $k \geq 2$ and for any $s \geq 1$ with $D$ being an automorphism group acting sharply transitively on the factor--set. %A general construction based on an arbitrary $1$--factorization of $K_{2s+2}$ allows us to The general method to construct a $k$-factorization $\F$ of type $(1,s)$ over an arbitrary $1$--factorization $\ES$ of $K_{2s+2}$ ($\F$ is said to be {\it based on $\ES$}) is used to prove that the number of pairwise non--isomorphic $k$--factorizations of this type goes to infinity with $s$. In this paper, we show that the full automorphism group of $\F$ is known as soon as we know the one of $\ES$. In particular, the full automorphism group of $\F_k(D)$ is determined for any $k\geq2$, generalizing a result given by P.\,J.~Cameron for patterned $1$--factorizations [J London Math Soc 11 (1975), 189--201]. Finally, it is shown that $\F_k(D)$ has exactly $(k!)^{2s+1}(2s+1)|Aut(D)|$ automorphisms whenever $D$ is abelian. % keywords are optional \bigskip\noindent \textbf{Keywords:} ($1$-rotational) $k$--factorization; automorphism group. \end{abstract} \section{Introduction} Let $V$ and $W$ be sets of size $v$ and $w$, respectively. As usual we denote by $K_v$ the {\it complete graph} on $v$ vertices and by $K_V$ the complete graph with vertex--set $V$. Also, by $K_{V,W}$ we denote the {\it complete bipartite graph} with parts $V$ and $W$ and by $K_{v,w}$ any complete bipartite graph with parts of size $v$ and $w$. For any simple graph $\Gamma$, the vertex--set and the edge--set of $\Gamma$ will be denoted by $V(\Gamma)$ and $E(\Gamma)$, respectively. A $k$--regular spanning subgraph of $K_v$ is a {\it $k$-factor} and a set $\F$ of edge--disjoint $k$--factors whose edges partition $E(K_v)$ is a {\it $k$--factorization of $K_v$}. It is easily seen that for a $k$--factorization of $K_v$ to exist we must have $kv \equiv 0 \pmod{2}$ and $v-1 \equiv 0 \pmod{k}$; in particular, $k$ and $v-1$ must have the same parity. % Except when $k=1$, the $k$--factors of a $k$--factorization $\F$ are not necessarily pairwise isomorphic. When it happens, $F$ is said to be {\it uniform}. In this paper, we will only deal with uniform $k$--factorization. An {\it automorphism} of a $k$-factorization $\F$ of $K_V$ is a permutation $\varphi$ of $V$ preserving $\F$, namely, $\varphi(F) \in \F$ for any $F \in \F$. The set of all automorphisms of $\F$ is a group which is called the {\it full automorphism group of $\F$} and usually denoted by $Aut(\F)$. Any subgroup of $Aut(\F)$ is an {\it automorphism group of $\F$}. It is very well known that a $1$--factorization of $K_{2n}$ exists for any $n$. For a given multiplicative group $D$ (not necessarily abelian!) of order $2n-1$, one can be constructed as follows. Set $P = \{[\infty, 1]\} \ \cup \ \{[x, x^{-1}] \ | \ x \in D\setminus \{1\}\}$ (where $\infty$ is an element not belonging to $D$) and let $P_d = Pd$, for any $d \in D$. Of course, $P_d$ is the $1$--factor that we get from $P$ by replacing any vertex $x \neq \infty$ with $xd$ hence, $P_1 = P$. It is known (see \cite{Bu00} for a proof when $D$ is not necessarily abelian!) that the set $\PP = \{P_d \ | \ d \in D\}$ turns out to be a $1$--factorization of $K_{D \cup \{\infty\}}$ and throughout the paper it will be referred to as the {\it patterned $1$--factorization over $D$}. % By construction, $D$ is a group of automorphisms of $\ES$ since the translation by any element of $D$ preserves $\ES$. In \cite{Ca75} the full automorphism group of $\PP$ is determined whenever $D$ is abelian.\\ Many other papers deal with $1$--factorizations of $K_v$ with a certain degree of symmetry, namely, with an automorphism group acting somehow regularly on either the vertex--set or the edge-set or the factor--set (see, for example, \cite{BoBuMa06, BoLa02, Bu01, HaRo85, MaRi09, Ri05}). Note that a $k$--factorization $\F$ with $k \geq 2$ is not necessarily made up of isomorphic $k$--factors. When this happens $\F$ will be called {\it uniform}. In this paper we will only deal with uniform $k$--factorizations. The main problem concerning the existence of a uniform $k$--factorization consists of establishing whether for a given $k$--factor $F$ of $K_v$ there exists a $k$--factorization whose factors are copies of $F$. When $k=2$ then $F$ is nothing but the disjoint union of $t$--cycles of length $\ell_1, \ell_2, \ldots, \ell_t$ with $\sum \ell_i = v$. In this case the problem is briefly denoted by OP$(\ell_1, \ell_2, \ldots, \ell_t)$ and it is known as the {\it Oberwolfach problem} (see \cite{BrRo07}). Although there are many infinite sets of parameters $\ell_1, \ell_2, \ldots, \ell_t$ for which the problem has been solved (see \cite{BrSch09, BuRi08, BuTr11, OlWil11, RiTr11, Tr12} for some recent results), the problem remains open. It is worth pointing out that most of the above cited papers provide solutions satisfying some conditions of symmetry such as the existence of an automorphism group fixing one vertex and acting semiregularly on the others. Generally speaking, a $k$--factorization $\F$ of $K_v$ is said to be {\it $1$--rotational} under a group $G$ if the vertices of $K_v$ can be renamed over $G \cup \{\infty\}$, $\infty \not\in G$, in such a way that the action of $G$ on the vertices by right multiplication (with the condition $\infty g = \infty$ for any $g \in G$) preserves $\mathcal{F}$, namely, $Fg \in \mathcal{F}$ for any $F \in \mathcal{F}$ and $g \in G$. Of course, the graph $Fg$ is obtained by replacing each vertex of $F$, say $x$, with $xg$. In particular, the patterned $1$--factorization over $D$ is $1$--rotational over the same group $D$.\\ % Nonetheless, % Although the problem is still open, it is reasonable to believe that apart from $OP(4,5)$ and OP$(3,3,5)$, none of which has a solution, any other instance of the Oberwolfach problem is solvable. As $k$ increases, the structure of an arbitrary $k$--factor of $K_v$ can be much more involved and the general existence problem appears much more difficult to face. We refer the reader to \cite{Ad09, RoHu12} for some recent results on cubic ($k=3$) factorizations. In this paper, we restrict our attention to $k$--factors which are the union of complete graphs and bipartite complete graphs. For $k\geq 2$, let $F$ denote a $k$--factor with the following structure: \[ F = \underbrace{K_{k+1} \ \cup \ldots \cup \ K_{k+1}}_{\text{$r$--times}} \cup \underbrace{K_{k,k} \ \cup \ldots \cup \ K_{k,k}}_{\text{$s$--times}} \] for some non--negative integers $r$ and s. % Such a $k$--factor is briefly denoted by $F_k(r,s)$. A $k$--factorization of $K_v$ whose factors are copies of $F$ will be called a $k$--factorization of {\it type $(r,s)$}. Of course, $v = r(k+1) + 2sk$ and for such a factorization to exist we must have $v \equiv 1 \pmod k$, hence $r \equiv 1 \pmod k$. This means that a necessary condition for the existence of $k$--factorization of type $(r,s)$ is that the number $r$ of complete graphs in any of its factors is $\equiv 1 \pmod k$ thus $r \geq 1$. Even with such a strong restriction on the structure of a $k$--factor the problem is almost completely open even in the most studied case, i.e., $k=2$. This instance of the Oberwolfach problem, i.e., OP$(\underbrace{3, \ldots, 3}_{\text{$r$--times}}, \underbrace{4, \ldots, 4}_{\text{$s$--times}})$, has been solved only when $r$ is odd and either $s=0$ (in this case we have a Kirkman Triple system KTS(v) of order $v$ whose existence has been proven in \cite{ChaWi71}), or $s=1$ \cite{DeFraMeRo97} and whenever $s \geq 0$ and $r=1$ (\cite{BrRo07}, see also \cite{BuRi08}). The case $r=1$ which is OP$(3,4,\ldots,4)$ is somewhat peculiar and it has been treated in \cite{BuRi08, Tr10}. The former paper shows that a $1$--rotational solution to such a problem can be easily constructed over the dihedral group. In \cite{Tr10} the full automorphism group of such a solution is completely determined, providing a lower bound for the number of non--isomorphic solutions to OP$(3,4,\ldots,4)$. The aim of this paper is to show that as in \cite{Tr10} we can construct a highly symmetric $k$--factorization of $K_v$ of type $(1,s)$ for any $k \geq 2$ and for any $s\geq 1$. In Section 2 we construct such a factorization over an arbitrary $1$--factorization of $K_{2s+2}$ and we prove that the number of pairwise non--isomorphic $k$--factorizations of type $(1,s)$ is at least as large as the number of non--isomorphic $1$--factorizations of $K_{2s+2}$. The $k$--factorization we obtain when starting from $\PP$ is called the {\it patterned $k$--factorization over $D$}. In Section 3 we completely determine its full automorphism group and we also determine its size when $D$ is abelian. \section{The existence of $k$--factorizations of type $(1,s)$} In this section we construct a $k$--factorization of type $(1,s)$ for any positive integers $k \geq 2$ and $s$, generalizing the construction given in \cite{BuRi08} when $k=2$. \\ Let $D$ be a set of order $2s+1$ and let $\infty$ be an element not belonging to $D$. Also, let $\ES$ be a $1$--factorization of $K_{D \cup \{\infty\}}$. We are going to construct the requested $k$--factorization over the complete graph $K_{(I_k \times D) \cup \{\infty\}}$, where $I_k=\{1,2,\ldots,k\}$. Consider the partition of $I_k \times D$ into the sets $A_d = I_k \times \{d\}$ with $d\in D$ and let $F_d$ be the $k$--factor defined as follows: $$F_d = K_{A_d \cup \{\infty\}} \cup \bigcup_{\stackrel{[x,y]\in S_d}{x \neq \infty \neq y}} K_{A_x, A_y}$$ where $S_d$ denotes the factor of $\ES$ containing the edge $[\infty, d]$, for any $d \in D$. It is worth mentioning that by means of the {\it circle product $\circ$} defined in \cite{RiTr11}, one can see that $F_d$ is nothing but the product of $K_{I_k \cup \{\infty\}}$ and $S_d$, i.e. $F_d = K_{I_k \cup \{\infty\}} \circ S_d$. We claim that the set $\F_k(\ES) = \{F_d \ | \ d \in D\}$ is a $k$--factorization of $K_{I_k \times D \cup \{\infty\}}$ of type $(1,s)$. Since $\F_k(\ES)$ contains the right number of $k$--factors, we only need to prove that they are edge--disjoint. First of all note that $K_{A_x \cup \{\infty\}}$ and $K_{A_x, A_y}$ are edge-disjoint for any $x, y \in D$. Also, any two distinct complete graphs of the form $K_{A_x \cup \{\infty\}}$ only share the vertex $\infty$ hence, they do not have a common edge. Finally, note that two complete bipartite graphs $K_{A_{x_1}, A_{y_1}}$ and $K_{A_{x_2}, A_{y_2}}$ share an edge if and only if $[x_1, y_1] = [x_2, y_2]$. From the above considerations easily follows that all $k$--factors of $\F_k(\ES)$ are edge disjoint and then partition the edge--set of $K_{I_k \times D \cup \{\infty\}}$. We will call $\F_k(\ES)$ the {\it $k$--factorization based on $\ES$}. Our simple construction leads to non--isomorphic $k$--factorizations of type $(1,s)$ as soon as we start from non--isomorphic $1$--factorizations. More precisely, \begin{proposition}\label{noniso} If $\ES$ and $\ol{\ES}$ are two non--isomorphic $1$--factorizations, then $\F_k({\ES})$ and $\F_k(\ol{\ES})$ are non--isomorphic. \end{proposition} \begin{proof} Let $\F_k(\ES) = \{F_d \ | \ d \in D\}$ and $\F_k(\ol{\ES})=\{\ol{F}_d \ | \ d \in D\}$ be the two $k$--factorizations based on $\ES$ and $\ol{\ES}$, respectively, and consider an isomorphism $\psi$ between $\F_k(\ES)$ and $\F_k(\ol{\ES})$. Since for any $d \in D$ there exists $d' \in D$ such that $\psi(F_d) = \ol{F}_{d'}$ we have, in particular, that $\psi(K_{A_d \cup \{\infty\}}) = K_{A_{d'} \cup \{\infty\}}$. Therefore, if we prove that $\psi$ fixes $\infty$ we will necessarily have that $\psi(A_d) = A_{d'}$, i.e., $\psi$ permutes the $A_d$'s. By contradiction, assume there exists an element $(i, a) \in I_k \times D$ such that $\psi(i,a) = \infty$. Then for any $b \neq a$ we would have that $\psi(K_{A_b \cup \{\infty\}})$ is a complete graph not passing through $\infty$ % lying in some factor of $\F_k(\ol{\ES})$ which contradicts the consideration above.\\ Now, denote by $S_d$ ($\ol{S}_d$) the factor of $\ES$ ($\ol{\ES}$) containing the edge $[\infty, d]$, for any $d \in D$, and consider the permutation $\varphi$ of $D \ \cup \ \{\infty\}$ fixing $\infty$ and such that $\varphi(x) = y$ if and only if $\psi(A_x) = A_y$. We are left to prove that $\varphi$ is an isomorphism between $\ES$ and $\ol{\ES}$ which means that for a given $d \in D$ we have $\varphi(S_d) = \ol{S}_{d'}$, where $d' = \varphi(d)$. Of course, $\varphi([\infty, d]) = [\infty, d']$. Now, let $[x,y] \in S_d\setminus\{[\infty, d]\}$. Since $\psi(F_d) = \ol{F}_{d'}$, there exists $\bar{x}, \bar{y} \in D$ such that $\psi(K_{A_{x}, A_{y}}) = K_{A_{\bar{x}}, A_{\bar{y}}} \in \ol{F}_{d'}$ hence, $\varphi([x,y]) = [\bar{x}, \bar{y}] \in \bar{S}_{d'}$. We then conclude that $\varphi$ is an isomorphism between $\ES$ and $\ol{\ES}$ and the proof is complete. \end{proof} It is very well known (see \cite{Wa97}) that the number $N(2n)$ of pairwise non--isomorphic $1$--factorizations of $K_{2n}$ goes to infinity with $n$; more precisely, $\ln N(2n) \sim 2n^2\ln(2n)$ \cite{Ca76}. Therefore, we have: \begin{corollary} The number of pairwise non isomorphic $k$--factorizations of type $(1,s)$ is at least as the number of pairwise non--isomorphic $1$--factorizations of $K_{2s+2}$ and it goes to infinity with $s$. \end{corollary} Now, assume that $D$ is a multiplicative group (not necessarily abelian!) and let $\ER$ be a $1$--rotational $1$--factorization over $D$. Also consider the action of $D$ on $I_k \times D \ \cup \ \{\infty\}$ by right translation defined by $\infty d = \infty$ and $(i,x)d = (i,xd)$ for any $d \in D$ and for any $(i,x) \in I_k \times D$. The reader can easily check that $F_x \cdot d = F_{xd}$ for any $x,d \in D$ meaning that the $k$--factorization $\F_k(\ER)$ based on $\ER$ admits $D$ as an automorphism group acting sharply transitively on the factor--set. % When writing $\F_k(\ER)$ (with $\ER$ being ) it will be understood that $D$ is a group of order $2s+1$. Recall that the patterned $1$--factorization $\PP$ over $D$ is $1$--rotational over the same group $D$. The $k$--factorization based on $\PP$ will be denoted by $\F_{k}(D)$ and referred to as the {\it patterned $k$--factorization over $D$}. The arguments given so far allow us to state the following result. \begin{proposition} For any $k\geq 2$, any $s\geq 1$ and any group $D$ of order $2s+1$ there exists a $k$--factorization of type $(1,s)$ with $D$ being an automorphism group acting sharply transitively on the factor--set. \end{proposition} \begin{proof} For a given group $D$ of order $2s+1$, $\F_k(D)$ provides the requested $k$--factorization for any $k \geq 2$ and any $s \geq 1$. \end{proof} It is worth pointing out that the patterned $2$--factorization has been defined in \cite{BuRi08} over the cyclic group $\Z_{2s+1}$. Reviewing $I_2$ as the cyclic group $\Z_2$ of order $2$ the authors proved that $\F_2(\Z_{2s+1})$ is $1$--rotational under the direct product $\Z_2 \times \Z_{2s+1}$. In order to show that $\F_k(D)$ is $1$--rotational under many different groups we need to recall the following facts. A semidirect product $G \ltimes_{\theta} D$ with $\theta : G \rightarrow Aut(D)$ being an homomorphism is defined over the cartesian product $G \times D$ with the binary operation $* : (g_1, d_1) * (g_2, d_2) = (g_1 g_2, d_1^{g_2}d_2)$, where $d_1^{g_2} = \theta(g_2)(d_1)$. The holomorph Hol(D) of $D$ is usually defined as the semidirect product $Aut(D) \ltimes_{\theta} D$ where $\theta$ is the identity map. If we denote by $\tau_d$, $d \in D$, the right transltion by $d$ which fixes $\infty$ and maps $x$ to $xd$, for any $x \in D$, and let $\tau_D$ be the group of all right translations over $D$ then $Hol(D)$ can also be represented as the group generated by $\tau_D$ and $Aut(D)$, i.e., $Hol(D) \simeq \langle Aut(D), \tau_D\rangle$. One can easily see that the holomorph of $D$ is an automorphism group of $\PP$ fixing $\infty$. The converse, when $D$ is abelian, has been proven in \cite{Ca75}: \begin{proposition} \label{Cam75} If $D$ is abelian, then any automorphism of the patterned $1$--factorization $\PP$ fixing $\infty$ lies in $Hol(D)$. \end{proposition} Now recall that the dihedral group $D_{4s+2}$ of order $4s+2$ can be defined as the semidirect product $\Z_2 \ltimes_{\theta} \Z_{2s+1}$ with $\theta$ mapping the generator of $\Z_2$ to the inverse map of $D$. In \cite{BuRi08} the authors prove that $\F_2(Z_{2s+1})$ is $1$--rotational under the dihedral group of order $4s+2$ and in \cite{Tr10} it is observed (without proof!) that it is actually $1$--rotational under any semidirect product $\Z_2 \ltimes_{\theta} \Z_{2s+1}$. A more general result will be now proven for any $k\geq 2$. \begin{proposition} Let $D$ and $G$ be groups of order $2s+1$ and $k$, respectively. Then the patterned $k$--factorization over $D$ is $1$--rotational under any semidirect product $G \ltimes D$. \end{proposition} \begin{proof} Rename the elements of $I_k$ over the ones in $G$. Then $A_d = G \times \{d\}$ for any $d \in D$ and $\F_k(D)$ becomes a $k$--factorization of $K_{G \times D \cup \{\infty\}}$. Since $(g,d)*(a,b) = (ga, d^ab) \in G \times \{d^ab\}$, it follows that $A_d*(a,b) = A_{d^ab}$. Note that $\tau_b\theta(a) \in Hol(D)$ hence, it is an automorphism of $\ES$ mapping $S_d$ to $S_{d^ab} \in \ES$. Therefore, we have \[ \begin{aligned} F_d * (a,b) &= K_{d^ab} \cup \bigcup_{\stackrel{[x,y] \in S_d}{x\neq\infty\neq y}} K_{A_{x^ab}, A_{y^ab}} \\ % &= K_{d^ab} \cup \bigcup_{\stackrel{[x,y] \in \tau_b\theta(a)(S_d)}{x\neq\infty\neq y}} K_{A_{x}, A_{y}} \\ &= K_{d^ab} \cup \bigcup_{\stackrel{[x,y] \in S_{d^ab}}{x\neq\infty\neq y}} K_{A_{x}, A_{y}} = F_{d^ab} \end{aligned} \] for any $d\in D$ which means that the right multiplication by any element of $G \ltimes_{\theta} D$ leaves $\F_{k}(D)$ invariant. The conclusion follows. \end{proof} We leave to the reader the easy task to show that starting from any $1$--rotational $1$--factorization $\ES$ over $D$, the $k$--factorization $\F_k(\ES)$ is actually $1$--rotational under the direct product $G \times D$ with $G$ being an arbitrary group of order $k$. \section{The full automorphism group of a patterned $k$--factorization} Let $D$ be a set of order $2s+1$ and let $\ES = \{S_d \ | \ d \in D\}$ be a $1$--factorization of $K_{D \ \cup \ \{\infty\}}$ with $S_d$, $d \in D$, denoting the factor of $\ES$ containing $[\infty, d]$. In this section we show that the full automorphism group of $\F_k(\ES)$ is linked to that of $\ES$. After that we completely determine the full automorphism group of a patterned $k$--factorization over an abelian group. From now on $\F_k(\ES)$ will be simply denoted by $\F$ and we will also refer to the sets $A_d$'s as the {\it parts} of $\F$. First, we prove the following result. \begin{proposition} Each automorphism $\psi$ of $\F$ fixes $\infty$ and permutes its parts, namely, for any $d \in D$ there exists $d' \in D$ such that $\psi(A_d) = A_{d'}$. \end{proposition} \begin{proof} It is enough to review the first part of the proof of Proposition \ref{noniso}, with $\ol{\ES} = \ES$. \end{proof} Now, we define two different types of automorphisms of $\F$. Denote by $Aut_{\infty}(\ES)$ the group of the automorphisms of $\ES$ fixing $\infty$. For a given $\varphi \in Aut_{\infty}(\ES)$ we call a {\it lift of $\varphi$} the permutation $\ol{\varphi}$ of $I_k \times D \ \cup \ \{\infty\}$ which fixes $\infty$ and maps any element $(i, d) \in I_k \times D$ to $(i, \varphi(d))$. It is easy to check that the set $\ol{Aut_{\infty}(\ES)} = \{\ol{\varphi} \ | \ \varphi \in Aut_{\infty}(\ES)\}$ of all {\it lifted automorphisms} is a group. We are about to prove that it is actually an automorphism group of $\F$. \begin{proposition} $\ol{Aut_{\infty}(\ES)}$ is an automorphism group of $\F$. \end{proposition} \begin{proof} Consider an automorphism $\varphi$ of $\ES$ fixing $\infty$. For a given $d \in D$, there exists $d' \in D$ such that $\varphi(S_d) = S_{d'}$; in particular, $\varphi(d) = d'$ and the edges $[\varphi(x), \varphi(y)]$ cover all edges of $S_{d'}\setminus \{[\infty, d']\}$ as $[x,y]$ runs over $S_d\setminus \{[\infty, d]\}$. Therefore, we have: \[ \begin{aligned} \ol{\varphi}(F_d) & = K_{A_{\varphi(d)} \cup \{\infty\}} \cup \bigcup_{\stackrel{[x,y] \in S_d}{x\neq \infty \neq y}} K_{A_{\varphi(x)}, A_{\varphi(y)}} \\ & = K_{A_{d'} \cup \{\infty\}} \cup \bigcup_{\stackrel{[x,y] \in S_{d'}}{x\neq \infty \neq y}} K_{A_{x}, A_{y}} = F_{d'} \end{aligned} \] The conclusion easily follows. \end{proof} We now introduce a different type of automorphism of $\F$. Let $\sigma$ be a permutation of $I_k \times D \ \cup \ \{\infty\}$ fixing $\infty$ and preserving each part, i.e., $\sigma(A_d) = A_d$ for any $d \in D$. Since $\sigma$ fixes any complete graph of the form $K_{A_d} \cup \{\infty\}$ and any bipartite complete graph of the form $K_{A_x, A_y}$, it follows that $\sigma$ is an automorphism of $\F$ with the further property that each of its factors is fixed by $\sigma$. Such an automorphism is called a {\it vertical automorphism} and the set of all such automorphisms will be denoted by $\Sigma$. It is straightforward that $\Sigma$ is an automorphism group of $\F$ and to describe its structure we denote by $\Sigma_d$, $d \in D$, the subgroup of $\Sigma$ consisting of those automorphisms fixing each element not belonging to $A_d$. \begin{proposition} The group $\Sigma$ of the vertical automorphisms of $\F$ is a normal subgroup of $Aut(\F)$ and it is the direct product of the $\Sigma_d$s, namely, $ \Sigma = \times_{d \in D} \Sigma_d$. In particular, $|\Sigma| = (k!)^{2s+1}$. \end{proposition} \begin{proof} To prove that $\Sigma$ is a normal subgroup we need to check that for any $\sigma \in \Sigma$ and any $\psi \in Aut(\F)$ we have $\psi^{-1} \sigma \psi\in \Sigma$. Indeed, for any $d, d' \in D$ such that $\psi(A_d) = A_{d'}$ we have that $\psi^{-1} \sigma \psi (A_d) = \psi^{-1} \sigma (A_{d'}) = \psi^{-1} (A_{d'}) = A_d$, hence $\psi^{-1} \sigma \psi$ is vertical.\\ Now, let $\sigma$ be a vertical automorphisms of $\PP$ and for any $d \in D$ define $\sigma_d \in \Sigma_d$ as follows: \[ \sigma_d(x) = \begin{cases} \sigma(x) \quad\mbox{ if $x \in A_d$;}\cr x \quad\quad\mbox{ otherwise.} \end{cases} \] It is easy to check that $\sigma$ decomposes into the product of the $\sigma_d$'s, i.e., $\sigma = \prod_{d \in D} \sigma_d$, and that such a decomposition is unique up to the order. This is enough to state that $\Sigma = \times_{d \in D} \Sigma_d$. Since $D$ has order $2s+1$ and $|\Sigma_d| = k!$ we get $|\Sigma| = (k!)^{2s+1}$. \end{proof} Note that a non trivial lifted automorphism $\ol{\varphi}$ moves at least one $k$--factor of $\F$ since there exists at least an element $d \in D$ such that $\varphi(d) \neq d$ and then $\ol{\varphi}(F_d) = F_{\varphi(d)} \neq F_d$. On the other hand a vertical automorphism fixes each $k$--factor of $\F$. Therefore we conclude that $\Sigma \cap Aut_{\infty}(\ES) = \{id\}$. We are now able to describe the structure of the full automorphism group of $\F$. \begin{theorem} The full automorphism group of the $k$--factorization $\F$ based on $\ES$ is generated by all lifted and vertical automorphisms, namely, $Aut(\F) = \Sigma \ol{Aut_{\infty}(\ES)}$. In particular, it has at least $(k!)^{2s+1}$ automorphisms. % In particular, % $|Aut(\PP)| = (k!)^{2s+1}|Aut_{\infty}(\ES)|$. \end{theorem} \begin{proof} It is enough to prove that for any automorphism $\psi$ of $\F$ there exists a lifted automorphism $\ol{\varphi}$ such that $\psi \ol{\varphi}^{-1} \in \Sigma$. It will follow that $\psi \in \Sigma \ol{Aut_{\infty}(\ES)}$ and then $Aut(\F) = \Sigma \ol{Aut_{\infty}(\ES)}$.\\ Let $\psi$ be an automorphism of $\F$ and denote by $\varphi$ the permutation of $D \ \cup \ \{\infty\}$ fixing $\infty$ and such that $\varphi(x) = y$ if and only if $\psi(A_x) = A_y$, for any $x,y\in D$. We prove that $\varphi$ is an automorphism of $\ES$, namely, for a given $d \in D$ we have $\varphi(S_d) = S_{d'}$ where $d' = \varphi(d)$. Of course, $\varphi([\infty, d]) = [\infty, d']$. Now, let $[x,y] \in S_d\setminus\{[\infty, d]\}$. Since $\psi(F_d) = F_{d'}$, there exists $x', y' \in D$ such that $\psi(K_{A_{x}, A_{y}}) = K_{A_{x'}, A_{y'}} \in F_{d'}$ hence, $\varphi([x,y]) = [x', y'] \in S_{d'}$. It follows that $\varphi$ is an automorphism of $\ES$ and $\psi \ol{\varphi}^{-1}$ fixes each part, i.e., $\psi \ol{\varphi}^{-1} \in \Sigma$. The conclusion follows. \end{proof} As already mentioned in Proposition \ref{Cam75}, when $D$ is an abelian group and $\ES = \PP$ is the patterned $1$--factorization over $D$ then $Aut_{\infty}(\ES) = Hol(D)$ and we known that $|Hol(D)| = (2s+1)|Aut(D)|$. Therefore we get the following corollary. \begin{corollary} Let $D$ be an abelian group of order $2s+1$. The full automorphism group of the patterned $k$--factorization over $D$ has order $(k!)^{2s+1}(2s+1)|Aut(D)|$. \end{corollary} Recall that the full automorphism group of any abelian group can be easily computed. Hence, as a final application of the results above, we determine the order of $Aut(\F_k(D))$ for any abelian group $D$ of order $125$. There are exactly $3$ non-isomorphic abelian groups of such order: $D_1 = \Z_{125}$, $D_2 = \Z_5 \times \Z_{25}$ and $D_3 = \Z_5 \times \Z_5 \times \Z_5$. One can easily check that their full automorphism groups $Aut(D_i)$ have the following orders: $|Aut(D_1)| = 100$, $|Aut(D_2)| = 100\cdot 20 = 2000$, and $|Aut(D_3)| = 124 \cdot 120 \cdot 100 = 1488000$. Since $Aut(\F_k(D_i)) = (k!)^{125}(125)|Aut(D_i)|$, the three patterned $k$--factorizations constructed over the $D_i$'s have a different number of automorphisms hence, they are pairwise non--isomorphic. \begin{thebibliography}{99} \bibitem{Ad09} P. Adams, H. Ardal, J. Manuch, V.D. Hua, M. Rosenfeld, and L. Stacho, Spanning cubic graph designs, Discrete Math. 309 (2009), 5781--5788. \bibitem{AlSchStWa89} B. Alspach, P.J. Schellenberg, D.R. Stinson, and D. Wagner, {The Oberwolfach problem and factors of uniform odd length cycles}, J. Combin. Theory Ser. A {52} (1989), 20--43. \bibitem{BoBuMa06} {A. Bonisoli, M. Buratti, and G. Mazzuoccolo}, Doubly transitive $2$--factorizations, J. Combin. Des. 15 (2006), 120--132. \bibitem{BoLa02} {A. Bonisoli and D. Labbate}, One--factorizations of complete graphs with vertex--regular automorphism groups, J. Combin. Des. 10 (2002), 1--16. \bibitem{BrRo07} D. Bryant and C. Rodger, {Cycle decompositions}, in: C.J. Colbourn and J.H. Dinitz (Eds), The CRC Handbook of Combinatorial Designs, 2nd edition, CRC Press, Boca Raton, 2007, pp. 373--382. \bibitem{BrSch09} D. Bryant and V. Scharaschkin, {Complete solutions to the Oberwolfach problem for an infinite set of orders}, J. Combin. Theory Ser. B {99} (2009), 904--918. \bibitem{Bu00} M. Bu\-ratti, A description of any regular or $1$-rotational design by dif\-fer\-ence meth\-ods, Booklet of the abstracts of {\it Combinatorics $2000$}, pp. 35--52, \url{http://www.mat.uniroma1.it/~combinat/gaeta/Combinatorics2000.pdf}. \bibitem{Bu01} {M. Buratti}, Abelian $1$--factorizations of the complete graph, European J. Combin. 22 (2001), 291--295. \bibitem{BuRi08} M. Buratti and G. Rinaldi, {$1$--rotational $k$--factorizations of the complete graph and new solutions to the Oberwolfach problem}, J. Combin. Des. 16 (2008), 87--100. \bibitem{BuTr11} M. Buratti and T. Traetta, Starters, graceful labelings and a doubling construction for the Oberwolfach problem, J. Combin. Des., \doi{10.1002/jcd.21296}. \bibitem{Ca75} P.J. Cameron, Minimal edge--colourings of complete graphs, J. London Math. Soc. 11 (1975), 189--201. \bibitem{Ca76} P.J. Cameron, Parallelisms of Complete Designs, Cambridge Univ. Press, London, 1976 \bibitem{ChaWi71} D.K. Ray-Chaudhuri and R.M. Wilson, Solution of Kirkman's schoolgirl problem, Proc. Sympos. Pure Math. 19 (1971), 187--204. \bibitem{DeFraMeRo97} I.J. Dejter, F. Franek, E. Mendelsohn, and A. Rosa, Triangles in $2$--factorizations, J. Graph Theory 26 (1997), 83--94. \bibitem{HaRo85} {A. Hartman and A. Rosa}, Cyclic one--factorizations of the complete graph, European J. Combin. 6 (1985), 45--48. \bibitem{MaRi09} {G. Mazzuoccolo and G. Rinaldi}, $k$-pyramidal one-factorizations, Graphs Combin. 23 (2007), 315--326. \bibitem{OlWil11} M.A. Ollis and D.T. Willmott, {On twizzler, zigzag and graceful terraces}, Australas. J. Combin. 51 (2011), 243--257. \bibitem{Ri05} {G. Rinaldi}, Nilpotent one--factorizations of the complete graph, J. Combin. Des. 13 (2005), 393--405. \bibitem{RiTr11} G. Rinaldi and T. Traetta, {Graph products and new solutions to Oberwolfach problems}, Electron. J. Combin. 18 (2011) P52. \bibitem{RoHu12} M. Rosenfeld, V.D. Hua, Cubic factorizations, Discrete Math., \doi{10.1016/j.disc.2012.05.001}. \bibitem{Tr10} T. Traetta, {Some new results on $1$-rotational $2$-factorizations of the complete graph}, J. Combin. Des. 18 (2010), 237--247. \bibitem {Tr12} T. Traetta, A complete solution to the two-table Oberwolfach problems, preprint. \bibitem{Wa97} W.D. Wallis, One-Factorizations, Kluwer, Dordrecht, 1997. \end{thebibliography} \end{document}