Maximum Packings of Complete Graphs with Octagons

Abstract

The edge set of $K_n$ cannot be decomposed into edge-disjoint octagons (or $8$-cycles) when $n\not\equiv 1(\mathrm{mod}16)$. We consider the problem of removing edges from the edge set of $K_n$ so that the remaining graph can be decomposed into edge-disjoint octagons. This paper gives the solution of finding maximum packings of complete graphs with edge-disjoint octagons and the minimum leaves are given.