Packing pentagons into complete graphs: How clumsy can you get? (Q1322192): Difference between revisions

A pentagonal packing PP\((n;t)\) is a family of \(t\) edge-disjoint pentagons \(C_ 5\) in the complete graph \(K_ n\). A pentagonal packing is maximal if the complement of the union of its pentogons is pentagon-free. The spectrum \(S^{(5)}(n)\) is the set of all numbers \(t\) such that there exist a maximal packing PP\((n;t)\). The authors establish the values of \[ m^{(5)}(n)=\min S^{(5)}(n)\qquad\text{and}\qquad M^{(5)}(n)=\max S^{(5)}(n). \] In Section 3, the authors determine the maximum number of edges in graphs without pentagons satisfying various additional conditions. E.g., the maximal size of an eulerian graph with \(n\) vertices without pentagons, \(E(n)\), and the maximal size of an antieulerian graph with \(n\) vertices without pentagons, \(A(n)\), are established. These results are then used in Section 4 in the proof of the main result of this paper: let \(\Delta_ n=\lceil(n(n-1)/2-E(n))/5\rceil\) if \(n\) is odd, and \(\Delta_ n=\lceil(n(n-1)/2-A(n))/5\rceil\) if \(n\) is even. If \(n\geq 11\) then \[ m^{(5)}(n)= \begin{cases}\Delta_ n+2 \quad &\text{if }n\equiv 4,8 \pmod {20},\\ \Delta_ n+1 &\text{if }n\equiv 13,14,15,17,18 \pmod {20}, \\ \Delta_ n &\text{otherwise}.\end{cases} \] {}.