The Intersection Problem for Maximum Pentagon Packings

Abstract

Let $K_n$ be the complete graph on $n$ vertices. Let $I(X)$ denote the set of integers $k$ for which a pair of maximum pentagon packings of graph $X$ exist having $k$ common 5-cycles. Let $J(n)$ denote the set $\{0,1,2,\dots ,P-2,P\}$, where $P$ is the number of 5-cycles in a maximum pentagon packing of $K_n$. This paper shows that $I(K_n)=J(n)$, for all $n\ge 1$.