ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 21 (2021) #P1.02 / 23–32
https://doi.org/10.26493/1855-3974.2288.a20
(Also available at http://amc-journal.eu)
Complex uniformly resolvable
decompositions of Kv
Csilla Bujtás *
Faculty of Mathematics and Physics, University of Ljubljana,
Jadranska 19, Ljubljana 1000, Slovenia
Mario Gionfriddo, Elena Guardo, Lorenzo Milazzo, Salvatore Milici †
Dipartimento di Matematica e Informatica, Università di Catania,
Viale A. Doria, 6, 95125 - Catania, Italia
Zsolt Tuza ‡
Alfréd Rényi Institute of Mathematics,
1053 Budapest, Reáltanoda u. 13–15, Hungary, and
Department of Computer Science and Systems Technology, University of Pannonia,
8200 Veszprém, Egyetem u. 10, Hungary
Dedicated to the good friend and colleague Lorenzo Milazzo
who passed away in March 2019.
Received 22 March 2020, accepted 2 February 2021, published online 10 August 2021
Abstract
In this paper we consider complex uniformly resolvable decompositions of the com-
plete graph Kv into subgraphs such that each resolution class contains only blocks isomor-
phic to the same graph from a given set H and at least one parallel class is present from
each graph of H. We completely determine the spectrum for the cases H = {K2, P3,K3},
H = {P4, C4}, and H = {K2, P4, C4}.
Keywords: Resolvable decomposition, complex uniformly resolvable decomposition, path, cycle.
Math. Subj. Class. (2020): 05C51, 05C38, 05C70
*Supported by the Slovenian Research Agency under the project N1-0108.
†Supported by MIUR and I.N.D.A.M. (G.N.S.A.G.A.), Italy and by Università degli Studi di Catania, “Piano
della Ricerca 2016/2018 Linea di intervento 2” and “PIACERI 2020/22”.
‡Corresponding author. Research supported by the National Research, Development and Innovation Office –
NKFIH under the grant SNN 129364.
E-mail addresses: bujtas@fmf.uni-lj.si (Csilla Bujtás), gionfriddo@dmi.unict.it (Mario Gionfriddo),
guardo@dmi.unict.it (Elena Guardo), — (Lorenzo Milazzo), milici@dmi.unict.it (Salvatore Milici),
tuza@dcs.uni-pannon.hu (Zsolt Tuza)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
24 Ars Math. Contemp. 21 (2021) #P1.02 / 23–32
1 Introduction and definitions
Given a set H of pairwise non-isomorphic graphs, an H-decomposition (or H-design) of a
graph G is a decomposition of the edge set of G into subgraphs (called blocks) isomorphic
to some element of H. We say that an H-decomposition is complex1 if all H ∈ H are
present in it.
An H-factor of G is a spanning subgraph of G which is a vertex-disjoint union of some
copies of graphs belonging to H. If H = {H}, we will briefly speak of an H-factor. An
H-decomposition of G is resolvable if its blocks can be partitioned into H-factors (H-
factorization or resolution of G). An H-factor in an H-factorization is referred to as a
parallel class. Note that the parallel classes are mutually edge-disjoint, by definition.
An H-factorization F of G is called uniform if each factor of F is an H-factor for
some graph H ∈ H. A K2-factorization of G is known as a 1-factorization and its fac-
tors are called 1-factors; it is well known that a 1-factorization of Kv exists if and only
if v is even ([10]). If H = {F1, . . . , Fk} and ri ≥ 0 for i = 1, . . . , k, we denote by
(F1, . . . , Fk)-URD(v; r1, . . . , rk) a uniformly resolvable decomposition of the complete
graph Kv having exactly ri Fi-factors. A complex (F1, . . . , Fk)-URD(v; r1, . . . , rk) is a
uniformly resolvable decomposition of the complete graph Kv into r1 + · · · + rk parallel
classes with the requirement that at least one parallel class is present for each Fi ∈ H, i.e.,
ri > 0 for i = 1, . . . , k.
Recently, the existence problem for H-factorizations of Kv has been studied and a lot
of results have been obtained, especially on the following types of uniformly resolvable
H-decompositions: for a set H consisting of two complete graphs of orders at most five in
[3, 13, 14, 15]; for a set H of two or three paths on two, three, or four vertices in [5, 6, 9];
for H = {P3,K3 + e} in [4]; for H = {K3,K1,3} in [8]; for H = {C4, P3} in [11]; for
H = {K3, P3} in [12]; for 1-factors and n-stars in [7]; and for H = {P2, P3, P4} in [9].
In connection with our current studies the following cases are most relevant:
• perfect matchings and parallel classes of triangles or 4-cycles (that is, {K2,K3} or
{K2, C4}, Rees [13]);
• perfect matchings and parallel classes of 3-paths ({K2, P3}, Bermond et al. [1],
Gionfriddo and Milici [5]);
• parallel classes of 3-paths and triangles ({K3, P3}, Milici and Tuza [12]).
In this paper we give a complete characterization of the spectrum (the set of all admissible
combinations of the parameters) for the following two triplets of graphs and for the pair
contained in one of them which is not covered by the cases known so far:
• complex {K2, P3,K3}-decompositions of Kv (Section 3, Theorem 3.1);
• complex {K2, P4, C4}-decompositions of Kv (Section 4, Theorem 4.1);
• complex {P4, C4}-decompositions of Kv (Section 5, Theorem 5.1).
We summarize the formulation of those results in the concluding section, where a conjec-
ture related to the method of “metamorphosis” of parallel classes is also raised. We provide
the basis for this approach by applying linear algebra in Section 2.
1In the terminology of [2] one may say that in a complex decomposition all H ∈ H are essential (page 131)
or mandatory (page 232). In Chapter II.7.9 on uniformly resolvable designs the default is that all block sizes are
essential, while in Chapter IV.1 on partially balanced designs no block size is required to be mandatory.
Cs. Bujtás et al.: Complex uniformly resolvable decompositions of Kv 25
2 Local metamorphosis
In this section we prove three relations between uniform parallel classes of 4-cycles and
4-paths that will be used in the proofs of our main theorems. Before presenting the new
statements, we recall the Milici–Tuza–Wilson Lemma from [12].
It will be assumed throughout, without further mention, that all parallel classes are
meant on the same vertex set.
Theorem 2.1 ([12]). The union of two parallel classes of 3-cycles can be decomposed into
three parallel classes of P3.
The next two results, Theorems 2.2 and 2.3, will directly imply Theorem 2.4 which
states a pure metamorphosis from 4-cycles to 4-paths.
Theorem 2.2. The union of two parallel classes of C4 is decomposable into two parallel
classes of P4 and one perfect matching.
Proof. Let the vertices be v1, . . . , vn where n is a multiple of 4. The union of two parallel
classes of C4 forms a 4-regular graph G with 2n edges, say e1, . . . , e2n. We associate
a Boolean variable xi with each edge ei (1 ≤ i ≤ 2n) and construct a system of linear
equations over GF (2), which has 3n2 − 1 equations over the 2n variables. Let us set
xi1 + xi2 + xi3 + xi4 = 1 (mod 2)
for each 4-tuple of indices such that ei1 , ei2 , ei3 , ei4 are either the edges of a C4 in a parallel
class (call this a C-equation) or are the four edges incident with a vertex vi (a V -equation).
This gives 32n equations, but the V -equation for vn can be omitted since the n V -equations
sum up to 0 (as each edge is counted twice in the total sum) and therefore the one for vn
follows from the others.
We claim that this system of equations is contradiction-free over GF (2). To show this,
we need to prove that if the left sides of a subcollection E of the equations sum up to 0,
then also the right sides have zero sum; that is, the number |E| of its equations is even.
Observe that each variable is present in precisely three equations: in one C-equation
and two V -equations. Hence, to have zero sum on the left side, any xi should either not
appear in any equations of E or be present in precisely two. This means one of the following
two situations.
(T1) If (ei1 , ei2 , ei3 , ei4) is a 4-cycle (in this cyclic order of edges) and its C-equation
belongs to E , then precisely two related V -equations must be present in E , namely
either those for the vertices ei1 ∩ ei2 and ei3 ∩ ei4 or those for ei2 ∩ ei3 and ei1 ∩ ei4 .
(T2) If (ei1 , ei2 , ei3 , ei4) is a 4-cycle such that its C-equation does not belong to E but
some xij (1 ≤ j ≤ 4) is involved in E , then all the four V -equations for vi1 , vi2 , vi3 ,
vi4 must be present in E .
In the first and second parallel class of 4-cycles, respectively, let us denote the number
of cycles of type (T1) by a1 and b1, and that of type (T2) by a2 and b2. Then the number
of V -equations in E is equal to both 2a1 + 4a2 and 2b1 + 4b2, which is the same as the
average of these two numbers. Thus, the number |E| of equations is equal to
a1 + b1 +
1
2
((2a1 + 4a2) + (2b1 + 4b2)) = 2(a1 + a2 + b1 + b2)
26 Ars Math. Contemp. 21 (2021) #P1.02 / 23–32
that is even, as needed.
Since the system of equations is non-contradictory, it has a solution ξ ∈ {0, 1}2n over
GF (2). We observe further that in any C-equation xi1 + xi2 + xi3 + xi4 = 1 we may
switch the values from ξ(xij ) to 1− ξ(xij ) simultaneously for all 1 ≤ j ≤ 4, and doing so
the modified values remain a solution because the parities of sums in the V -equations do
not change either. In this way, we can transform ξ to a basic solution ξ0 in which every C-
equation contains precisely one 1 and three 0s. Since each V -equation contains precisely
two or zero variables from each C-equation, it follows that in the basic solution ξ0 each
V -equation, too, contains precisely one 1 and three 0s.
As a consequence, the variables which have xi = 1 in the basic solution define a perfect
matching in G (since at most two 1s may occur at each vertex, and then the corresponding
V -equation implies that there is precisely one). Moreover, removing those edges from G,
each cycle of each parallel class becomes a P4. In this way we obtain two parallel classes
of P4, and one further class which is a perfect matching.
Theorem 2.3. The edge-disjoint union of a perfect matching and a parallel class of C4 is
decomposable into two parallel classes of P4.
Proof. We apply several ideas from the previous proof, but in a somewhat different way.
We now introduce Boolean variables x1, . . . , xn for the edges e1, . . . , en of the 4-cycles
only; but still there will be two kinds of linear equations, namely n/4 of them for 4-cycles
(called C-equations) and n/2 of them for the edges of the perfect matching (M -equations).
They are of the same form as before:
xi1 + xi2 + xi3 + xi4 = 1 (mod 2)
The C-equations require ei1 , ei2 , ei3 , ei4 to be the edges of a C4 in the parallel class. The
M -equations take ei1 , ei2 , ei3 , ei4 as the four edges incident with a matching edge. If a
matching edge is the diagonal of a 4-cycle, then their equations coincide; and if a matching
edge shares just one vertex with a 4-cycle then the M -equation and the C-equation share
two variables which correspond to consecutive edges on the cycle. Further, we recall that
the matching is edge-disjoint from the cycles, therefore each variable associated with a
cycle-edge occurs in precisely two distinct M -equations.
These facts imply that only two types of C-equations can occur in a subcollection E of
equations whose left sides sum up to 0 over GF (2).
(T1) If (ei1 , ei2 , ei3 , ei4) is a 4-cycle and its C-equation belongs to E , then the corre-
sponding C4 has precisely two (antipodal) vertices for which the M -equations of the
incident matching edges are present in E . (At the moment it is unimportant whether
those two vertices form a matching edge or not.)
(T2) If (ei1 , ei2 , ei3 , ei4) is a 4-cycle whose C-equation does not belong to E but some xij
(1 ≤ j ≤ 4) is involved in E , then each M -equation belonging to a matching edge
incident with some of the four vertices vi1 , vi2 , vi3 , vi4 is present in E . (It is again
unimportant whether one or both or none of the diagonals of the C4 in question is a
matching edge.)
Let now a1 and a2 denote the number of cycles with type (T1) and type (T2), re-
spectively. By what has been said, the number of vertices requiring an M -equation is
equal to 2a1 + 4a2. Since each of those equations is now counted at both ends of the
Cs. Bujtás et al.: Complex uniformly resolvable decompositions of Kv 27
corresponding matching edge, we obtain that E contains exactly a1 + 2a2 M -equations;
moreover it has a1 C-equations, by definition. Thus, the number |E| of equations is equal
to a1 + (a1 + 2a2) = 2(a1 + a2) which is even. Thus, if the left sides in E sum up to
zero, then also the right sides have sum 0 in GF (2). It proves that the system of the 3n/4
equations is contradiction-free and has a solution ξ ∈ {0, 1}n over GF (2).
Now, we observe that in any C-equation xi1 + xi2 + xi3 + xi4 = 1 we may switch the
values from ξ(xij ) to 1− ξ(xij ) simultaneously for all 1 ≤ j ≤ 4. Doing so, the modified
values remain a solution as the parities of sums in the M -equations do not change either.
In this way we can transform ξ to a basic solution ξ0 in which every C-equation contains
precisely one 1 and three 0s. Since each M -equation has precisely two or four or zero
variables from any C-equation, it follows that in the basic solution ξ0 each M -equation,
too, contains precisely one 1 and three 0s.
As a consequence, the variables (cycle-edges) which have xi = 1 in the basic solution
establish a pairing between the edges of the original matching. Hence the set I = {ei :
ξ0(xi) = 1} together with the edges of the given matching factor determines a P4-factor.
Moreover, removing the edges of I from the 4-cycles, we obtain another parallel class of
paths P4.
These two types of metamorphosis can be combined to obtain the following third one.
Theorem 2.4. The union of three parallel classes of C4 is decomposable into four parallel
classes of P4.
Proof. Applying Theorem 2.2 we transform the union of the first and the second C4-class
into two P4-classes and a perfect matching. After that we combine the third C4-class with
the perfect matching just obtained into two further P4-classes, by Theorem 2.3.
3 The spectrum for H = {K2, P3,K3}
In this section we consider complex uniformly resolvable decompositions of the complete
graph Kv into m classes containing only copies of 1-factors (perfect matchings), p classes
containing only copies of paths P3 and t classes containing only copies of triangles K3. The
current problem is to determine the set of feasible triples (m, p, t) such that m · p · t ̸= 0,
for which there exists a complex (K2, P3,K3)-URD(v;m, p, t). A little more than that, for
v = 6 and v = 12 we shall list all the possible (m, p, t) with m, p, t ≥ 0 such that there
exists a uniformly resolvable decomposition (K2, P3,K3)-URD(v;m, p, t).
Theorem 3.1. The necessary and sufficient conditions for the existence of a complex
(K2, P3,K3)-URD(v;m, p, t) are:
(i) v ≥ 12 and v is a multiple of 6;
(ii) 3m+ 4p+ 6t = 3v − 3.
Moreover, the parameters m, p, t are in the following ranges:
(iii) 1 ≤ m ≤ v − 7 and m is odd,
3 ≤ p ≤ 3 · ⌊ v4 − 1⌋,
1 ≤ t ≤ ⌊v2 − 3⌋.
28 Ars Math. Contemp. 21 (2021) #P1.02 / 23–32
Proof. We first prove that the conditions are necessary. Divisibility of v by 6 is immediately
seen, due to the presence of K3-classes and 1-factors. We observe further that the number
of edges in a parallel class is v for a triangle-class, 2v/3 for a P3-class and v/2 for a
matching. Thus, in any (K2, P3,K3)-URD(v;m, p, t) we must have
mv
2
+
2pv
3
+ tv =
(
v
2
)
.
Dividing it by v/6, the assertion of (ii) follows.
As (ii) implies, p is a multiple of 3, say p = 3x. Then we obtain
m+ 4x+ 2t = v − 1
and also conclude that m is odd. Since m ≥ 1, t ≥ 1, and x ≥ 1, this equation yields
m ≤ v − 7, x ≤ v/4− 1, t ≤ v/2− 3,
implying the conditions listed in (iii), and the first one also excludes v = 6. This completes
the proof that the conditions (i) – (iii) are necessary.
To prove the sufficiency of (i) – (ii), we consider v ≥ 18 first. Since v is a multiple of
6 according to (i), there exists a Nearly Kirkman Triple System of order v, which means
m = 1 perfect matching and t = v2 − 1 parallel classes of triangles. More generally,
for every odd m in the range 1 ≤ m ≤ v − 7, there exists a collection of m perfect
matchings and t = v−1−m2 parallel classes of triangles, which together decompose Kv;
this was proved in [13]. From such a system, for every 0 < x < v−1−m4 , we can take
2x parallel classes of triangles. Applying Theorem 2.1 [12], also proved independently
by Wilson (unpublished), we obtain 3x parallel classes of paths P3. This gives a com-
plex (K2, P3,K3)-URD(v;m, 3x, v−1−m2 − 2x). For v = 12, the statement follows by
Proposition 3.3 below.
3.1 Small cases
Obviously, the proofs of the necessary conditions that v is a multiple of 6, and that the
equality 3m+4p+6t = 3v− 3 must be satisfied by every (K2, P3,K3)-URD(v;m, p, t),
do not use the assumption m · p · t ̸= 0.
Proposition 3.2. There exists a (K2, P3,K3)-URD(6;m, p, t) if and only if (m, p, t) ∈
{(5, 0, 0), (3, 0, 1), (1, 3, 0)}.
Proof. Putting v = 6, the equation 3m+ 4p+ 6t = 15 has exactly four solutions (m, p, t)
over the nonnegative integers. The case (1, 0, 2) would correspond to an NKTS(6) which
is known not to exist [13]. The case (5, 0, 0) corresponds to a 1-factorization of the com-
plete graph K6 which is known to exist [10]. The case of (1, 3, 0) is just the same as a
(K2, P3)-URD(6; 1, 3) that is known to exist [6]. To see the existence for (3, 0, 1), consider
V (K6) = Z6 and the following classes: {{1, 4}, {2, 5}, {3, 6}}, {{1, 5}, {2, 6}, {3, 4}},
{{1, 6}, {2, 4}, {3, 5}}, {(1, 2, 3), (4, 5, 6)}.
Proposition 3.3. There exists a (K2, P3,K3)-URD(12;m, p, t) if and only if (m, p, t) ∈
{(11, 0, 0), (9, 0, 1), (7, 3, 0), (7, 0, 2), (5, 0, 3), (5, 3, 1), (3, 6, 0), (3, 3, 2), (3, 0, 2),
(1, 6, 1), (1, 3, 3)}.
Cs. Bujtás et al.: Complex uniformly resolvable decompositions of Kv 29
Proof. Checking the nonnegative integer solutions of 3m + 4p + 6t = 33, the case of
(1, 0, 5) would correspond to an NKTS(12) which is known not to exist [13]. The case of
(11, 0, 0) corresponds to a 1-factorization of the complete graph K12 that is known to exist
[2]. The result for the cases (9, 0, 1), (7, 0, 2), (5, 0, 3), (3, 0, 4) follows by [13]. Applying
Theorem 2.1 to (7, 0, 2), (5, 0, 3), (3, 0, 4), we obtain the existence for (7, 3, 0), (5, 3, 1),
(3, 3, 2), and (3, 6, 0). The existence for the case (1, 3, 3) is shown by the following con-
struction. Let V (K12) = Z12, and consider the following parallel classes:
• matching: {{1, 6}, {2, 4}, {3, 0}, {5, 11}, {7, 9}, {8, 10}};
• paths: {{5, 0, 11}, {8, 1, 7}, {9, 2, 3}, {6, 4, 10}}, {{1, 3, 8}, {7, 5, 10}, {4, 9, 0},
{2, 11, 6}}, {{0, 6, 5}, {2, 7, 4}, {9, 8, 11}, {3, 10, 1}};
• triangles: {{0, 1, 2), {3, 4, 5}, {6, 7, 8}, {9, 10, 11}}, {{0, 4, 8}, {3, 7, 11},
{2, 6, 10}, {1, 5, 9}}, {{0, 7, 10}, {3, 6, 9}, {2, 5, 8}, {1, 4, 11}}.
Finally, we apply Theorem 2.1 to the case (1, 3, 3) and infer that a (K2, P3,K3)-
URD(12; 1, 6, 1) exists, too.
4 The spectrum for F = {K2, P4, C4}
In this section we consider complex uniformly resolvable decompositions of the complete
graph Kv into m parallel 1-factors, p parallel classes of 4-paths, and c parallel classes of
4-cycles. The current problem is to determine the set of feasible triples (m, p, c) such that
m · p · c ̸= 0, for which there exists a complex (K2, P3, C4)-URD(v;m, p, c). The case
{P4, C4} will be discussed in Section 5.
Theorem 4.1. The necessary and sufficient conditions for the existence of a complex
(K2, P4, C4)-URD(v;m, p, c) are:
(i) v ≥ 8 and v is a multiple of 4;
(ii) 2m+ 3p+ 4c = 2v − 2.
Moreover, the parameters m, p, c are in the following ranges:
(iii) 1 ≤ c ≤ v2 − 3,
1 ≤ m ≤ v − 6,
2 ≤ p ≤ 2 ⌊ v−43 ⌋;
(iv) p is even; and if p ≡ 2 (mod 4), then also m is even.
Proof. We first show that the conditions are necessary. Since Kv has a C4-factor, v must
be a multiple of 4. Further, as a C4-, K2-, and P4-factor respectively cover exactly v, v/2,
and 3v/4 edges, in a (K2, P4, C4)-URD(v;m, p, c) we have
mv
2
+
3pv
4
+ cv =
(
v
2
)
.
This equality directly implies (ii) and we may also conclude that p is even and, further, if
p ≡ 2 (mod 4), then m must be even as well. Putting p = 2x we obtain
m+ 3x+ 2c = v − 1.
30 Ars Math. Contemp. 21 (2021) #P1.02 / 23–32
By our condition, all the three types of parallel classes are present in the decomposition,
i.e. we have c ≥ 1, m ≥ 1, and x ≥ 1. These, together with the equality above, imply the
necessity of (iii).
Next we prove the sufficiency of (i) – (ii). We first take a 1-factorization of Kv/2 into
v/2 − 1 perfect matchings, which exists because v is a multiple of 4. Now, replace each
vertex of Kv/2 with two non-adjacent vertices, and each edge with a copy of the complete
bipartite graph K2,2, i.e. a 4-cycle whose missing diagonals are the non-adjacent vertex
pairs.2 This blow-up results in v/2 − 1 parallel classes of C4 inside Kv , and the missing
edges can be taken as a perfect matching. Let C be the set of the parallel classes of C4 and
x be a nonnegative integer such that 0 < x ≤ ⌊v−43 ⌋. The construction splits into two cases
depending on the parity of x.
If x is even, take 3x2 parallel classes from C. Applying Theorem 2.4, we transform the
3x
2 parallel classes of C4 into 2x = p parallel classes of paths P4. For any given y = c
in the range 0 < y ≤ ⌊v−22 −
3x
2 ⌋, keep y classes of C4 and transform the remaining
v−2
2 −
3x
2 − y classes of C4 into 2(
v−2
2 −
3x
2 − y) = m − 1 classes of 1-factors. In this
way we obtain a complex (K2, P4, C4)-URD(v; v − 3x− 2y − 1, 2x, y).
If x is odd, take 3(x−1)2 + 2 parallel classes from C. By Theorems 2.2 and 2.4, we
can transform the 3(x−1)2 + 2 parallel classes of C4 into 2x = p parallel classes of paths
P4 and a 1-factor. For any given y = c in the range 0 < y ≤ v−22 −
3(x−1)
2 − 2, keep
y classes of C4 and transform the remaining v−22 −
3(x−1)
2 − 2 − y classes of C4 into
2( v−22 −
3(x−1)
2 − 2− y) = m− 2 classes of 1-factors. In this way, we obtain a complex
(K2, P4, C4)-URD(v; v − 3x− 2y − 1, 2x, y).
The result, for every v ≡ 0 (mod 4), 0 < x ≤ ⌊ v−43 ⌋, and 0 < y ≤ ⌊
v−2
2 −
3x
2 ⌋,
is a uniformly resolvable decomposition of Kv into into v − 1 − 3x − 2y = m classes
containing only copies of 1-factors, 2x = p classes containing only copies of paths P4,
and y = c classes containing only copies of 4-cycles C4. This finishes the proof of the
theorem.
5 The spectrum for H = {P4, C4}
Finally, we consider complex uniformly resolvable decompositions of the complete graph
Kv into p classes containing only copies of paths P4 and c classes containing only copies
of 4-cycles C4.
Theorem 5.1. The necessary and sufficient conditions for the existence of a complex
(P4, C4)-URD(v; p, c) are:
(i) v ≥ 8 and v is a multiple of 4;
(ii) 3p+ 4c = 2v − 2.
Proof. Necessity is a consequence of Theorem 4.1, since we did not need to assume m > 0
in that part of its proof. Turning to sufficiency, the condition 3p+4c = 2v− 2 implies that
3p ≡ 2v − 2 (mod 4). This gives p = 2 + 4x and c = v−42 − 3x. For a construction, we
start with a decomposition of Kv into a perfect matching F and v−22 parallel classes of C4
as in the proof of Theorem 4.1. By Theorem 2.3, we can transform one class of C4 and F
2With another terminology, this “blow-up” is the lexicographic product Kv/2[2K1].
Cs. Bujtás et al.: Complex uniformly resolvable decompositions of Kv 31
into two classes of paths P4. Then, by Theorem 2.4, we transform 3x parallel classes of
C4 into 4x parallel classes of P4. The result, for every x such that 0 ≤ x ≤ ⌊ v−66 ⌋, is a
uniformly resolvable decomposition of Kv into 2 + 4x classes containing only copies of
paths P4 and v−42 − 3x classes containing only copies of 4-cycles C4. This completes the
proof.
6 Conclusion
Combining Theorems 3.1, 4.1, and 5.1, we obtain the main result of this paper.
Theorem 6.1.
(i) A complex (K2, P3,K3)-URD(v;m, p, t) exists if and only if v ≥ 12, v is a multiple
of 6, and 3m+ 4p+ 6t = 3v − 3.
(ii) A complex (K2, P4, C4)-URD(v;m, p, t) exists if and only if v ≥ 8, v is a multiple
of 4, and 2m+ 3p+ 4t = 2v − 2.
(iii) A complex (P4, C4)-URD(v; p, t) exists if and only if v ≥ 8, v is a multiple of 4, and
3p+ 4t = 2v − 2.
Concerning the local metamorphosis studied in Section 2, we pose the following con-
jecture as a common generalization of Theorems 2.1 and 2.4.
Conjecture 6.2. The union of k−1 parallel classes of Ck is decomposable into k parallel
classes of Pk.
ORCID iDs
Csilla Bujtás https://orcid.org/0000-0002-0511-5291
Zsolt Tuza https://orcid.org/0000-0003-3235-9221
References
[1] J.-C. Bermond, K. Heinrich and M.-L. Yu, Existence of resolvable path designs, European J.
Combin. 11 (1990), 205–211, doi:10.1016/s0195-6698(13)80120-5.
[2] C. J. Colbourn and J. H. Dinitz (eds.), Handbook of Combinatorial Designs, Discrete Mathe-
matics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2nd edition,
2007.
[3] J. H. Dinitz, A. C. H. Ling and P. Danziger, Maximum uniformly resolvable designs with block
sizes 2 and 4, Discrete Math. 309 (2009), 4716–4721, doi:10.1016/j.disc.2008.05.040.
[4] M. Gionfriddo and S. Milici, On the existence of uniformly resolvable decompositions of Kv
and Kv − I into paths and kites, Discrete Math. 313 (2013), 2830–2834, doi:10.1016/j.disc.
2013.08.023.
[5] M. Gionfriddo and S. Milici, Uniformly resolvable H-designs with H = {P3, P4}, Aus-
tralas. J. Combin. 60 (2014), 325–332, https://ajc.maths.uq.edu.au/?page=
get_volumes&volume=60.
[6] M. Gionfriddo and S. Milici, On uniformly resolvable {K2, Pk}-designs with k = 3, 4, Con-
trib. Discrete Math. 10 (2015), 126–133, doi:10.11575/cdm.v10i1.62266.
32 Ars Math. Contemp. 21 (2021) #P1.02 / 23–32
[7] M. S. Keranen, D. L. Kreher, S. Milici and A. Tripodi, Uniformly resolvable decompositions
of Kv in 1-factors and 4-stars, Australas. J. Combin. 76 (2020), 55–72, https://ajc.
maths.uq.edu.au/?page=get_volumes&volume=76.
[8] S. Küçükçifçi, S. Milici and Z. Tuza, Maximum uniformly resolvable decompositions of Kv
and Kv − I into 3-stars and 3-cycles, Discrete Math. 338 (2015), 1667–1673, doi:10.1016/j.
disc.2014.05.016.
[9] G. Lo Faro, S. Milici and A. Tripodi, Uniformly resolvable decompositions of Kv into paths on
two, three and four vertices, Discrete Math. 338 (2015), 2212–2219, doi:10.1016/j.disc.2015.
05.030.
[10] E. Lucas, Récréations Mathématiques, Volume 2, Gauthier-Villars, Paris, 1883.
[11] S. Milici, A note on uniformly resolvable decompositions of Kv and Kv − I into 2-stars and
4-cycles, Australas. J. Combin. 56 (2013), 195–200, https://ajc.maths.uq.edu.au/
?page=get_volumes&volume=56.
[12] S. Milici and Z. Tuza, Uniformly resolvable decompositions of Kv into P3 and K3 graphs,
Discrete Math. 331 (2014), 137–141, doi:10.1016/j.disc.2014.05.010.
[13] R. Rees, Uniformly resolvable pairwise balanced designs with blocksizes two and three, J.
Combin. Theory Ser. A 45 (1987), 207–225, doi:10.1016/0097-3165(87)90015-x.
[14] E. Schuster and G. Ge, On uniformly resolvable designs with block sizes 3 and 4, Des. Codes
Cryptogr. 57 (2010), 45–69, doi:10.1007/s10623-009-9348-1.
[15] H. Wei and G. Ge, Uniformly resolvable designs with block sizes 3 and 4, Discrete Math. 339
(2016), 1069–1085, doi:10.1016/j.disc.2015.10.042.