# On uniqueness of packing of three copies of 2-factors

Igor Grzelec, Tomáš Madaras, Alfréd Onderko22footnotemark: 2 Department of
Discrete Mathematics, AGH University of Krakow, Poland. The corresponding
author. Email<EMAIL_ADDRESS>of mathematics, P.J. Šafárik
University, Košice, Slovakia

###### Abstract

The packing of three copies of a graph $G$ is the union of three edge-disjoint
copies (with the same vertex set) of $G$. In this paper, we completely solve
the problem of the uniqueness of packing of three copies of 2-regular graphs.
In particular, we show that $C_{3},C_{4},C_{5},C_{6}$ and $2C_{3}$ have no
packing of three copies, $C_{7},C_{8},C_{3}\cup C_{4},C_{4}\cup
C_{4},C_{3}\cup C_{5}$ and $3C_{3}$ have unique packing, and any other
collection of cycles has at least two distinct packings.

##  1 Introduction

All graphs considered in this paper are finite, undirected and have neither
loops nor multiple edges. For a graph $G$, we will denote its order $|V(G)|$
and size $|E(G)|$ as $n$ and $m$, respectively.

At the beginning, we present additional definitions which will be useful to
formulate the results. For two graphs $G_{1}$ and $G_{2}$ with disjoint vertex
sets, the union $G=G_{1}\cup G_{2}$ has $V(G)=V(G_{1})\cup V(G_{2})$ and
$E(G)=E(G_{1})\cup E(G_{2})$. The union of $n\geq 2$ disjoint copies of a
graph $H$ is denoted by $G=nH$. Further, for graphs $G_{1}$ and $G_{2}$ such
that $V(G_{1})=V(G_{2})$ and $E(G_{1})\cap E(G_{2})=\emptyset$, the edge sum
$G_{1}\oplus G_{2}$ has $V(G)=V(G_{1})=V(G_{2})$ and $E(G)=E(G_{1})\cup
E(G_{2})$.

A permutation $\sigma$ on $V(G)$ with the property that whenever $xy\in E(G)$,
then $\sigma(x)\sigma(y)\not\in E(G)$, is called an embedding of $G$ in its
complement $\overline{G}$. In other words, an embedding is an edge-disjoint
packing of two copies of $G$ into a complete graph $K_{n}$.

One of the first results on packing problem is the following theorem, which
was proved independently in [3], [4] and [14]:

######  Theorem 1.

Let $G=(V,E)$ be a graph of order $n$ and size $m$. If $m\leq n-2$ then $G$
can be embedded in its complement $\overline{G}$.

We can easily see that the star $K_{1,n-1}$ is not embeddable. Therefore,
Theorem 1 cannot be improved by raising the size of $G$. Burns and Schuster in
[5] described the full characterization of graphs of order $n$ and size $n-1$
that are embeddable:

######  Theorem 2.

Let $G=(V,E)$ be a graph of order $n$ and size $m$. If $m\leq n-1$ then either
$G$ is embeddable or $G$ is isomorphic to one of the following graphs:
$K_{1,n-1}$, $K_{1,n-4}\cup K_{3}$ with $n\geq 8$, $K_{1}\cup K_{3}$,
$K_{2}\cup K_{3}$, $K_{1}\cup 2K_{3}$, $K_{1}\cup C_{4}$.

Considering the problem of the uniqueness of graph packings, let us explain
first what we mean by distinct embeddings: let $\sigma$ be an embedding of the
graph $G=(V,E)$. Denote by $\sigma(G)$ the graph with the vertex set $V$ and
the edge set $\sigma^{*}(E)$ where the mapping $\sigma^{*}$ is induced by
$\sigma$. From the definition of an embedding we can see that the sets $E$ and
$\sigma^{*}(E)$ are disjoint; thus, we may create the graph
$G\oplus\sigma(G)$. We say that two embeddings $\sigma_{1}$, $\sigma_{2}$ of a
graph $G$ are distinct if the graphs $G\oplus\sigma_{1}(G)$ and
$G\oplus\sigma_{2}(G)$ are not isomorphic. We call a graph $G$ uniquely
embeddable if, for all embeddings $\sigma$ of $G$, all graphs
$G\oplus\sigma(G)$ are isomorphic.

This problem has been the subject of three papers. The next theorem from [16]
characterizes all graphs of order $n$ and size $n-2$ that are uniquely
embeddable:

######  Theorem 3.

Let $G$ be a graph of order $n$ and size $m=n-2$. Then either $G$ is not
uniquely embeddable or $G$ is isomorphic to one of the six following graphs:
$K_{2}\cup K_{1}$, $2K_{2}$, $K_{3}\cup 2K_{1}$, $K_{3}\cup K_{2}\cup K_{1}$,
$K_{3}\cup 2K_{2}$, $2K_{3}\cup 2K_{1}$.

The following characterization of uniquely embeddable forests was proved in
[13].

######  Theorem 4.

Let $F$ be a forest of order $n$ having at least one edge. Then either $F$ is
not uniquely embeddable or $F$ is isomorphic to one of the following graphs:
$K_{2}\cup K_{1}$, $2K_{2}$, $3K_{2}$, the double star $S(p,q)$ or the
$(n-1)$-vertex star with one edge subdivided.

Recently the problem of the uniqueness of embeddings was completely solved for
2-factors, i.e. a vertex-disjoint union of cycles. More precisely, the
following theorem was proved in [9]:

######  Theorem 5.

Let $G$ be a vertex-disjoint union of $k$ cycles. If $G$ is $C_{3}$, $C_{4}$
or $2C_{3}$ then $G$ is not embeddable. The graphs $C_{5}$, $C_{6}$,
$C_{3}\cup C_{4}$, $C_{3}\cup C_{5}$, $3C_{3}$ and $4C_{3}$ are uniquely
embeddable. In every other case, there exist at least two distinct embeddings
of $G$.

For other results on different packing problems, we refer the reader to the
survey papers [20], [17] and [18].

To generalize the above mentioned problem of the uniqueness of packing for
three copies of a graph, we first clarify what we mean by packing of three
copies of a graph, and when two such packings are distinct. Let $G_{1}$,
$G_{2}$ and $G_{3}$ be three copies of a graph $G$ of order $n$. We say that
there exists a packing of three copies of $G$ into a complete graph $K_{n}$ if
there exist injections $\alpha_{i}:V(G_{i})\rightarrow V(K_{n})$,
$i\in\\{1,2,3\\}$, such that, for $i\neq j$,
$\alpha_{i}^{*}(E(G_{i}))\cap\alpha_{j}^{*}(E(G_{j}))=\emptyset$, where the
mapping $\alpha_{i}^{*}:E(G_{i})\rightarrow E(K_{n})$ is induced by
$\alpha_{i}$. Two packings of three copies of $G$ are distinct if the graphs
$\alpha_{1}(G)\oplus\alpha_{2}(G)\oplus\alpha_{3}(G)$ and
$\alpha_{1}^{\prime}(G)\oplus\alpha_{2}^{\prime}(G)\oplus\alpha_{3}^{\prime}(G)$
are not isomorphic. We say that a packing of three copies of $G$ is unique if
all packings of three copies of $G$ are isomorphic.

Note that the problem of the uniqueness of packing of three copies of a graph
can be easily generalized for $l\geq 4$ copies (the definitions are
analogous).

It is worth to mention two results on the existence of packing of three copies
of a graph. In [19], the following theorem (which yields full characterization
of all graphs of order $n$ and size $n-2$ that have a packing of three copies)
was proved:

######  Theorem 6.

Let $G$ be a graph of order $n$ and size $m$. If $m\leq n-2$, then either
there exists a packing of three copies of $G$ or $G\in\\{K_{3}\cup
2K_{1},K_{4}\cup 4K_{1}\\}$.

In [15], the full characterization of all trees that have a packing of three
copies was proved:

######  Theorem 7.

Let $T$ be a tree of order $n\geq 6$ which is neither a star nor a star with
one edge subdivided, nor else a 6-vertex star with one edge subdivided twice.
Then there exists a packing of three copies of $T$.

The purpose of this paper is to consider the problem of the uniqueness of
packing of three copies of a graph for 2-factors. This problem for 2-factors
is related to the well-known Oberwolfach problem which is still open. To
present this problem in a formal way, we provide additional definitions. By a
$2$-factorization of a graph $G$ we mean an edge-disjoint partition of the
edge set of $G$ into 2-factors. A 1-factor of a graph $G$ (i.e. a perfect
matching of $G$) will be denoted by $I$. The Oberwolfach problem (OP for
short) asks whether a complete graph $K_{n}$ (for $n$ odd), or $K_{n}$ without
a 1-factor (for $n$ even), admits a 2-factorization in which each 2-factor is
isomorphic to a given 2-factor. More precisely, an instance
OP$(n;n_{1},\ldots,n_{k})$ of the Oberwolfach problem asks if there is a
2-factorization of $K_{n}$ for $n$ odd, or $K_{n}\setminus I$ for $n$ even,
such that each 2-factor is isomorphic to $C_{n_{1}}\cup
C_{n_{2}}\cup\ldots\cup C_{n_{k}}$. Since the problem was posed in 1967 by
Gerhard Ringel, many papers on the topic were published. With an exception of
four cases, namely OP$(6;3^{2})$, OP$(9;4,5)$, OP$(11;3^{2},5)$ and
OP$(12;3^{4})$, for which solutions do not exist, solutions were obtained for
all orders $n\leq 40$ (see [1] and [8]) and for many special cases (for
example OP$(n;r^{k},n-rk)$ for all $n\geq 6kr-1$, see [11]). For more results
on this topic, we refer the reader to the survey [6].

Now, we introduce the relation between the problem of the uniqueness of
packing of three copies of a 2-factor and the Oberwolfach problem. Because the
sum of three edge disjoint copies (with common vertex set) of any 2-factor is
a 6-regular graph, 2-factors for which there exists a packing of three copies
shall have order at least seven .

######  Observation 8.

For any $2$-factor $G=C_{n_{1}}\cup C_{n_{2}}\cup\ldots\cup C_{n_{k}}$ of
order $n=n_{1}+\ldots+n_{k}$, where $n\geq 7$, if there exists a solution for
the instance OP$(n;n_{1},\ldots,n_{k})$ of the Oberwolfach problem then there
exists a packing of three copies of $G$.

Remark that the converse of Observation 8 does not hold; it suffices to find a
packing of three copies of $C_{4}\cup C_{5}$, because OP$(9;4,5)$ has no
solution. The packing of three copies of this 2-factor is presented in Section
5. Moreover, considering complements of packings of three copies of 2-factor
of order seven and eight, we can easily see that they are isomorphic to a
graph of size zero and order seven, and to a perfect matching of order eight,
respectively. Therefore the following observation holds:

######  Observation 9.

For any $2$-factor $G=C_{n_{1}}\cup C_{n_{2}}\cup\ldots\cup C_{n_{k}}$ of
order $n=n_{1}+\ldots+n_{k}$, where $n\in\\{7,8\\}$, if there exists a
solution for the instance OP$(n;n_{1},\ldots,n_{k})$ of the Oberwolfach
problem, then there exist a unique packing of three copies of $G$.

Note that the above observations can be generalized to the problem of the
uniqueness of packing of $l\geq 4$ copies of a graph using similar reasoning.
For any 2-factor $G=C_{n_{1}}\cup C_{n_{2}}\cup\ldots\cup C_{n_{k}}$ of order
$n=n_{1}+\ldots+n_{k}$ with $n\geq 2l+1$ such that OP$(n;n_{1},\ldots,n_{k})$
has a solution, it is easy to see that there exists a packing of $l$ copies of
$G$. Furthermore, for any 2-factor $G=C_{n_{1}}\cup C_{n_{2}}\cup\ldots\cup
C_{n_{k}}$ of order $n=n_{1}+\ldots+n_{k}$, where $n\in\\{2l+1,2l+2\\}$, if
there exists a solution for OP$(n;n_{1},\ldots,n_{k})$, then there exists a
unique packing of $l$ copies of $G$.

Now, we introduce our main result:

######  Theorem 10.

Let $G=C_{n_{1}}\cup C_{n_{2}}\cup\ldots\cup C_{n_{k}}$ be a vertex-disjoint
union of $k$ cycles. For cycles $C_{3}$, $C_{4}$, $C_{5}$, $C_{6}$ and the
graph $2C_{3}$, there is no packing of three copies. The graphs $C_{7}$,
$C_{8}$, $C_{3}\cup C_{4}$, $C_{4}\cup C_{4}$, $C_{3}\cup C_{5}$ and $3C_{3}$
have unique packing of three copies. For any other graph $G$, there exist at
least two distinct packings of its three copies.

The proof of Theorem 10 is presented in the next sections. Section 2 contains
the case of cycles, Section 3 presents the proof of the existence of packing
of three copies of 2-factors (for $k\geq 2$) and general strategy of the
remaining part of the proof, Section 4 contains the proof of the existence of
at least two distinct packings of three copies of 2-factors for five
particular families of 2-factors, and the last section presents the proof for
the remaining small cases.

Remark. To better differentiate between copies of $G$ in a packing (both in
subsequent figures and proofs), we say that the first (initial) copy of $G$ is
black, the second copy of $G$ is red and the third copy of $G$ is blue in such
packing of $G$; this is useful, in particular, when a packing is presented
solely by a figure.

For the proof of our main result, we will need the following lemma which
generalizes Lemma 6 from [9].

######  Lemma 11.

If a graph $G=C_{n_{1}}\cup C_{n_{2}}\cup\ldots\cup C_{n_{k}}$ has a packing
$\alpha$ of three copies such that the graph
$\alpha_{1}(G)\oplus\alpha_{2}(G)\oplus\alpha_{3}(G)$ is not connected $($a
disconnected packing$)$, then $G$ has another packing $\alpha^{\prime}$ such
that the graph
$\alpha_{1}^{\prime}(G)\oplus\alpha_{2}^{\prime}(G)\oplus\alpha_{3}^{\prime}(G)$
is connected $($a connected packing$)$. In particular, the graph $G$ has two
distinct packings of three copies.

###### Proof.

Let $\alpha$ be the packing with the smallest number of connected components.
If $H=\alpha_{1}(G)\oplus\alpha_{2}(G)\oplus\alpha_{3}(G)$ is connected, we
are done. Otherwise, let $H_{1},H_{2}$ be two components of $H$.

Take a vertex $x_{1}$ of $H_{1}$ such that removing the two blue edges
$x_{1}^{-}x_{1}$ and $x_{1}^{+}x_{1}$ (where $x_{1}^{-}$ and $x_{1}^{+}$ are
neighbors of $x_{1}$ on the blue cycle in $H_{1}$) leaves $H_{1}$ connected.
In a similar manner, take $x_{2}$, a vertex belonging to the component
$H_{2}$. Note that such selections of $x_{1}$ and $x_{2}$ are always possible
– it suffices to take, in $H_{1}$ and $H_{2}$, any vertex that is not a cut
vertex (for example, the last vertex on the longest component path).

If now instead of the edges $x_{1}^{-}x_{1}$ and $x_{1}^{+}x_{1}$ we add two
blue edges $x_{2}^{-}x_{1}$ and $x_{2}^{+}x_{1}$, and instead of the edges
$x_{2}^{-}x_{2}$ and $x_{2}^{+}x_{2}$ we add two blue edges $x_{1}^{-}x_{2}$
and $x_{1}^{+}x_{2}$, we obtain a new packing $\alpha^{\prime}$ where two
components $H_{1}$ and $H_{2}$ become one connected component. However, this
is a contradiction with the choice of the packing $\alpha$. ∎

##  2 Cycles

In this section we prove the following lemma which will be useful in the
remaining part of the proof:

######  Lemma 12.

Let $C_{n}$ be a cycle of length $n$. For cycles $C_{3}$, $C_{4}$, $C_{5}$ and
$C_{6}$, there is no packing of three copies. The cycles $C_{7}$ and $C_{8}$
have unique packing of three copies. For longer cycles, there exist at least
two distinct packings of three copies.

###### Proof.

Obviously, the cycles $C_{3}$, $C_{4}$, $C_{5}$ and $C_{6}$ do not have
packing of three copies because such a packing is always a 6-regular graph.
From Observation 9 we know that $C_{7}$ and $C_{8}$ have unique packing of
three copies.

We will denote by $C_{n}(a,b,c)$ the 6-regular circulant graph on $n$ vertices
with generators $a$, $b$ and $c$, that is, the graph with vertex set
$\mathbb{Z}_{n}=\\{0,\ldots,n-1\\}$ and edge set
$\\{\\{x,x+s\\}:x\in\mathbb{Z}_{n},s\in\\{a,b,c\\}\\}$ (note that the addition
is modulo $n$). In [7], Dean proved that every 6-regular circulant graph on
$n$ vertices with at least one generator of order $n$ (with respect to the
group $\mathbb{Z}_{n}$) has Hamiltonian cycle decomposition. Thus, it suffices
to find, for any $n\geq 9$, two nonisomorphic 6-regular circulant graphs on
$n$ vertices with at least one generator of order $n$; this confirms that
there exist two distinct packings of three copies of a cycle with at least
nine vertices.

To distinguish between 6-regular circulant graphs on $n\geq 9$ vertices with
at least one generator of order $n$, we use their chromatic number. The
following two results from [12] and [10] give information on the chromatic
number of specific 6-regular circulant graphs:

######  Theorem 13.

Let $G=C_{n}(a,b,c)$ be a connected $6$-regular circulant graph, where $n\geq
7$, $c=a+b$ or $n-c=a+b$ are pairwise distinct positive integers different
from $n/2$. Let $\chi(G)$ be the chromatic number of $G$. Then

  * •

$\chi(G)=7$ if and only if $G\cong K_{7}\cong C_{7}(1,2,3)$,

  * •

$\chi(G)=6$ if and only if $G\cong C_{11}(1,2,3)$,

  * •

$\chi(G)=5$ if and only if $G\cong C_{n}(1,2,3)$ and $n\neq 7,11$ is not
divisible by $4$, or $G$ is isomorphic to one of the following circulant
graphs: $C_{13}(1,3,4)$, $C_{17}(1,3,4)$, $C_{18}(1,3,4)$, $C_{19}(1,7,8)$,
$C_{25}(1,3,4)$, $C_{26}(1,7,8)$, $C_{33}(1,6,7)$, $C_{37}(1,10,11)$,

  * •

$\chi(G)=3$ if and only if $n$ is divisible by $3$ and none of $a$, $b$, $c$
is divisible by $3$,

  * •

$\chi(G)=4$ in all the remaining cases.

######  Theorem 14.

Let $G$ be a connected circulant graph of order $n$. Then $G$ is bipartite if
and only if $n$ is even and all generators are odd.

From Theorem 13 we have that there exist two nonisomorphic 6-regular circulant
graphs of order $n\geq 9$ where $n\neq 11$ and $n\not\equiv 0\pmod{4}$: one
can take, for example, $C_{n}(1,2,3)$ which has chromatic number equal to five
and $C_{n}(1,4,5)$ which has chromatic number equal to three or four. The same
theorem yields that $C_{11}(1,4,5)$ has chromatic number equal to four, and
$C_{11}(1,2,3)$ has chromatic number equal to six. Hence, it remains to find
two nonisomorphic 6-regular circulant of graphs of order $n\geq 9$ where $n$
is divisible by four. Using Theorem 14, we know that $C_{4l}(1,3,5)$ is
bipartite whereas $C_{4l}(1,3,4)$ is not bipartite. Therefore, there always
exist two nonisomorphic 6-regular circulant graphs on $n\geq 9$ vertices with
one generator of order $n$. ∎

##  3 General strategy of the the proof for
2-factors where $k\geq 2$

At first, we prove the following useful lemma about the existence of packing
of three copies of 2-factors which contain at least two cycles:

######  Lemma 15.

Let $G$ be a vertex-disjoint union of $k\geq 2$ cycles. Then $G$ has a packing
of three copies except when $G=2C_{3}$.

###### Proof.

In the proof, we use the following Aigner and Brandt result from [2]:

######  Theorem 16.

Let $H$ be a graph of order $n$ with $\delta(H)\geq\frac{2n-1}{3}$. Then $H$
contains any graph $G$ of order at most $n$ with $\Delta(G)=2$ $($as a
subgraph$)$.

From Theorem 5 we know that the graph $2C_{3}$ is the only one which is not
embeddable, and therefore $2C_{3}$ also does not have a packing of three
copies; hence, we can assume that $n>6$. From the fact that packing of two
copies of a 2-factor is always a 4-regular graph, we obtain that its
complement $H$ has $\delta(H)=n-1-4=n-5$. From Theorem 16 we can see that $H$
contains a packing of additional third copy of $G$ if
$\delta(H)\geq\frac{2n-1}{3}$. Therefore, for every $n\geq 14$ we have
$n-5=\delta(H)\geq\frac{2n-1}{3}$, and so contains a packing of additional
third copy of $G$. This proves that every 2-factor $G$ of order $n\geq 14$ has
a packing of three copies.

Using Observation 8 and the Oberwolfach problem solutions for all orders
$n\leq 40$ (see [1] and [8]), we get that every 2-factor $G$ of order $7\leq
n\leq 14$ except for $C_{4}\cup C_{5}$, $2C_{3}\cup C_{5}$ and $4C_{3}$ has a
packing of three copies. The packings of three copies of $C_{4}\cup C_{5}$,
$2C_{3}\cup C_{5}$ and $4C_{3}$ also exist, and they are presented in Section
5. ∎

Now, we present the general strategy of the remaining part of the proof of our
main result. Assume that $G=C_{n_{1}}\cup C_{n_{2}}\cup\ldots\cup C_{n_{k}}$
is a vertex-disjoint union of $k\geq 2$ cycles, where $n=n_{1}+\ldots+n_{k}$.
Without loss of generality, assume that $n_{1}\leq n_{2}\leq\ldots\leq n_{k}$.
Note that for all such 2-factors, except for $2C_{3}$, a packing of three
copies exists by Lemma 15. From Observation 9 and the Oberwolfach problem
solutions for orders $n\in\\{7,8\\}$ we know that 2-factors on seven and eight
vertices have unique packing of three copies. Therefore, we may assume that
$n\geq 9$. We consider several cases according to $k$.

If $k=2$ then $G=C_{n_{1}}\cup C_{n_{2}}$ and $n_{1}\leq n_{2}$. If $n_{1}\geq
7$, we have disconnected packing of $G$ which consists of two components. Each
of these components we obtain as a packing of three copies of a cycle from
Lemma 12. Thus, by Lemma 11, the graph $G$ has two distinct packings of three
copies. Therefore, we have to consider four families of 2-factors:
$G=C_{3}\cup C_{x}$ where $x\geq 6$, $G=C_{4}\cup C_{x}$ where $x\geq 5$,
$G=C_{5}\cup C_{x}$ where $x\geq 5$ and $G=C_{6}\cup C_{x}$ where $x\geq 6$.
The uniqueness of packing of three copies of 2-factors from these families is
investigated in Section 4 for $x\geq 11$ and in Section 5 for $x\leq 10$.

If $k=3$ then $G=C_{n_{1}}\cup C_{n_{2}}\cup C_{n_{3}}$ and $n_{1}\leq
n_{2}\leq n_{3}$. We can divide $G$ into two subgraphs $G_{1}=C_{n_{1}}\cup
C_{n_{2}}$ and $G_{2}=C_{n_{3}}$. Thus, from Lemmas 12 and 15 we get a packing
of three copies of $G_{1}$ and $G_{2}$ except for the case $G=C_{3}\cup
C_{3}\cup C_{x}$ where $x\geq 3$, and the following twelve 2-factors:
$G=C_{3}\cup C_{4}\cup C_{4}$, $G=C_{3}\cup C_{4}\cup C_{5}$, $G=C_{3}\cup
C_{4}\cup C_{6}$,
$G=C_{4}\cup C_{4}\cup C_{4}$, $G=C_{4}\cup C_{4}\cup C_{5}$, $G=C_{4}\cup
C_{4}\cup C_{6}$,
$G=C_{4}\cup C_{5}\cup C_{5}$, $G=C_{4}\cup C_{5}\cup C_{6}$,
$G=C_{5}\cup C_{5}\cup C_{5}$, $G=C_{5}\cup C_{5}\cup C_{6}$,
$G=C_{5}\cup C_{6}\cup C_{6}$,
$G=C_{6}\cup C_{6}\cup C_{6}$.
Therefore, by Lemma 11, the graph $G$ has two distinct packings of three
copies. The uniqueness of packing of three copies of 2-factors from the family
$G=C_{3}\cup C_{3}\cup C_{x}$ where $x\geq 11$ is investigated in Section 4
and, in Section 5, we investigate 2-factors from the family $G=C_{3}\cup
C_{3}\cup C_{x}$ where $x\in\\{3,4,\ldots,11\\}$ and the above mentioned
twelve exceptional 2-factors.

If $k=4$ then $G=C_{n_{1}}\cup C_{n_{2}}\cup C_{n_{3}}\cup C_{n_{4}}$ and
$n_{1}\leq n_{2}\leq n_{3}\leq n_{4}$. If at least two $n_{i}$ (where
$i\in\\{1,2,3,4\\}$) are different from 3 then we can divide $G$ into two
parts $G=G_{1}\cup G_{2}$ such that both $G_{1}$ and $G_{2}$ have packing of
three copies by Lemma 15. Therefore, by Lemma 11, the graph $G$ has two
distinct packings of three copies. We argue similarly when $n_{4}\geq 7$
(however, in this case, we need to use also Lemma 12). Thus, we are left with
the following 2-factors: $G=C_{3}\cup C_{3}\cup C_{3}\cup C_{3}$, $G=C_{3}\cup
C_{3}\cup C_{3}\cup C_{4}$, $G=C_{3}\cup C_{3}\cup C_{3}\cup C_{5}$ and
$G=C_{3}\cup C_{3}\cup C_{3}\cup C_{6}$; the uniqueness of packing of three
copies of these four 2-factors is investigated in Section 5.

If $k=5$ then $G=C_{n_{1}}\cup C_{n_{2}}\cup C_{n_{3}}\cup C_{n_{4}}\cup
C_{n_{5}}$ and $n_{1}\leq n_{2}\leq n_{3}\leq n_{4}\leq n_{5}$. If $n_{5}\geq
4$, we can divide $G$ into two parts $G=G_{1}\cup G_{2}$ such that
$G_{1}=C_{n_{1}}\cup C_{n_{2}}\cup C_{n_{3}}$ and $G_{2}=C_{n_{4}}\cup
C_{n_{5}}$ have packing of three copies by Lemma 15. Therefore, by Lemma 11,
we know that $G$ has two distinct packings of three copies. Thus, we have to
investigate the uniqueness of packing of three copies of $G=5C_{3}$; this will
be done in Section 5.

If $k\geq 6$ then $G=C_{n_{1}}\cup C_{n_{2}}\cup\ldots\cup C_{n_{k}}$ and
$n_{1}\leq n_{2}\leq\ldots\leq n_{k}$. We can divide $G$ into two parts
$G=G_{1}\cup G_{2}$ so that $G_{1}=C_{n_{1}}\cup C_{n_{2}}\cup C_{n_{3}}$ and
$G_{2}=C_{n_{4}}\cup C_{n_{5}}\cup\ldots\cup C_{n_{k}}$. From Lemma 15 and the
fact that $k\geq 6$, we have packings of three copies of $G_{1}$ and $G_{2}$.
Therefore, $G$ has a disconnected packing of three copies, and, from Lemma 11,
we get the connected one.

##  4 Five particular families of 2-factors

In this section we present two distinct packings of three copies of 2-factors
from five families: $C_{3}\cup C_{x}$, $C_{4}\cup C_{x}$, $C_{5}\cup C_{x}$,
$C_{6}\cup C_{x}$ and $C_{3}\cup C_{3}\cup C_{x}$ where $x\geq 11$. We use the
construction approach. The first presented packing of three copies of these
2-factors will contain a clique $K_{5}$ whereas the second one will not. At
first, we present the packing with a clique $K_{5}$.

We start our construction of packing of three copies of 2-factors with a
clique $K_{5}$ from the smallest graphs in each family, that is, the graphs
$C_{3}\cup C_{11}$, $C_{4}\cup C_{11}$, $C_{5}\cup C_{11}$, $C_{6}\cup C_{11}$
and $C_{3}\cup C_{3}\cup C_{11}$. The packing of three copies of these
2-factors is presented in Figures 1 and 2.

Figure 1: The packing of three copies of $C_{3}\cup C_{11}$, $C_{4}\cup
C_{11}$, $C_{5}\cup C_{11}$ and $C_{6}\cup C_{11}$ with a clique $K_{5}$.
Figure 2: The packing of three copies of $C_{3}\cup C_{3}\cup C_{11}$ with a
clique $K_{5}$.

For the clarity of drawings, some cycles connecting vertices marked with the
same color and type of the marker are not drawn. More precisely, in Figure 1,
in the packing (of three copies) of $C_{3}\cup C_{11}$, we have also the red
cycle $v_{1}v_{4}v_{10}v_{1}$ and the blue cycle $v_{2}v_{12}v_{11}v_{2}$. In
the packing of $C_{4}\cup C_{11}$, we have also the red cycle
$v_{1}v_{4}v_{7}v_{10}v_{1}$ and the blue cycle
$v_{2}v_{12}v_{14}v_{11}v_{2}$. In the packing of $C_{5}\cup C_{11}$, we have
also the red cycle $v_{1}v_{4}v_{13}v_{7}v_{10}v_{1}$ and, in the packing of
$C_{6}\cup C_{11}$, we have also the red cycle
$v_{1}v_{4}v_{13}v_{16}v_{7}v_{10}v_{1}$. Similarly, in Figure 2, in the
packing of three copies of $C_{3}\cup C_{3}\cup C_{11}$, we have also red
cycles $v_{1}v_{4}v_{10}v_{1}$, $v_{7}v_{13}v_{15}v_{7}$ and blue cycles
$v_{2}v_{14}v_{15}v_{2}$, $v_{11}v_{13}v_{16}v_{11}$. Note that each of these
packings contains a subgraph $K_{5}$ induced by vertices $v_{5}$, $v_{6}$,
$v_{7}$, $v_{8}$ and $v_{9}$.

The presented packings of three copies of the smallest graphs from these
particular families are easily extendable to appropriate graphs from these
families if the longest cycle $C_{x}$ in the considered 2-factor has odd
length. Note that in every already-presented packing, the vertices $v_{10}$,
$v_{11}$, $v_{1}$, $v_{2}$ and $v_{3}$ induce almost the same subgraph (up to
the edge $v_{11}v_{2}$ which is not present in the packing of $C_{3}\cup
C_{3}\cup C_{11}$). Therefore, we introduce a common extension for these
packings in which we will change only the ”upper part” of the packing, which
contains vertices $v_{10}$, $v_{11}$, $v_{1}$, $v_{2}$, $v_{3}$ and edges
incident to them. The method of extension depends on the number of edges added
to the longest cycle in each copy of the smallest 2-factor in the respective
family. To increase the length of the longest cycle in each copy of the
smallest 2-factor in these families by 2, 4 or 6, we use appropriate extension
presented in Figure 3.

Figure 3: The extensions of packings of three copies of 2-factors from five
particular families when the longest cycle has odd length.

For better understanding, we describe each of these extensions in detail.

Extension by 2. At first, we replace black edges $v_{2}v_{3}$ and
$v_{11}v_{10}$ by black paths $v_{2}a_{1}v_{3}$ and $v_{11}b_{1}v_{10}$,
respectively. Then, we replace red edge $v_{11}v_{8}$ by red edge
$b_{1}v_{8}$. Next, we replace the red edge from the ”bottom part” to $v_{3}$
by the red edge from the same vertex in the ”bottom part” to $a_{1}$. Then, we
replace the blue edge from the ”bottom part” to $v_{1}$ by the blue edge from
the same vertex in the ”bottom part” to $b_{1}$. At the end, we add red edges
$b_{1}v_{3}$, $v_{11}a_{1}$ and the blue path $v_{1}a_{1}b_{1}$.

Extension by 4. At first, we replace black edges $v_{2}v_{3}$ and
$v_{11}v_{10}$ by black paths $v_{2}a_{1}a_{2}v_{3}$ and
$v_{11}b_{1}b_{2}v_{10}$, respectively. Then, we replace the red edge from the
”bottom part” to $v_{3}$ by the red edge from the same vertex in the ”bottom
part” to $a_{1}$. Next, we replace the blue edge from the ”bottom part” to
$v_{1}$ by the blue edge from the same vertex in the ”bottom part” to $b_{2}$.
Then, we remove the red edge $v_{11}v_{3}$. Next, we replace two red edges
from the ”bottom part” to $v_{2}$ by two red edges from the same vertices in
the ”bottom part” to $a_{2}$. At the end, we add the red path
$a_{1}v_{3}b_{1}v_{2}b_{2}v_{11}$ and the blue path
$v_{1}a_{1}b_{1}a_{2}b_{2}$.

Extension by 6. At first, we replace black edges $v_{2}v_{3}$ and
$v_{11}v_{10}$ by black paths $v_{2}a_{1}a_{2}a_{3}v_{3}$ and
$v_{11}b_{1}b_{2}b_{3}v_{10}$, respectively. Then, we replace the blue edge
from the ”bottom part” to $v_{1}$ by the blue edge from the same vertex in the
”bottom part” to $b_{3}$. Then, we remove the red edge $v_{11}v_{3}$ and the
blue edge $v_{1}v_{3}$. Next, we replace two red edges from the ”bottom part”
to $v_{2}$ by two red edges from the same vertices in the ”bottom part” to
$a_{3}$. At the end, we add the red path
$v_{3}b_{1}v_{2}b_{3}a_{2}b_{2}a_{1}v_{11}$ and the blue path
$v_{3}b_{2}a_{3}b_{1}a_{2}v_{1}a_{1}b_{3}$.

Now, we describe how to create the packing of three copies of a 2-factor with
the longest cycle $C_{11+2t}$, for $t>3$, from the smallest 2-factor in the
respective family. At first, we replace black edges $v_{2}v_{3}$ and
$v_{11}v_{10}$ by black paths $v_{2}a_{1}a_{2}\ldots a_{t}v_{3}$ and
$v_{11}b_{1}b_{2}\ldots b_{t}v_{10}$, respectively. Then, we replace the blue
edge from the ”bottom part” to $v_{1}$ by the blue edge from the same vertex
in the ”bottom part” to $b_{t}$. Then, we remove the red edge $v_{11}v_{3}$
and the blue edge $v_{1}v_{3}$. At the end, we add the red path
$v_{3}b_{1}a_{t}b_{t}a_{t-1}b_{t-1}\ldots a_{2}b_{2}a_{1}v_{11}$ and the blue
path $v_{3}b_{t-1}a_{t}b_{t-2}a_{t-1}\ldots
b_{2}a_{3}b_{1}a_{2}v_{1}a_{1}b_{t}$. This extension of packing of three
copies is also presented in Figure 3.

Now, we show how to obtain a packing of three copies of a 2-factor from each
of these families, if the longest cycle in 2-factor has an even length $x$. We
take the packing of three copies of a 2-factor in which the longest cycle has
length $x-1$. We replace: the black edge $v_{1}v_{2}$ by the black path
$v_{1}v_{c}v_{2}$, the blue edge $v_{10}v_{3}$ by the blue path
$v_{10}v_{c}v_{3}$, the red edge $v_{11}v_{8}$ by the red path
$v_{11}v_{c}v_{8}$ (if $x=14$, we replace the red edge $v_{11}a_{1}$ by the
red path $v_{11}v_{c}a_{1}$). Thus, we obtain a packing of three copies of a
2-factor from each of these families if the longest cycle in 2-factor has an
even length. Note that in each packing which we obtain using the above
extensions we have induced subgraph $K_{5}$ on vertices $v_{5}$, $v_{6}$,
$v_{7}$, $v_{8}$ and $v_{9}$.

Next, we present packings of three copies of 2-factors from these five
particular families without a clique $K_{5}$. The following observation is
particularly useful for the construction:

######  Observation 17.

Let $B$ be a union of cycles, let $q\geq 3$, and let $G$ be an instance of a
$K_{5}$-free packing of three copies of $B\cup C_{q}$. If there are three
independent edges $e_{1}$, $e_{2}$, and $e_{3}$ on $C_{q}$ in the black, the
blue, and the red copy of $B\cup C_{q}$, then there is a $K_{5}$-free packing
of three copies of $B\cup C_{q+1}$.

###### Proof.

Let $e_{1}=x_{1}x_{2}$, $e_{2}=y_{1}y_{2}$, and $e_{3}=z_{1}z_{2}$. Let $w$ be
a new vertex. Replace edges $x_{1}x_{2},y_{1}y_{2},z_{1}z_{2}$ with edges
$x_{1}w,wx_{2},y_{1}w,wy_{2},z_{1}w,wz_{2}$. The new graph $G^{\prime}$ is a
packing of three copies of $C_{3}\cup C_{q+1}$. Moreover, since no edges were
added between the vertices of $V(G)$, the 5-clique, if there is one, contains
$w$. Let there be a 5-clique $A$ containing $w$ in $G^{\prime}$. This clique
contains four neighbors of $w$, and, therefore, it contains two neighbors of
$w$ which were adjacent in $G$ but are not adjacent in $G^{\prime}$; this,
however, contradicts the fact that $A$ is a clique. ∎

Note that, instead of adding one new vertex, it is possible to add $k$
vertices at once, if there are $k$ pairwise edge-disjoint matchings, each
consisting of three edges of $G$ lying on $C_{q}$ in the black, the blue, and
the red subgraph of $G$, respectively. We will use this fact later.

Figure 4: $K_{5}$-free packing of three copies of $C_{3}\cup C_{11}$.

Consider first the packing of three copies of $C_{3}\cup C_{11}$ in Figure 4;
note that this graph is $K_{5}$-free, which can be checked using computer. We
now show how to extend the packing in Figure 4 to a $K_{5}$-free packing of
three copies of $C_{3}\cup C_{11+4t}$ for some positive integer $t$. Denote by
$G$ the graph in Figure 4. Let $G^{\prime}$ be a graph obtained from $G$ after
removing edges
$v_{3}v_{4},v_{3}v_{12},v_{4}v_{5},v_{4}v_{10},v_{5}v_{9},v_{8}v_{9},v_{8}v_{13},v_{9}v_{10}$
(dashed edges in Figure 4), adding new vertices $a_{i},b_{i},c_{i},d_{i}$ for
$i\in\\{1,\dots,t\\}$, and adding edges of the (black) paths
$v_{3}(a_{i})_{i=1}^{t}v_{9}$, $v_{5}(b_{i})_{i=1}^{t}v_{4}$,
$v_{10}(c_{i})_{i=1}^{t}v_{9}$ and $v_{8}(d_{i})_{i=1}^{t}v_{9}$, (blue) paths
$v_{10}(a_{i}c_{i})_{i=1}^{t}v_{4}$ and $v_{5}(d_{i}b_{i})_{i=1}^{t}v_{9}$,
and (red) paths $v_{3}(b_{i}a_{i})_{i=1}^{t}v_{12}$ and
$v_{8}(c_{i}d_{i})_{i=1}^{t}v_{13}$. For an overview of the added part, see
Figure 5.

Figure 5: The subgraph $H$ of the $K_{5}$-free packing of three copies of
$C_{3}\cup C_{11+4t}$ induced on $4t$ added vertices and their neighbors.
Dashed edges are newly added edges, full edges are old edges.

In the following, we refer to vertices from $\\{v_{1},\dots,v_{14}\\}$ as old
vertices, and other vertices of $G^{\prime}$ as new vertices.

It follows from the construction that $G^{\prime}$ is a packing of three
copies of $C_{3}\cup C_{11+4t}$, however, the absence of $K_{5}$ in
$G^{\prime}$ is not clear. Therefore, suppose to the contrary that there is a
copy of $K_{5}$ in $G^{\prime}$. Let $H$ be a subgraph of $G^{\prime}$ induced
on new vertices and their neighbors (see Figure 5). Note that no edge between
two old vertices was added in the construction; hence, if there is a clique on
five vertices, it contains at least one new vertex. Thus, each 5-clique in
$G^{\prime}$ is a 5-clique in $H$. Note also that $H-a_{1}$ is 3-degenerate
(consider for example the ordering
$v_{12},v_{13},v_{3},v_{10},v_{8},v_{5},c_{1},d_{1},\dots,c_{t},d_{t},v_{9},b_{1},a_{2},b_{2},\dots
a_{t},b_{t},v_{4}$); hence, if there is a 5-clique in $H$, then it contains
$a_{1}$. However, $a_{1}$ and its neighbors induce a planar graph, see Figure
6. Hence, there is no 5-clique in $G$.

Figure 6: The subgraph induced on $N(a_{1})\cup\\{a_{1}\\}$ for $t\geq 2$
(left) and $t=1$ (right).

Using Observation 17 for all three (pairwise edge-disjoint) matchings
$v_{1}v_{3},v_{6}v_{11},v_{7}v_{8}$, $v_{1}v_{5},v_{6}v_{13},v_{10}v_{11}$,
and $v_{1}v_{11},v_{3}v_{10},v_{9}v_{12}$ at once, we get that there is a
$K_{5}$-free packing of $C_{3}\cup C_{11+4t+q}$ for every nonnegative integer
$t$ and every $q\in\\{0,1,2,3\\}$. This covers all the cases of packings of
three copies of $C_{3}\cup C_{x}$, $x\geq 11$. Moreover, such a construction
does not remove any of the edges of the initial black, blue, or red copy of
$C_{3}$; this will be useful to extend created $K_{5}$-free packings of three
copies of $C_{3}\cup C_{x}$ to $K_{5}$-free packings of $C_{y}\cup C_{x}$ for
$y\in\\{4,5,6\\}$. To obtain a packing of three copies of $C_{4}\cup C_{x}$,
apply Observation 17 for $B=C_{x}$, $q=4$, $e_{1}=v_{12}v_{13}$,
$e_{2}=v_{2}v_{11}$, and $e_{3}=v_{4}v_{14}$; for later use, denote the newly
added vertex by $w_{1}$.

Note that there are no larger sets of matchings of desired properties in the
packing of three copies of $C_{3}\cup C_{x}$ that could be used to extend them
to a packing of three copies of $C_{5}\cup C_{x}$ or $C_{6}\cup C_{x}$ at
once. However, we can do it in steps. Observe that, in the created packing of
three copies of $C_{4}\cup C_{x}$, the black edge $w_{1}v_{13}$, the blue edge
$v_{11}v_{12}$, and the red edge $v_{2}v_{14}$ form a matching, and we can
make use of Observation 17 to obtain a $K_{5}$-free packing of three copies of
$C_{5}\cup C_{x}$; denote the newly added vertex by $w_{2}$ (see Figure 7). To
obtain a packing of three copies of $C_{6}\cup C_{x}$, simply repeat the
previous step for edges $v_{13}v_{14},v_{11}w_{2},v_{2}v_{4}$.

Figure 7: Extensions of monochromatic triangles. Dashed edges are edges of a
matching for which Observation 17 is used.

Finally we show how to obtain a $K_{5}$-free packing of three copies of
$C_{3}\cup C_{3}\cup C_{x}$ for $x\geq 11$. The process is similar to the case
of $K_{5}$-free packings of three copies of $C_{3}\cup C_{x}$. We start with
the initial packing $G$ of three copies of $C_{3}\cup C_{3}\cup C_{11}$
displayed in Figure 8. Using a computer check, one can find that such a
packing is $K_{5}$-free (in this case, the size of the maximum clique is
three).

Figure 8: $K_{5}$-free packing of three copies of $C_{3}\cup C_{3}\cup
C_{11}$.

We show how to extend $G$ to a $K_{5}$-free packing of three copies of
$C_{3}\cup C_{3}\cup C_{11+4t}$ for some positive integer $t$, using a similar
approach as previously. Let $G^{\prime}$ be a graph obtained from $G$ by
adding $4t$ new vertices, namely $a_{i},b_{i},c_{i},d_{i}$ for
$i\in\\{1,\dots,t\\}$, removing the edges
$v_{3}v_{4},v_{3}v_{10},v_{4}v_{5},v_{4}v_{9},v_{5}v_{12},v_{9}v_{10},v_{9}v_{17},v_{10}v_{11}$
(dashed edges in Figure 8), and adding (black) paths
$v_{11}(a_{i})_{i=1}^{t}v_{10}$, $v_{3}(b_{i})_{i=1}^{t}v_{4}$,
$v_{9}(c_{i})_{i=1}^{t}v_{10}$, and $v_{5}(d_{i})_{i=1}^{t}v_{4}$, (blue)
paths $v_{11}(b_{i}a_{i})_{i=1}^{t}v_{4}$ and
$v_{5}(c_{i}d_{i})_{i=1}^{t}v_{10}$, and (red) paths
$v_{9}(a_{i}c_{i})_{i=1}^{t}v_{17}$ and $v_{5}(b_{i}d_{i})_{i=1}^{t}v_{12}$
(see Figure 9).

Figure 9: The subgraph $H$ induced on new vertices and their neighborhood in
the $K_{5}$-free packing of three copies of $C_{3}\cup C_{3}\cup C_{11+4t}$.
Dashed edges are newly added edges.

Clearly, the presented construction creates a packing of three copies of
$C_{3}\cup C_{3}\cup C_{11+4t}$. Suppose that a 5-clique $A$ was created in
the process. Since no edge between two old vertices (that is, the vertices
from $\\{v_{1},\dots,v_{17}\\}$) was added, at least one of the vertices of
$A$ is a new vertex. Hence, the 5-clique is present in a subgraph $H$ induced
on new vertices and their neighbors, see Figure 9.

Vertices $v_{12}$ and $v_{17}$ are of degree two in $H$, and the vertex
$v_{3}$ is of degree three in $H$, hence, none of them is in $A$.

Vertices $v_{4}$, $v_{9}$, $v_{10}$ and $v_{11}$ are of degree four in $H$.
Thus, if any of them is contained in the 5-clique $A$, then all its neighbors
are from $A$; however, for each of these vertices, there are two of its
neighbors that are not adjacent. Namely, for $v_{9}$, the vertices $v_{5}$ and
$v_{11}$ are not adjacent, for $v_{11}$, the vertices $v_{3}$ and $v_{9}$ are
not adjacent, and, for $v_{4}$ and $v_{10}$, the vertices $a_{t}$ and $d_{t}$
are not adjacent. Since the degree of $v_{5}$ in $H$ is five and at least two
of its neighbors are not from the 5-clique $A$ (namely $v_{3}$ and $v_{9}$),
we get that $v_{5}\notin A$. Hence, $A$ contains only new vertices. However,
the subgraph of $G^{\prime}$ induced on new vertices is 3-degenerate (consider
the vertex ordering
$b_{1},a_{1},b_{2}\dots,a_{t},c_{1},d_{1},c_{2},\dots,d_{t}$) and, therefore,
it does not contain a 5-clique.

Now, we show how to extend the constructed $K_{5}$-free packing of three
copies of $C_{3}\cup C_{3}\cup C_{11+4t}$ to a $K_{5}$-free packing of three
copies of $C_{3}\cup C_{3}\cup C_{11+4t+q}$ for $q\in\\{1,2,3\\}$. In all
cases, use Observation 17 for three (pairwise edge-disjoint) matchings
$v_{1}v_{2},v_{14}v_{15},v_{3}v_{5}$, $v_{2}v_{3},v_{6}v_{15},v_{9}v_{11}$,
and $v_{6}v_{7},v_{5}v_{8},v_{9}v_{17}$. This completes the proof in case of
five particular families of 2-factors.

##  5 Remaining small cases

This section contains the discussion on the uniqueness of packings of three
copies of small 2-factors which were not treated by general constructions in
Section 4. First, note that the packing of three copies of $3C_{3}$ is unique,
as it corresponds to Steiner triple system STS(9) on nine points
(equivalently, to the affine plane of order three), which is unique. For the
remaining 46 small 2-factors, Table 1 contains description of two distinct
packings of three copies of particular 2-factors; each of three 2-factors is
presented as a collection of sequences of vertices of its cycles. Moreover, we
present two distinct packings of three copies of these 2-factors for which the
Oberwolfach problem has not solution in Figures 10, 11 and 12.

Figure 10: Two distinct packings of three copies of $C_{4}\cup C_{5}$. Figure
11: Two distinct packings of three copies of $2C_{3}\cup C_{5}$. Figure 12:
Two distinct packings of three copies of $4C_{3}$.

For computer-assisted finding of these distinct packings, we used Wolfram
Mathematica computer algebra system with its graph theory procedures. About
the half of cases was solved using the following strategy: considering a
2-factor $H\cong C_{n_{1}}\cup\ldots\cup C_{n_{k}}$, we first removed from the
complete graph $K_{n_{1}+\ldots+n_{k}}$ the cycles
$(1,\dots,n_{1}),(n_{1}+1,n_{1}+2,\ldots,n_{1}+n_{2}),\dots,(n_{1}+\ldots+n_{k-1}+1,\dots,n_{1}+n_{2}+\ldots+n_{k})$.
In the resulting graph $G_{1}$, we were looking for several distinct subgraphs
isomorphic to $H$ (using the procedure FindIsomorphicSubgraph[$G$,$H$,$p$]
which allows to find either all, or at most $p$ distinct copies of $H$ in
$G$). Among the graphs resulted from removing these subgraphs from $G_{1}$, we
were looking for two nonisomorphic graphs
$G_{2}^{\prime},G_{2}^{\prime\prime}$, and, in them, we again looked for
distinct subgraphs isomorphic to $H$. Finally, in two collections of graphs
obtained from $G_{2}^{\prime},G_{2}^{\prime\prime}$ by third removal of
isomorphic copies of $H$, we were able to find two nonisomorphic graphs; their
complements yielded the desired distinct packings.

We have to notice that this strategy failed when $k=3,n_{1}\geq 4,n_{2}\geq 5$
and, also, when $k\geq 4$: the procedure
FindIsomorphicSubgraph[$G_{1}$,$H$,$p$] was able to find only at most three
distinct copies of $H$ in $G_{1}$ (higher values of $p$ resulted in
computation crash), and further attempts to look for copies of $H$ in
$G_{2}^{\prime},G_{2}^{\prime\prime}$ have led to computation crash or to
isomorphic graphs. To overcome these obstacles, we have generated, for each of
the remaining cases, a collection of distinct packings of two copies of $H$
using the code in Python (which took a fixed 2-factor, then renamed its
vertices using a random permutation to obtain another 2-factor with the same
cycle structure, and then checked whether these two 2-factors are edge
disjoint and forming together a 4-regular graph). These packings of two copies
of $H$ were first removed from $K_{n_{1}+\ldots+n_{k}}$ and, in each of the
obtained graphs, a single third copy of $H$ was searched for (again using
FindIsomorphicSubgraph[] procedure). Among the graphs resulted from this
removal, we searched for a pair of nonisomorphic ones (again, their
complements yielded the desired packings).

2-factor | First packing | Second packing
---|---|---
$C_{3}\cup C_{6}$ | $(1,2,3),(4,5,6,7,8,9)$ | $(1,2,3),(4,5,6,7,8,9)$
| $(3,4,6),(1,8,2,5,7,9)$ | $(3,4,6),(1,5,9,7,2,8)$
| $(2,6,9),(1,4,8,5,3,7)$ | $(2,6,9),(1,4,8,5,3,7)$
$C_{3}\cup C_{7}$ | $(1,2,3),(4,5,6,7,8,9,10)$ | $(1,2,3),(4,5,6,7,8,9,10)$
| $(1,4,6),(2,5,3,8,10,7,9)$ | $(1,4,6),(2,5,7,9,3,8,10)$
| $(1,5,7),(2,4,8,6,9,3,10)$ | $(1,5,8),(2,4,3,7,10,6,9)$
$C_{3}\cup C_{8}$ | $(1,2,3),(4,5,6,7,8,9,10,11)$ | $(1,2,3),(4,5,6,7,8,9,10,11)$
| $(1,4,6),(2,5,3,7,9,11,8,10)$ | $(1,4,6),(2,5,3,8,10,7,11,9)$
| $(1,5,7),(2,8,3,9,4,10,6,11)$ | $(1,5,7),(2,4,8,11,3,9,6,10)$
$C_{3}\cup C_{9}$ | $(1,2,3),(4,5,6,7,8,9,10,11,12)$ | $(1,2,3),(4,5,6,7,8,9,10,11,12)$
| $(1,4,6),(2,5,3,7,9,11,8,10,12)$ | $(1,4,6),(2,5,3,7,9,11,8,12,10)$
| $(1,5,7),(2,4,8,12,9,3,10,6,11)$ | $(1,5,7),(2,4,8,10,3,9,12,6,11)$
$C_{3}\cup C_{10}$ | $(1,2,3),(4,5,6,7,8,9,10,11,12,13)$ | $(1,2,3),(4,5,6,7,8,9,10,11,12,13)$
| $(1,4,6),(2,5,3,7,9,11,8,12,10,13)$ | $(1,4,6),(2,5,3,7,9,11,8,13,10,12)$
| $(1,5,7),(2,4,3,8,10,6,11,13,9,12)$ | $(1,5,7),(2,4,3,6,10,8,12,9,13,11)$
$C_{4}\cup C_{5}$ | $(1,2,3,4),(5,6,7,8,9)$ | $(1,2,3,4),(5,6,7,8,9)$
| $(1,3,5,7),(2,4,8,6,9)$ | $(1,3,5,7),(2,6,8,4,9)$
| $(1,5,2,8),(3,6,4,7,9)$ | $(1,5,2,8),(3,6,4,7,9)$
$C_{4}\cup C_{6}$ | $(1,2,3,4),(5,6,7,8,9,10)$ | $(1,2,3,4),(5,6,7,8,9,10)$
| $(1,3,5,7),(2,4,8,10,6,9)$ | $(1,3,5,7),(2,6,8,10,4,9)$
| $(1,5,2,8),(3,6,4,9,7,10)$ | $(1,5,2,8),(3,9,6,4,7,10)$
$C_{4}\cup C_{7}$ | $(1,2,3,4),(5,6,7,8,9,10,11)$ | $(1,2,3,4),(5,6,7,8,9,10,11)$
| $(1,3,5,7),(2,4,6,9,11,8,10)$ | $(1,3,5,7),(2,4,8,10,6,9,11)$
| $(1,5,2,8),(3,6,10,4,9,7,11)$ | $(1,5,2,6),(3,8,11,4,9,7,10)$
$C_{4}\cup C_{8}$ | $(1,2,3,4),(5,6,7,8,9,10,11,12)$ | $(1,2,3,4),(5,6,7,8,9,10,11,12)$
| $(1,3,5,7),(2,4,6,8,10,12,9,11)$ | $(1,3,5,7),(2,4,6,9,11,8,10,12)$
| $(1,5,2,6),(3,9,4,10,7,11,8,12)$ | $(1,5,2,6),(3,8,12,9,4,10,7,11)$
$C_{4}\cup C_{9}$ | $(1,2,3,4),(5,6,7,8,9,10,11,12,13)$ | $(1,2,3,4),(5,6,7,8,9,10,11,12,13)$
| $(1,3,5,7),(2,4,6,8,10,12,9,11,13)$ | $(1,3,5,7),(2,4,6,8,10,12,9,13,11)$
| $(1,5,2,6),(3,7,9,13,10,4,11,8,12)$ | $(1,5,2,6),(3,7,9,11,4,10,13,8,12)$
$C_{4}\cup C_{10}$ | $(1,2,3,4),(5,6,7,8,9,10,11,12,13,14)$ | $(1,2,3,4),(5,6,7,8,9,10,11,12,13,14)$
| $(1,3,5,7),(2,4,6,8,10,12,9,13,11,14)$ | $(1,3,5,7),(2,4,6,8,10,12,9,14,11,13)$
| $(1,5,2,6),(3,7,4,9,11,8,12,14,10,13)$ | $(1,5,2,6),(3,7,4,8,11,9,13,10,14,12)$
$C_{5}\cup C_{5}$ | $(1,2,3,4,5),(6,7,8,9,10)$ | $(1,2,3,4,5),(6,7,8,9,10)$
| $(1,3,5,6,8),(2,4,9,7,10)$ | $(1,3,5,2,6),(4,8,10,7,9)$
| $(1,4,6,2,7),(3,8,10,5,9)$ | $(1,4,7,2,10),(3,6,8,5,9)$
$C_{5}\cup C_{6}$ | $(1,2,3,4,5),(6,7,8,9,10,11)$ | $(1,2,3,4,5),(6,7,8,9,10,11)$
| $(1,3,5,2,4),(6,8,10,7,11,9)$ | $(1,3,5,2,6),(4,7,9,11,8,10)$
| $(1,6,2,7,9),(3,8,4,10,5,11)$ | $(1,4,2,7,11),(3,8,5,9,6,10)$
$C_{5}\cup C_{7}$ | $(1,2,3,4,5),(6,7,8,9,10,11,12)$ | $(1,2,3,4,5),(6,7,8,9,10,11,12)$
| $(1,3,5,2,4),(6,8,10,7,12,9,11)$ | $(1,3,5,2,4),(6,8,11,7,9,12,10)$
| $(1,6,2,7,9),(3,8,4,10,12,5,11)$ | $(1,6,2,7,10),(3,8,4,9,11,5,12)$
$C_{5}\cup C_{8}$ | $(1,2,3,4,5),(6,7,8,9,10,11,12,13)$ | $(1,2,3,4,5),(6,7,8,9,10,11,12,13)$
| $(1,3,5,2,4),(6,8,10,7,11,13,9,12)$ | $(1,3,5,2,4),(6,8,10,7,12,9,13,11)$
| $(1,6,2,7,9),(3,8,4,11,5,12,10,13)$ | $(1,6,2,7,9),(3,8,4,11,5,12,10,13)$
$C_{5}\cup C_{9}$ | $(1,2,3,4,5),(6,7,8,9,10,11,12,13,14)$ | $(1,2,3,4,5),(6,7,8,9,10,11,12,13,14)$
| $(1,3,5,2,4),(6,8,10,7,9,12,14,11,13)$ | $(1,3,5,2,4),(6,8,10,7,11,13,9,14,12)$
| $(1,6,2,7,11),(3,8,4,9,13,5,12,10,14)$ | $(1,6,2,7,9),(3,8,4,11,14,5,12,10,13)$
$C_{5}\cup C_{10}$ | $(1,2,3,4,5),(6,7,8,9,10,11,12,13,14,15)$ | $(1,2,3,4,5),(6,7,8,9,10,11,12,13,14,15)$
| $(1,3,5,2,4),(6,8,10,7,9,11,13,15,12,14)$ | $(1,3,5,2,4),(6,8,10,7,9,12,14,11,15,13)$
| $(1,6,2,7,11),(3,8,4,12,5,13,9,14,10,15)$ | $(1,6,2,7,11),(3,8,4,9,13,5,12,15,10,14)$
$C_{6}\cup C_{6}$ | $(1,2,3,4,5,6),(7,8,9,10,11,12)$ | $(1,2,3,4,5,6),(7,8,9,10,11,12)$
| $(1,3,5,2,4,7),(6,8,10,12,9,11)$ | $(1,3,5,2,4,7),(6,9,11,8,12,10)$
| $(1,4,6,2,7,9),(3,10,5,11,8,12)$ | $(1,4,6,2,7,11),(3,8,10,5,9,12)$
$C_{6}\cup C_{7}$ | $(1,2,3,4,5,6),(7,8,9,10,11,12,13)$ | $(1,2,3,4,5,6),(7,8,9,10,11,12,13)$
| $(1,3,5,2,4,7),(6,8,10,12,9,11,13)$ | $(1,3,5,2,4,7),(6,8,10,12,9,13,11)$
| $(1,4,6,2,7,9),(3,10,13,5,11,8,12)$ | $(1,4,6,2,7,9),(3,10,13,5,11,8,12)$
$C_{6}\cup C_{8}$ | $(1,2,3,4,5,6),(7,8,9,10,11,12,13,14)$ | $(1,2,3,4,5,6),(7,8,9,10,11,12,13,14)$
| $(1,3,5,2,4,7),(6,8,10,12,9,13,11,14)$ | $(1,3,5,2,4,7),(6,8,10,12,9,14,11,13)$
| $(1,4,6,2,7,5),(3,9,11,8,12,14,10,13)$ | $(1,4,6,2,7,5),(3,8,11,9,13,10,14,12)$
$C_{6}\cup C_{9}$ | $(1,2,3,4,5,6),(7,8,9,10,11,12,13,14,15)$ | $(1,2,3,4,5,6),(7,8,9,10,11,12,13,14,15)$
| $(1,3,5,2,4,7),(6,8,10,12,9,13,15,11,14)$ | $(1,3,5,2,4,7),(6,8,10,12,9,14,11,13,15)$
| $(1,4,6,2,7,5),(3,8,11,9,14,12,15,10,13)$ | $(1,4,6,2,7,5),(3,8,11,9,13,10,14,12,15)$
$C_{6}\cup C_{10}$ | $(1,2,3,4,5,6),(7,8,9,10,11,12,13,14,15,16)$ | $(1,2,3,4,5,6),(7,8,9,10,11,12,13,14,15,16)$
| $(1,3,5,2,4,7),(6,8,10,12,9,11,14,16,13,15)$ | $(1,3,5,2,4,7),(6,8,10,12,9,13,15,11,14,16)$
| $(1,4,6,2,7,5),(3,8,11,13,9,14,10,15,12,16)$ | $(1,4,6,2,7,5),(3,8,11,9,14,12,15,10,13,16)$
$2C_{3}\cup C_{4}$ | $(1,2,3),(4,5,6),(7,8,9,10)$ | $(1,2,3),(4,5,6),(7,8,9,10)$
| $(1,4,7),(2,5,8),(3,9,6,10)$ | $(1,4,7),(2,5,9),(3,8,6,10)$
| $(1,5,9),(2,4,10),(3,7,6,8)$ | $(1,5,8),(2,4,10),(3,7,6,9)$
$2C_{3}\cup C_{5}$ | $(1,2,3),(4,5,6),(7,8,9,10,11)$ | $(1,2,3),(4,5,6),(7,8,9,10,11)$
| $(1,4,7),(2,5,8),(3,9,11,6,10)$ | $(1,4,7),(2,5,9),(3,8,10,6,11)$
| $(1,5,9),(2,4,10),(3,7,6,8,11)$ | $(1,5,8),(2,4,11),(3,9,6,7,10)$

2-factor First packing Second packing $2C_{3}\cup C_{6}$
$(1,2,3),(4,5,6),(7,8,9,10,11,12)$ $(1,2,3),(4,5,6),(7,8,9,10,11,12)$
$(1,4,7),(2,5,8),(3,6,10,12,9,11)$ $(1,4,7),(2,5,8),(3,9,11,6,10,12)$
$(1,5,9),(2,4,10),(3,7,6,11,8,12)$ $(1,5,9),(2,4,10),(3,6,12,8,11,7)$
$2C_{3}\cup C_{7}$ $(1,2,3),(4,5,6),(7,8,9,10,11,12,13)$
$(1,2,3),(4,5,6),(7,8,9,10,11,12,13)$ $(1,4,7),(2,5,8),(3,6,9,11,13,10,12)$
$(1,4,7),(2,5,8),(3,6,10,12,9,13,11)$ $(1,5,9),(2,4,10),(3,7,11,6,12,8,13)$
$(1,5,9),(2,4,10),(3,7,11,6,12,8,13)$ $2C_{3}\cup C_{8}$
$(1,2,3),(4,5,6),(7,8,9,10,11,12,13,14)$
$(1,2,3),(4,5,6),(7,8,9,10,11,12,13,14)$
$(1,4,7),(2,5,8),(3,6,9,11,13,10,12,14)$
$(1,4,7),(2,5,8),(3,6,9,11,13,10,14,12)$
$(1,5,9),(2,4,10),(3,7,11,14,6,12,8,13)$
$(1,5,9),(2,4,10),(3,7,11,14,6,12,8,13)$ $2C_{3}\cup C_{9}$
$(1,2,3),(4,5,6),(7,8,9,10,11,12,13,14,15)$
$(1,2,3),(4,5,6),(7,8,9,10,11,12,13,14,15)$
$(1,4,7),(2,5,8),(3,6,9,11,13,10,14,12,15)$
$(1,4,7),(2,5,8),(3,6,9,11,13,10,15,12,14)$
$(1,5,9),(2,4,10),(3,7,6,12,8,13,15,11,14)$
$(1,5,9),(2,4,10),(3,7,6,12,8,14,11,15,13)$ $2C_{3}\cup C_{10}$
$(1,2,3),(4,5,6),(7,8,9,10,11,12,13,14,15,16)$
$(1,2,3),(4,5,6),(7,8,9,10,11,12,13,14,15,16)$
$(1,4,7),(2,5,8),(3,6,9,11,13,10,14,16,12,15)$
$(1,4,7),(2,5,8),(3,6,9,11,13,10,15,12,14,16)$
$(1,5,9),(2,4,10),(3,7,6,8,12,14,11,15,13,16)$
$(1,5,9),(2,4,10),(3,7,6,11,14,8,12,16,13,15)$ $C_{3}\cup 2C_{4}$
$(1,2,3),(4,5,6,7),(8,9,10,11)$ $(1,2,3),(4,5,6,7),(8,9,10,11)$
$(1,4,6),(2,5,8,10),(3,7,9,11)$ $(1,4,6),(2,5,8,10),(3,9,7,11)$
$(1,5,7),(2,8,3,9),(4,10,6,11)$ $(1,5,7),(2,4,9,11),(3,8,6,10)$ $C_{3}\cup
C_{4}\cup C_{5}$ $(1,2,3),(4,5,6,7),(8,9,10,11,12)$
$(1,2,3),(4,5,6,7),(8,9,10,11,12)$ $(1,4,6),(2,5,3,7),(8,10,12,9,11)$
$(1,4,6),(2,5,3,8),(7,10,12,9,11)$ $(1,5,8),(2,9,4,10),(3,6,11,7,12)$
$(1,5,7),(2,9,3,10),(4,8,11,6,12)$ $C_{3}\cup C_{4}\cup C_{6}$
$(1,2,3),(4,5,6,7),(8,9,10,11,12,13)$ $(1,2,3),(4,5,6,7),(8,9,10,11,12,13)$
$(1,5,7),(2,4,8,12),(3,9,11,6,10,13)$ $(1,5,7),(2,8,3,11),(4,9,13,6,10,12)$
$(1,4,6),(2,5,3,7),(8,10,12,9,13,11)$ $(1,4,6),(2,5,3,7),(8,10,13,11,9,12)$
$3C_{4}$ $(1,2,3,4),(5,6,7,8),(9,10,11,12)$ $(1,2,3,4),(5,6,7,8),(9,10,11,12)$
$(1,3,5,7),(2,4,9,11),(6,8,10,12)$ $(1,3,5,7),(2,4,9,11),(6,10,8,12)$
$(1,5,2,6),(3,9,7,10),(4,11,8,12)$ $(1,5,2,6),(3,9,8,11),(4,7,10,12)$
$2C_{4}\cup C_{5}$ $(1,2,3,4),(5,6,7,8),(9,10,11,12,13)$
$(1,2,3,4),(5,6,7,8),(9,10,11,12,13)$ $(1,3,5,7),(2,4,6,8),(9,11,13,10,12)$
$(1,3,5,7),(2,4,6,8),(9,11,13,10,12)$ $(1,5,2,9),(3,10,6,11),(4,7,12,8,13)$
$(1,5,2,9),(3,10,7,11),(4,8,12,6,13)$ $2C_{4}\cup C_{6}$
$(1,2,3,4),(5,6,7,8),(9,10,11,12,13,14)$
$(1,2,3,4),(5,6,7,8),(9,10,11,12,13,14)$
$(1,6,9,12),(4,11,8,14),(2,5,3,13,10,7)$
$(2,12,3,13),(4,6,10,7),(1,5,14,11,9,8)$
$(1,3,6,8),(2,4,5,9),(7,12,10,14,11,13)$
$(1,3,5,7),(2,4,8,10),(6,11,13,9,12,14)$ $C_{4}\cup 2C_{5}$
$(1,2,3,4),(5,6,7,8,9),(10,11,12,13,14)$
$(1,2,3,4),(5,6,7,8,9),(10,11,12,13,14)$
$(2,9,4,14),(1,3,12,8,5),(6,10,7,13,11)$
$(1,3,9,11),(2,5,14,7,12),(4,6,10,8,13)$
$(1,6,2,7),(3,5,4,8,11),(9,13,10,12,14)$
$(1,5,3,6),(2,4,7,9,14),(8,11,13,10,12)$ $C_{4}\cup C_{5}\cup C_{6}$
$(1,2,3,4),(5,6,7,8,9),(10,11,12,13,14,15)$
$(1,2,3,4),(5,6,7,8,9),(10,11,12,13,14,15)$
$(3,14,8,15),(1,10,2,7,13),(4,5,11,6,9,12)$
$(2,6,12,7),(1,10,14,5,13),(3,9,15,8,4,11)$
$(1,3,5,7),(2,4,6,8,11),(9,10,13,15,12,14)$
$(1,3,5,7),(2,4,6,8,10),(9,11,13,15,12,14)$ $3C_{5}$
$(1,2,3,4,5),(6,7,8,9,10),(11,12,13,14,15)$
$(1,2,3,4,5),(6,7,8,9,10),(11,12,13,14,15)$
$(1,7,11,2,14),(3,5,9,6,15),(4,10,12,8,13)$
$(1,7,5,2,15),(3,6,13,4,8),(9,12,10,11,14)$
$(1,3,6,2,4),(5,7,9,11,8),(10,13,15,12,14)$
$(1,3,5,6,4),(2,7,9,11,8),(10,13,15,12,14)$ $2C_{5}\cup C_{6}$
$(1,2,3,4,5),(6,7,8,9,10),(11,12,13,14,15,16)$
$(1,2,3,4,5),(6,7,8,9,10),(11,12,13,14,15,16)$
$(1,4,16,10,12),(2,7,9,5,8),(3,14,6,13,11,15)$
$(1,10,15,6,12),(2,7,4,14,16),(3,5,13,9,11,8)$
$(1,3,5,2,6),(4,7,10,8,11),(9,12,14,16,13,15)$
$(1,3,6,2,4),(5,7,9,12,8),(10,14,11,15,13,16)$ $C_{5}\cup 2C_{6}$
$(1,2,3,4,5),(6,7,8,9,10,11),(12,13,14,15,16,17)$
$(1,2,3,4,5),(6,7,8,9,10,11),(12,13,14,15,16,17)$
$(4,10,14,16,13),(1,8,6,15,9,17),(2,7,12,3,5,11)$
$(1,10,2,6,15),(3,7,16,14,11,9),(4,8,13,17,5,12)$
$(1,3,6,2,4),(5,7,9,11,8,13),(10,15,17,14,12,16)$
$(1,4,2,5,3),(6,8,10,7,9,13),(11,15,17,14,12,16)$ $3C_{6}$
$(1,2,3,4,5,6),(7,8,9,10,11,12),(13,14,15,16,17,18)$
$(1,2,3,4,5,6),(7,8,9,10,11,12),(13,14,15,16,17,18)$
$(1,5,14,7,3,13),(2,12,18,10,6,16),(4,8,11,17,9,15)$
$(1,4,2,17,10,12),(3,5,8,18,16,13),(6,9,11,15,7,14)$
$(1,3,5,2,4,7),(6,8,10,12,9,11),(13,15,17,14,18,16)$
$(1,3,6,2,5,7),(4,8,10,13,9,12),(11,16,14,17,15,18)$ $4C_{3}$
$(1,2,3),(4,5,6),(7,8,9),(10,11,12)$ $(1,2,3),(4,5,6),(7,8,9),(10,11,12)$
$(1,5,8),(2,4,12),(3,9,10),(6,7,11)$ $(1,5,8),(2,7,12),(3,6,10),(4,9,11)$
$(1,4,7),(2,5,10),(3,8,11),(6,9,12)$ $(1,4,7),(2,5,10),(3,8,11),(6,9,12)$
$3C_{3}\cup C_{4}$ $(1,2,3),(4,5,6),(7,8,9),(10,11,12,13)$
$(1,2,3),(4,5,6),(7,8,9),(10,11,12,13)$
$(1,5,9),(2,4,10),(3,6,11),(7,12,8,13)$
$(1,5,9),(2,4,10),(3,11,13),(6,7,12,8)$
$(1,4,7),(2,5,8),(3,10,12),(6,9,11,13)$
$(1,4,7),(2,5,8),(3,10,12),(6,11,9,13)$ $3C_{3}\cup C_{5}$
$(1,2,3),(4,5,6),(7,8,9),(10,11,12,13,14)$
$(1,2,3),(4,5,6),(7,8,9),(10,11,12,13,14)$
$(2,9,10),(3,6,12),(4,7,14),(1,5,13,8,11)$
$(1,4,12),(2,7,10),(5,9,11),(3,8,14,6,13)$
$(1,4,8),(2,5,7),(3,9,11),(6,13,10,12,14)$
$(1,5,7),(2,4,8),(3,6,9),(10,12,14,11,13)$ $3C_{3}\cup C_{6}$
$(1,2,3),(4,5,6),(7,8,9),(10,11,12,13,14,15)$
$(1,2,3),(4,5,6),(7,8,9),(10,11,12,13,14,15)$
$(1,9,11),(3,5,7),(8,12,15),(2,4,14,6,10,13)$
$(2,4,8),(6,13,15),(10,12,14),(1,9,3,7,5,11)$
$(1,4,7),(2,5,8),(3,6,12),(9,10,14,11,13,15)$
$(1,4,7),(2,5,9),(3,6,14),(8,10,13,11,15,12)$ $5C_{3}$
$(1,2,3),(4,5,6),(7,8,9),(10,11,12),(13,14,15)$
$(1,2,3),(4,5,6),(7,8,9),(10,11,12),(13,14,15)$
$(1,4,7),(2,10,13),(3,6,14),(5,8,11),(9,12,15)$
$(1,4,7),(2,5,8),(3,12,15),(6,10,13),(9,11,14)$
$(1,5,9),(2,4,8),(3,10,15),(6,11,13),(7,12,14)$
$(1,5,9),(2,4,10),(3,6,14),(7,11,15),(8,12,13)$

Table 1: Two distinct packings of three copies of each of 46 small 2-factors

## References

  * [1] P. Adams, D. Bryant, Two-factorisations of complete graphs of orders fifteen and seventeen, Australas. J. Comb., (1)35 (2006), 113–118.
  * [2] M. Aigner, S. Brandt, Embedding arbitrary graphs of maximum degree two, J. London Math. Soc., (2)48 (1993), 39–51.
  * [3] B. Bollobás, S. E. Eldridge, Packings of graphs and applications to computational complexity, J. Combin. Theory Ser. B, 25 (1978), 105–124.
  * [4] D. Burns, S. Schuster, Every $(p,p-2)$ graph is contained in its complement, J. Graph Theory, 1 (1977), 277–279.
  * [5] D. Burns, S. Schuster, Embedding $(n,n-1)$ graphs in their complements, Israel J. Math., 30 (1978), 313–320.
  * [6] C. J. Colbourn, J. H. Dinitz, eds., The CRC Handbook of Combinatorial Designs, Second Edition, CRC Press, Boca Raton, 2006.
  * [7] M. Dean, On Hamilton Cycle Decomposition of 6-regular Circulant Graphs, Graphs Combin., 22 (2006), 331–340.
  * [8] A. Deza, F. Franek, W. Hua, M. Meszka, A. Rosa, Solutions to the Oberwolfach problem for orders $18$ to $40$, J. Comb. Math. Comb. Comput., 74 (2010), 95–102.
  * [9] I. Grzelec, M. Pilśniak, M. Woźniak, A note on uniquely embeddable $2$-factors, Appl. Math. Comput., 468 (2024), 128505.
  * [10] C. Heuberger, On planarity and colorability of circulant graphs, Discrete Math., 268 (2003), 153–169.
  * [11] A. J. W. Hilton, M. Johnson, Some results on the Oberwolfach problem, J. London Math. Soc., (2)64 (2001), 513–522.
  * [12] M. Meszka, R. Nedela, A. Rosa, Circulants and the chromatic index of Steiner triple systems, Math. Slovaca, 56 (2006) 371–378.
  * [13] J. Otfinowska, M. Woźniak, A Note on Uniquely Embeddable Forests, Discuss. Math. Graph Th., 33.1 (2013), 193–201.
  * [14] N. Sauer, J. Spencer, Edge disjoint placement of graphs, J. Combin. Theory Ser. B, 25 (1978), 295–302.
  * [15] H. Wang, N. Sauer, Packing three copies of a tree into a complete graph, European J. Combin., 14 (1993), 137–142.
  * [16] M. Woźniak, A note on uniquely embeddable graphs, Discuss. Math. Graph Th., 18 (1998), 15–21.
  * [17] M. Woźniak, Packing of graphs, Diss. Math., 362 (1997), pp.78.
  * [18] M. Woźniak, Packing of graphs and permutation – a survery, Discrete Math., 276 (2004), 379–391.
  * [19] M. Wozniak, A. P. Wojda, Triple placement of graphs, Graphs Combin., 9 (1993), 85–91.
  * [20] H. P. Yap, Packing of graphs – a survey, Discrete Math., 72 (1988), 395–404.