Squashing Maximum Packings of $K_n$ With 8-Cycles into Maximum Packings of $K_n$ With 4-Cycles


Charles Curtis Lindner, Giovanni Lo Faro, Mariusz Meszka, Antoinette Tripodi




An 8-cycle is said to be squashed if we identify a pair of opposite vertices and name one of them with the other (and thereby turning the 8-cycle into a pair of 4-cycles with exactly one vertex in common). The resulting pair of 4-cycles is called a bowtie. We say that we have squashed the 8-cycle into a bowtie. Evidently an 8-cycle can be squashed into a bowtie in eight different ways. The object of this paper is the construction, for every $n\geq8$, of a maximum packing of $K_n$ with 8-cycles which can be squashed in a maximum packing of $K_n$ with 4-cycles.