ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ars mathematica contemporanea 8 (2015) 163-175
A note on m-factorizations of complete multigraphs arising from designs*
*
Gyorgy Kiss f
Department of Geometry andMTA-ELTE GAC Research Group Eötvös Lorand University 1117 Budapest, Pázmány s. 1/c, Hungary
Christian Rubio-Montiel *
Instituto de Matemáticas Universidad Nacional Autónoma de México Ciudad Universitaria, 04510, D.F., Mexico
Received 7 September 2013, accepted 8 May 2014, published online 28 September 2014 Abstract
Some new infinite families of simple, indecomposable m-factorizations of the complete multigraph AKv are presented. Most of the constructions come from finite geometries.
Keywords: Graph factorization, affine and projective spaces, spread. Math. Subj. Class.: 05C70, 51E23
1 Introduction
The complete multigraph AKv has v vertices and A edges joining each pair of vertices. An m-factor of the complete multigraph AKv is a set of pairwise vertex-disjoint m-regular subgraphs, which induce a partition of the vertices. An m-factorization of AKv is a set of pairwise edge-disjoint m-factors such that these m-factors induce a partition of the edges. An m-factorization is called simple if the m-factors are pairwise distinct. Furthermore, an m-factorization of AKv is decomposable if there exist positive integers and such
*The research was supported by the Mexican-Hungarian Intergovernmental Scientific and Technological Cooperation Project, Grant No. TET 10-1-2011-0471.
t Author was supported by the Hungarian National Foundation for Scientific Research, Grant Nos. K 72537 and K 81310.
* Author was partially supported by CONACyT of Mexico, Grant Nos. 166306 and 178395; and PAPIIT of Mexico, Grant No. IN101912.
E-mail addresses: kissgy@cs.elte.hu (Gyorgy Kiss), christian@matem.unam.mx (Christian Rubio-Montiel)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
164
Ars Math. Contemp. 8 (2015) 215-223
that + = A and the factorization is the union of the m-factorizations	and
,u2Kv, otherwise it is called indecomposable. There is no direct correspondence between simplicity and indecomposability.
Many papers deal with m-factorizations of graphs andmultigraphs. This is an interesting problem in its own right, but it is motivated by several applications, too. In particular if m = 1, then a one-factorization of Kv corresponds to a schedule of a round robin tournament. For a comprehensive survey on one-factorizations we refer to [29]. A special case of 2-factorizations is the famous Oberwolfach problem, see e.g. [2, 8]. Several authors investigated 3-factorizations of AKv with a certain automorphism group, see e.g. [1, 24]. In general, decompositions of AKv is also a widely studied problem, see e.g. [12, 13, 18, 27]. As m increases, the structure of an arbitrary m-factor of AKv can be much more complicated and the existence problem becomes much more difficult. In this paper we restrict ourselves to construct factorizations in which all factors are regular graphs of degree m whose connected components are complete graphs on (m +1) vertices. In the case m =1 an indecomposable one-factorization of AK2n is denoted by IOF(2n, A). Only a few conditions on the parameters are known: if IOF(2n, A) exists, then A < 1 • 3 • ... • (2n - 3) [4]; each IOF(2n, A) can be embedded in a simple IOF(2s, A), provided that A < 2n < s [16]. Six infinite classes of indecomposable one-factorizations have been constructed so far, namely a simple IOF(2n, n — 1) when 2n — 1 is a prime [16], IOF(2(A + p), A) where A > 2 and p is the smallest prime wich does not divide A [3] (an improvement of this result can be found in [15]), a simple IOF(2h + 2, 2) where h is a positive integer [28], IOF(q2 + 1, q — 1) where q is an odd prime number [26], a simple IOF(q2 + 1, q +1) for any odd prime power q [25], and a simple IOF(q2, q) for any even prime power q [25]. Most of these constructions arise from finite geometry.
The aim of this paper is to construct new simple and indecomposable m-factorizations of AKv for different values of m, A and v. In Section 2 we recall the basic combinatorial properties of designs and the geometric properties of finite affine and projective spaces. We also describe a general construction method of m-factorizations which is based on spreads of block designs. In Sections 3 and 4 affine spaces and projective spaces, respectively, are the key objects. We present several new multigraph factorizations using subspaces, subgeometries and other configurations of these structures.
2 Preliminaries
In this section we collect some concepts and results from design theory. For a detailed introduction to block designs we refer to [14].
2.1 Designs
Let v, b, k, r and A be positive integers with v > 1. Let D = (P, B, I) be a triple consisting of a set P of v distinct objects, called points of D, a set B of b distinct objects, called blocks of D, and an incidence relation I, a subset of P x B. We say that x is incident with y (or y is incident with x) if and only if the ordered pair (x, y) is in I. D is called a 2 — (v, b, k, r, A) design if it satisfies the following axioms.
(a)	Each block of D is incident with exactly k distinct points of D.
(b)	Each point of D is incident with exactly r distinct blocks of D.
(c)	If x and y are distinct points of D, then there are exactly A blocks of D incident with
G. Kiss and C. Rubio-Montiel: A note on m-factorizations of complete multigraphs
165
both x and y.
A 2 - (v, b, k, r, A) design is called a balanced incomplete block design and is denoted by (v, k, A)-design, too. The parameters of a 2 - (v, b, k, r, A) design are not all independent. The two basic equations connecting them are the following:
vr = bk and r(k - 1) = A(v - 1).	(2.1)
These necessary conditions are not sufficient, for example no 2 - (43,43, 7,7,1) design exists.
2.2 Resolvability
A resolution class (or, a parallel class) of a (v, k, A)-design is a partition of the point-set of the design into blocks. In general, an f -resolution class of a design is a collection of blocks, which together contain every point of the design exactly f times. A resolution of a design is a partition of the block-set of the design into r resolution classes. A (v, k, A)-design with a resolution is called resolvable.
Necessary conditions for the existence of a resolvable (v, k, A)-design are A(v -1) = 0 (mod (k - 1)), v = 0 (mod k) and b > v + r - 1, (see [9]).
Let D = (P, B, I) be a (v, k, A)-design, where P = {pi,p2,... ,pv} is the set of its points and B = {B1, B2,..., Bb} is the set of its blocks. Identify the points of D with the vertices of the complete multigraph AKv. Then in the natural way, the set of points of each block of D induces in AKv a subgraph isomorphic to Kk. For Bj G B, let Gj be the subgraph of AKv induced by Bj. Then it follows from the properties of D that a resolution class of D gives a (k - 1)-factor of AKv and a resolution of D gives a (k - 1)-factorization of AKv. Hence we get the following well-known fact.
Lemma 2.1 (Basic Construction). The existence a resolvable (v, k, A)-design is equivalent to the existence of a (k - 1)-factorization of the complete multigraph AKv.
2.3 Projective and affine spaces
Most of our factorizations come from finite geometries. In this subsection we collect the basic properties of these objects. For a more detailed introduction we refer to the book of Hirschfeld [22].
Let Vn+1 be an (n + 1)-dimensional vector space over the finite field of q elements, GF(q). The n-dimensionalprojective space PG(n, q) is the geometry whose k-dimensional subspaces for k = 0,1,..., n are the (k + 1)-dimensional subspaces of Vn+1 with the zero deleted. A k-dimensional subspace of PG(n, q) is called k-space. In particular subspaces of dimension zero, one and two are respectively a point, a line and a plane, while a subspace of dimension n - 1 is called a hyperplane.
The relation ~
x ~ y 0 = a G GF(q) : x = ay
is an equivalence relation on the elements of Vn+1 \ 0 whose equivalence classes are the points of PG(n, q). Let v = (v0, v1,..., vn) be a vector in Vn+1 \ 0. The equivalence class of v is denoted by [v]. The homogeneous coordinates of the point represented by [v] are (vo : v1 : ... : v„). Hence two (n + 1)-tuples (xo : X1 : ... : x„) and (yo : V1 : ... : Vn) represent the same point of PG(n, q) if and only if there exists 0 = a G GF(q) such that Xj = avi holds for i = 0,1,..., n.
166
Ars Math. Contemp. 8 (2015) 215-223
A k-space contains those points whose representing vectors x satisfy the equation xA = 0, where A is an (n +1) x (n — k) matrix of rank n — k with entries in GF(q). In particular a hyperplane contains those points whose homogeneous coordinates (x0 : x1 : ... : xn) satisfy a linear equation
U0X0 + UlXl + • • • + M„x„ = 0
where ui G GF(q) and (u0, u1,..., un) = 0.
The basic combinatorial properties of PG(n, q) can be described by the q-nomial coefficients. [k]q equals to the number of k-dimensional subspaces in an n-dimensional vector space over GF(q), hence it is defined as
nl _ (qn — 1)(qn — q) ... (qn — qk-1) k q := (qk — 1)(qk — q) ... (qk — qk-1) .
The proof of the following proposition is straightforward.
Proposition 2.2.
•	The number of k-dimensional subspaces in PG(n, q) is [n+] q.
•	The number of k-dimensional subspaces of PG(n, q) through a given d-dimensional (d < k) subspace in PG(n, q) is	.
•	In particular the number of k-dimensional subspaces of PG(n, q) through two distinct points in PG(n, q) is [n-] q.
If is any hyperplane of PG(n, q), then the n-dimensional affine space over GF(q) is AG(n, q) = PG(n, q) \ The subspaces of AG(n, q) are the subspaces of PG(n, q) with the points of deleted in each case. The hyperplane is called the hyperplane at infinity of AG(n, q), and for k = 0,1,..., n — 2 the k-dimensional subspaces in are called the k-spaces at infinity of AG(n, q). Let 1 < d < n be an integer. Two d-spaces of AG(n, q) are called parallel, if the corresponding d-spaces of PG(n, q) intersect in the same (d — 1)-space. The parallelism is an equivalence relation on the set of d-spaces of AG(n, q). As a straightforward corollary of Proposition 2.2 we get the following.
Proposition 2.3. In AG(n, q) each equivalence class of parallel d-spaces contains qn-d subspaces.
Projective and affine spaces provide examples of designs.
Example 2.4. Let i < n be positive integers. The projective space PG(n, q) can be considered as a 2-design D = (P, B, I), where P is the set of points of PG(n, q), B is the set of i-spaces of PG(n, q) and I is the set theoretical inclusion. The parameters of D are
- - q^11-1 b = rn+11 , k = , r = |"n] and A = fn-l .
U+1J q'	q— 1 '	LiJq	Li— 1J q
q-1 ' Ll+U q'	q-1 ' LiJq
Example 2.5. Let i < n be positive integers. The affine space AG(n, q) can be considered as a 2-design D = (P, B, I), where P is the set of points of AG(n, q), B is the set of i-spaces of AG(n, q) and I is the set theoretical inclusion. The parameters of D are v = q
b = qn-itn ]q, k = ql, r = tn ]q and A = fn-1]
n
G. Kiss and C. Rubio-Montiel: A note on m-factorizations of complete multigraphs
167
In the rest of this paper Examples 2.4 and 2.5 will be denoted by PG(i)(n, q) and by AG(i)(n, q), respectively. We will use the terminology from geometry. An i-spread, S% of PG(n, q) (or of AG(n, q)) is a set of pairwise disjoint i-dimensional subspaces which gives a partition of the points of the geometry. In general, an f -fold i-spread, Sf, is a set of i-dimensional subspaces such that every point of the geometry is contained in exactly f subspaces of SJ. An i-packing, P1, of PG(n, q) (or of AG(n, q)) is a set of spreads such that each i-dimensional subspace of the geometry is contained in exactly one of the spreads in Pi.e., the spreads give a partition of the i-dimensional subspaces of the geometry. The i-spreads, f -fold i-spreads and i-packings induce a resolution class, an f-resolution class and a resolution in PG(i) (n, q) (or in AG(i) (n, q)), respectively.
It is easy to construct spreads and packings in AG(i) (n, q), because each parallel class of i-spaces is an i-spread. The situation is much more complicated in PG(i)(n, q). There are only a few constructions of spreads. The following theorem summarizes the known existence conditions.
Theorem 2.6 ([22], Theorems 4.1 and 4.16).
•	There exists an i-spread in PG(j) (n, q) if and only if (i + 1) | (n + 1).
•	Suppose that i, l and n are positive integers such that (l +1)| gcd(i +1, n +1). Then there exists an f -fold i-spread in PG(j)(n, q), where f = (qj+1 — 1)/(q1+1 — 1).
There exist several different 1-spreads (line spreads) in PG(1)(3,q). We briefly mention two types. Let ¿1, and ¿3 be three skew lines in PG(3, q). The set of the q + 1 transversals of ¿1, ¿2 and ¿3 is called regulus and it is denoted by ¿2, ¿3). The classical construction of a line spread comes from a pencil of hyperbolic quadrics (see e.g. [20], Lemma 17.1.1) and it has the property that if it contains any three lines of a regulus ¿2, ¿3), then it contains each of the q + 1 lines of ¿2, ¿3). This type of spread is called regular. A line spread in PG(3, q) is called aregular, if it contains no regulus. An example of an aregular spread can be found in [20], Lemma 17.3.3.
3 Factorizations arising from affine spaces
In this section, we investigate the spreads and packings of AG(n, q) and the corresponding factorizations of multigraphs. In each case we apply Lemma 2.1, so we identify the points of AG(n, q) with the vertices of the complete multigraph.
Theorem 3.1. Let q be a prime power, i < n be positive integers and Aj = . Then there exists a simple (qj — 1 )-factorization Fj of Aj Kqn. Fj is decomposable if and only if there exists an f-fold (i — 1)-spread in PG(j-1)(n — 1, q) for some 1 < f < Aj.
Proof. Consider the n-dimensional affine space as AG(n, q) = PG(n, q) \ where is isomorphic to PG(n — 1, q). Take the design D = AG(j)(n, q) and apply Lemma 2.1. If nj-1 is an (i — 1)-space of , then the set of the qn-j parallel affine i-spaces through nj-1 is an i-spread of D. This spread induces a (qj — 1)-factor Fj for j e {1,..., r}. If n-1, n2-1,..., ng-1 are distinct (i — 1)-spaces of and they form an f-fold spread, then f = (g(qj — 1))/(qn — 1), and the union of the corresponding (qj — 1)-factors Fj for j = 1,2,..., g, gives a (qj — 1)-factorization of f Kqn. Distinct (i — 1)-spaces of
168
Ars Math. Contemp. 8 (2015) 215-223
obviously define distinct (q® - 1)-factors, so this factorization is simple. In particular if we consider all (i - 1)-spaces of then
n	, f = q	n	q4	-1	n - 1
i		i	q qn	-1	i-1
hence the union of the corresponding factors gives a simple (q® - 1)-factorization F® of
A®Kqn .
Suppose that F® is decomposable, then there exist two positive integers and such that + = A® and F® can be written as the union F® = F1 U F2; F1 and F2 are (q® - 1)-factorizations of	and , respectively, having no (q® - 1)-factors in
common, since F® is simple. For h = 1,2, the relation ) = (2)qn—®|Fh| holds, hence - 1) = (q® - 1)|Fh|. Without loss of generality we can set F1 = uf=1Fj® with /1 = (M1(qn - 1))/(q® - 1), and F2 = F® \F1, /2 = |F2|.
Let u1 and u2 be two affine points and let w be the point at infinity of the line u1u2. Since Fh is a factorization of , there are exactly factors of Fh containing the edge [u1, u2], say F® , F® ,..., F® . The edge [u1, u2] belongs the F® if and only if w G n®
J 1 J 2	J f-^fa	J s
for every 1 < s < This happens if and only if Uf= 1n
-1
exactly times, which means that Uf=1n® 1 is a ^h-fold spread in H
1 contains each point of for every
h = 1,2. It is thus proved that if F® is decomposable, then PG(® /-fold spread for some 1 < / < A®.
_1)(n - 1, q) posesses an
Vice versa, suppose that there exists a ^1-fold spread in PG(® 1) (n - 1, q) for some
1 < M1 < A®. Let F1 = Uf= 1Fj® be a ^1-fold spread in Then |F1| = /1 = ^1(qn -1)/(q® - 1). Let T be the set of all (i - 1)-dimensional subspaces in and let F2 = T\F1. Then |T| = [n1, hence
|F2|
- Mi(qn - 1)/(q4 - 1)
n - 1 i - 1

Mi
qn - 1 q4 - 1 ,
so if = ["_!] g - M1, then F2 is a ^2-fold spread in and 1 < < A® holds.
As we have already seen, Fh defines a (q® - 1)-factorization of	for h = 1, 2.
Then F® = F1 U F2, because + = A®. Hence the (q® - 1)-factorization F® of A®Kqn is decomposable.	□
A
g
q
q
q
Corollary 3.2. If gcd(i, n) > 1 then the (q® - 1)-factorization F® of A® is decomposable.
Proof. Let 1 < l + 1 be a divisor of gcd(i, n). Then it follows from Theorem 2.6 that there exists an (q® - 1)/(q1+1 - 1)-fold spread in so F® is decomposable.	□
To decide the decomposability of F® in the cases gcd(i, n) = 1 is a hard problem in general. We prove its indecomposability in the following important case.
Theorem 3.3. The (qn-1 - 1)-factorization Fn-1 of (qn-1 - 1)/(q - 1)Kqn is indecomposable.
G. Kiss and C. Rubio-Montiel: A note on m-factorizations of complete multigraphs
169
Proof. It is enough to prove that if ug=in" 2 is an /-fold (n - 2)-spread in then Ug=1n™-2 consists of all (n - 2)-dimensional subspaces of because this implies
/ = An-1, so the statement follows from Theorem 3.1 j "
ing of the point-subspace pairs p e nn 2 in gives
Each nn 2 contains exactly (qn 1 - 1)/(q - 1) points, thus the standard double count-
hence
qn-1 - 1 rqn - 1
g-r~ = f-^
q - 1	q - 1
f = g(qn-1 -1)
qn - 1
But gcd(qn - 1, qn-1 - 1) = q - 1 and / is an integer, so g > (qn - 1)/(q - 1) which implies g = (qn - 1)/(q - 1), hence / = An-1.	□
In particular if n = 2, we get the following.
Corollary 3.4. If q is a prime power then there exists a simple and indecomposable (q -1)-factorization of Kq2.
If q = 2r then each (q® - 1)-factor in F® is the vertex-disjoint union of 2r-® complete graphs on 2® vertices. It is well-known that these graphs can be partitioned into one-factors in many ways (but not in all the ways, it was proved by Hartman and Rosa [19], that there is no cyclic one-factorization of K2i for i > 3), hence Theorem 3.1 implies several one-factorizations of A®K2r.
Each of the one-factorizations arising from F® is simple, because distinct (i - 1)-dimensional subspaces define distinct (q® - 1)-factors of F®, and the one-factors of A®Kqn arising from distinct (q® - 1)-factors of F® are distinct, because they are the union of qn-® one-factors on q® vertices of a connected component.
There are both decomposable and indecomposable one-factorizations among these examples. We show it in the smallest case q = 2, n = 3. Let F2 be the 3-factorization of 3Kg induced by AG(3,2).
Let PG(3,2) = AG(3, 2) U Then is isomorphic to the Fano plane. Let its points be 0,1, 2,3,4, 5 and 6 such that for j = 0,1,..., 6, the triples Lj = (j, j +1, j + 3) form the lines of the plane, where the addition is taken modulo 7. Now the 3-factors of F2 can be described in the following way. Let a be a fixed point in AG(3,2). Then Lj defines a 3-factor Fj whose connected components are complete graphs K2i = K4. Let Ljja be the complete graph containing a, and let Lj a be the other component of Fj.
defines one-factors and a one-factorization of Kg in the following obvious way. The edge joining two points of AG(3, 2), say b and c, belong to the one-factor Gs if and only if b, c and s are collinear points in PG(3,2). Then G — U6_qGs is a one-factorization of Kg.
We can define a decomposable one-factorization of 3K8 in the following way. Take Lj a and Lj a and let s e Lj be any point. Then Gs gives a one-factor of Lj a and a one-factor of L^a. Hence Gj = UseLjGs is the union of three one-factors of 3Kg, and G' = u6=0Gj is a one-factorization of 3k8.
In there are three lines through the point s, hence G' contains each one-factor Gs three times. Thus G' is decomposable, because it is obviously the union of three copies of G.
170
Ars Math. Contemp. 8 (2015) 215-223
But we can define an indecomposable one-factorization, too. Let Lj be a line in take Lj,a and Lj,a and let Mj be the one-factor which contains the following pairs of points
in AG(3, 2) : '
-	(b, c) if b, c € Lj,a and 6, c, j are collinear in PG(3, 2).
-	(b, c) if b, c € Lj,a and b, c, j + 1 are collinear in PG(3,2).
Let Mj be the one-factor which contains the following pairs of points in AG(3, 2) :
-	(b, c) if b, c € Lj,a and b, c, j + 1 are collinear in PG(3,2).
-	(b, c) if b, c € Lj,a and b, c, j + 3 are collinear in PG(3,2).
Finally let Mj be the one-factor which contains the following pairs of points in AG(3,2) :
-	(b, c) if b, c € Lj,a and b, c, j + 3 are collinear in PG(3,2).
-	(b, c) if b, c € Lj,a and b, c, j are collinear in PG(3, 2).
Then Mj = uf=1 Mj is a union of three one-factors of 3K8, and M = U6=0Mj is a one-factorization of 3K8.
Suppose that this one-factorization is decomposable. Then it contains a one-factorization E of K8. E is the union of seven one-factors. We may assume without loss of generality, that M0j belongs to E. It contains an edge through a, let it be (a, b), and a pair (c, d) for which the lines ab and cd are parallel lines in AG(3,2). There are two more lines in the parallel class of ab, say ef and gh. It follows from the definition of the one-factors that exactly one of them contains the pairs (e, f) and (a, b), another one contains the pairs (e, f) and (c, d), and a third one contains the pairs (e, f) and (g, h). But E contains each pair exactly once, hence it must contain the one-factor containing the pairs (e, f) and (g, h). But this is a one-factor of type M0, where t =1. Hence E contains M0 where t = 2 or 3. If we repeat the previous argument, we get that E must contain M0 for 1 = l = t, too. Thus E is the union of triples of type Mj, t = 1, 2,3, but this is a contradiction, because E consists of seven one-factors.
4 Factorizations arising from projective spaces
There are two basic types of partitioning the point-set of finite projective spaces. Both types give factorizations of some multigraphs. In this section we discuss these constructions.
4.1 Spreads consisting of subspaces
It is easy to construct spreads in PG(i) (n, q), Theorem 2.6 gives a necessary and sufficient existence condition. Packings are much more complicated objects. Only a few packings in PG(1)( n, q) have been constructed so far. In each case of the known packings either n or q satisfies some conditions.
Theorem 4.1 (Beutelspacher, [6]). Let 1 < k be an integer and let n = 2k — 1. Then there exists a packing in PG(1)( n, q) .
Theorem 4.2 (Baker, [5]). Let 1 < k be an integer. Then there exists a packing in PG(1)(2k - 1, 2).
Applying the Basic Construction Lemma, we get the following existence theorems.
a — 1
Corollary 4.3. Let q be a prime power, 1 < k be an integer and v = aq-1 . Then there exists a q-factorization of Kv induced by a line-packing in PG(2k — 1, q).
G. Kiss and C. Rubio-Montiel: A note on m-factorizations of complete multigraphs
171
Corollary 4.4. Let 1 < k be an integer and v = qq-1 . There exists a 2-factorization K, induced by a line-packing in PG(2k — 1, 2).
If k = 2 then Corollary 4.4 gives a solution of Kirkman's fifteen schoolgirls problem, which was first posed in 1850 (for the history of the problem we refer to [7]), while Corollary 4.3 gives a solution of the generalised problem in the case of (q2 + 1)(q + 1) schoolgirls.
The complete classification of packings in PG(i)(n, q) is known only in the case i = 1, n = 3 and q = 2. There are 240 projectively distinct packings of lines in PG(3,2) (see [20], Subsection 17.5).
If gcd(q +1, 3) = 3, then there is a construction of aregular spreads in PG(1)(3,q) due to Bruen and Hirschfeld [11] which is completly different from the constructions of Theorems 4.1 and 4.2. It is based on the geometric properties of twisted cubics.
A normal rational curve of order 3 in PG(3, q) is called twisted cubic. It is known that a twisted cubic is projectively equivalent to the set of points {(t3 : t2 : t : 1) : t G GF(q)} U {(1 : 0 : 0 : 0)}. In [20] it was shown that there exist aregular spreads given by a twisted cubic. For a detailed description of twisted cubics and the proofs of the following theorems we refer to [20], Section 21.
Theorem 4.5. Let Gq be the group of projectivities in PG(3, q) fixing a twisted cubic C. Then
•	Gq = PGL(2, q) and it acts triply transitively on the points of C.
•	If q > 5 then the number of twisted cubics in PG(3, q) is q5(q4 — 1)(q3 — 1).
Theorem 4.6. Let C be a twisted cubic in PG(3, q). If gcd(q +1,3) =3, then there exists a spread in PG(1)(3, q) induced by C.
Using the spreads associated to twisted cubics and the Basic Construction Lemma, we get the following multigraph factorization.
Theorem 4.7. Let q > 5 be a prime power, A = q5(q4 — 1)(q—1) and v = q3 + q2 + q +1. If gcd(q + 1, 3) = 3, then there exists a simple q-factorization of AKv induced by the set of twisted cubics in PG(3, q).
Proof. Let c be the set of twisted cubics in PG(3, q). For C g c let Lc be the spread in PG(1)(3, q) induced by C. If t is a line and q denotes the number of twisted cubics C with the property that t belongs to LC, then it follows from Theorem 4.5 that q does not depend on t. Hence
|{twisted cubics in PG(3, q)}| x |{lines in a spread of PG(3, q)}| Q =	|{lines in PG(3,q)}|
_q5(q4 — 1)(q3 — 1) x (q2 + 1) _ 5, 4
(q2 + 1)(q2 + q + 1)
q5 (q4 — 1)(q — 1).
Thus c induces a |c|-fold spread in PG(1)(3, q). Each spread LC induces a q-factor in Kv, therefore the Basic Construction Lemma gives that |J LC is a q-factorization of AKv.
cec
Any two distinct twisted cubics define different spreads, hence the factorization is simple by definition.	□
172
Ars Math. Contemp. 8 (2015) 215-223
4.2 Constructions from subgeometries
If the order of the base field is not prime, then projective spaces can be partitioned by subgeometries. Let 1 < k be an integer. Since GF(q) is a subfield of GF(qk), so PG(n, q) is naturally embedded into PG(n, qk) if the coordinate system is fixed. Any PG(n, q) embedded into PG(n, qk) is called a subgeometry. Using cyclic projectivities one can prove that any PG(n, qk) can be partitioned by subgeometries PG(n, q). For a detailed description of cyclic projectivities, subgeometries, and the proofs of the following three theorems we refer to [22], Section 4.
Theorem 4.8 ([22], Lemma 4.20). Let s(n, q, qk) denote the number of subgeometries PG(n, q) in PG(n, qk). Then
n+1
s(n,q,qk) = q(n+1)(k-1) fl
qi-1 .
Theorem 4.9 ([22], Theorem 4.29). PG(n, qk) can be partitioned into 0(n, q, qk) = (qqk;_1)(-ri1++1lq-11)) disjoint subgeometries PG(n, q) if and only if gcd(k, n + 1) = 1.
Theorem 4.10 ([22], Theorem 4.35). Suppose that gcd(k, n +1) = 1. Let p0(n, q, qk) denote the number of projectivities which act cyclically on a PG(n, q) of PG(n, qk) such that determine different partitions. Then
n
n (qki -1)
po(n,q,qk) = q^^ i=1 +, .
n+ 1
Any given subgeometry PG(n, q) is contained in
n
n (q4 - 1)
, , (n+1) j=1 po(n,q) = q( 2 )-—:—
n+1
of these partitions.
We can consider the partitions of the point-set of PG(n, qk) by subgeometries
PG(n, q).
Each partition of PG(n, qk) into subgeometries PG(n, q) defines a (q(q_-1)) -factor
k (n+1)_1
of , with v — —j—. Each projectivity which acts cyclically on a PG(n, q) defines a ("t-^) -factorizations of the corresponding complete multigraph.
Theorem 4.11. Let q be a prime power, 1 < k and n be positive integers for which
( n+l ) k	n_1
gcd(k, n + 1) = 1 holds. Let A = q( q2k-)i((wq+-)1(^n1-1) n (qki - 1) and v = ¿(n--1.
i=1
Then there exist a simple (q qq ) -factorization of AKv induced by the set of those projec-
q-1.
tivities which act cyclically on a PG(n, q) of PG(n, qk) such that they determine different partitions.
G. Kiss and C. Rubio-Montiel: A note on m-factorizations of complete multigraphs
173
Proof. It follows from Theorem 4.8 that the number Se of subgeometries PG(n, q) through two points of PG(n, qk) is
s(n,q,qk) x |{pointsin PG(n, q)}| x (|{pointsin PG(n, q)}| — 1) e = |{points in PG(n, qk)}| x (|{pointsin PG(n,qk)}| — 1)
= q(n+1)(k-1)(qk — 1)	qki — 1
= qk-1(q — 1) \\qi — 1 '
Each cyclic projectivity determines different partitions, hence it determines different factors. Thus A = Se x p0(n, q).	□
We cannot decide the decomposability of the factorization construted in the previous theorem in general, but we can prove the existence of indecomposable factorizations in some cases. To do this we need the following result from number theory.
Lemma 4.12 ([22], Lemma 4.24). If r, s and x are positive integers with x > 1, then L))XX—1) is an integer if and only if gcd(r, s) = 1.
We apply it in a particular case.
Proposition 4.13. Let q be a prime power, 1 < k and n be positive integers for which
/ kn -i n -i \	k(n + 1) -i
gcd(k, n + 1) = 1 and gcd(k,n) = 1 hold. Let d = gcd i , ^———t) , v = q qk — 1—1 and m = q qq-"11. Suppose that F is an m-factorization of AKv for some A such that each
factor is the disjoint union of 6(n, q, qk) complete graphs on (qn+1 — 1)/(q — 1) vertices.
qn 1 k 1 qkn 1
If f denotes the number of m-factors in F then d(q—^ divides A and q1 d(qk —^ divides f. q
Proof. The standard double counting gives
A x (2) = (m2+1) x 6(n, q, qk) x f,
qkn 1 qn 1 qn 1
thus A x qk—1 dqqk-1) = f x dq(q-1). Because of Lemma 4.12,	divides A, hence
qk—1 d^ dMdes/.	□
As a direct corollary of the previous proposition we get the following result about the indecomposibility of the factorizations constructed in Theorem 4.11.
Theorem 4.14. Let q be a prime power, 1 < k and n be positive integers for which
/ kn_-i n_-i \	k(n + 1)_-i
gcd(k, n + 1) = 1 and gcd(k,n) = 1 hold. Let d = gcd i ,	- q-1
qk —1 , q— 1 J ,	qk — 1
_ 7m /)in tli s> vr> <9Vi ct n pt't-m n in /tin si jin si /> r> swift v~\/~\ c
q—1
qn 1
and m = q qq— 1 . Then there exist a simple and indecomposable m-factorization of AKv
( n + 1) k	n_1
where A = tdg—) for some t in {1,..., dEI (qki — 1)}'
i=1
Acknowledgement
The authors are grateful to the anonymous reviewers for their detailed and helpful comments and suggestions.
174
Ars Math. Contemp. 8 (2015) 215-223
References
[1]	P. Adams, D. Bryant and B. Maenhaut, Cube factorizations of complete graphs, J. Combin. Des. 12 (2004), 381-388.
[2]	B. Alspach, The Oberwolfach problem, in: C. J. Colbourn and J. H. Dinitz (eds), CRC Handbook of Combinatorial Designs, CRC Press, Boca Raton, FL, 1996, 394-395.
[3]	D. Archdeacon and J. H. Dinitz, Constructing indecomposable 1-factorizations of the complete multigraph, Discrete Math. 92 (1991), 9-19.
[4]	A. H. Baartmans and W. D. Wallis, Indecomposable factorizations of multigraphs, Discrete Math. 78 (1989), 37-43.
[5]	R. D. Baker, Partitioning the planes of AG2m(2) into 2-designs, Discrete Math. 15 (1976), 205-211.
[6]	A. Beutelspacher, On parallelisms in finite projective spaces, Geom. Dedicata 3 (1974), 35-40.
[7]	N. L. Biggs, T. P. Kirkman, mathematician, Bull. London Math. Soc. 13 (1981), 97-120.
[8]	S. Bonvicini, G. Mazzuoccolo and G. Rinaldi, On 2-factorizations of the complete graph: from the k-pyramidal to the universal property, J. Combin. Des. 17 (2009), 211-228.
[9]	R. C. Bose, A note on the resolvability of balanced incomplete block designs, Sankhya 6 (1942), 105-110.
[10]	R. H. Bruck, Construction problems in finite projective spaces, in: A. Barlotti (ed.), Finite geometric structures and their applications, Edizioni Cremonese, Rome, 1973, 105-188.
[11]	A. A. Bruen and J. W. P. Hirschfeld, Applications of line geometry over finite fields, I: The twisted cubic, Geom. Dedicata 6 (1977), 495-509.
[12]	D. Bryant, D. Horsley, B. Maenhaut and B. R. Smith, Cycle decompositions of complete multi-graphs, J. Combin. Des. 19 (2011), 42-69.
[13]	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.
[14]	P. Cameron and J. H. van Lint, Designs, Graphs, Codes and their Links, London Mathematical Society Student Texts 22, Cambridge University Press, Cambridge, 1991.
[15]	W. Chu, New constructions of simple and indecomposable 1-factorizations of complete multi-graphs, J. Statist. Plann. Inference 94 (2001), 181-196.
[16]	C. J. Colbourn, M. J. Colbourn and A. Rosa, Indecomposable 1-factorizations of the complete multigraph, J. Austral. Math. Soc. Ser. A 39 (1985), 334-343.
[17]	G. L. Ebert, Partitioning projective geometries into caps, Canad. J. Math. 37 (1985), 11631175.
[18]	M. N. Ferencak and A. J. W. Hilton, Regular multigraphs and their semiregular factorizations, Congr. Numer. 209 (2011), 149-159.
[19]	A. Hartman and A. Rosa, Cyclic one-factorization of the complete graph, European. J. Combin. 6 (1985), 45-48.
[20]	J. W. P. Hirschfeld, Finite projective spaces of three dimensions, Clarendon Press, Oxford, 1985.
[21]	J. W. P. Hirschfeld J. A. Thas, General Galois geometries, Clarendon Press, Oxford, 1991.
[22]	J. W. P. Hirschfeld, Projective geometries over finite fields, second ed., Clarendon Press, Oxford, 1998.
[23]	B. C. Kestenband, Projective geometries that are disjoint unions of caps, Canad. J. Math. 32 (1980), 1299-1305.
G. Kiss and C. Rubio-Montiel: A note on m-factorizations of complete multigraphs
175
[24]	G. B. Khosrovshahi, Ch. Maysoori and B. Tayfeh-Rezaie, A note on 3-factorizations of K10, J. Combin. Des. 9 (2001), 379-383.
[25]	Gy. Kiss, One-factorizations of complete multigraphs and quadrics in PG(n,q), J. Combin. Des. 10 (2002), 139-143.
[26]	G. Korchmáros, A. Siciliano and A. Sonnino, 1-factorizations of complete multigraphs arising from finite geometry, J. Combin. Theory Ser. A 93 (2001), 385-390.
[27]	B. R. Smith, Cycle decompositions of complete multigraphs, J. Combin. Des. 18 (2010), 85-93.
[28]	A. Sonnino, One-factorizations of complete multigraphs arising from maximal (k; n)-arcs in PG(2, 2h), Discrete Math. 231 (2001), 447-451.
[29]	W. D. Wallis, One-factorizations, Mathematics and its Applications, 390, Kluwer Academic Publishers Group, Dordrecht, 1997.