Maximum Packings of Bowtie Designs

Abstract

A bowtie is a simple graph on $5$ vertices with $6$ edges, which consists of a pair of edge-disjoint triangles having one common vertex. A bowtie design of order $n$ is an edge-disjoint decomposition of the complete undirected graph $K_n$ into bowties. These exist if and only if $n\equiv 1$ or $9(\mathrm{mod}12)$. For any $n\ge 5$, a maximum packing of the complete undirected graph $K_n$ with bowties is a collection of edge-disjoint bowties picked from $K_n$, of maximum cardinality. The unused edges of $K_n$ in this decomposition, if any, form the leave of the packing, which is necessarily a set with cardinality as small as possible. In this paper, a maximum packing of $K_n$ with bowties is found, for all $n\ge 5$ and for all possible leaves.