On uniqueness of packing of three copies of 2-factors

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.

26 pages, 12 figures