Packing pentagons into complete graphs: How clumsy can you get?
type: Item
instance of: scholarly article
title: Packing pentagons into complete graphs: How clumsy can you get?
zbMATH Open document ID: 0797.05063
DOI: 10.1016/0012-365X(94)90121-X
author: Štefan Znám
author: Alexander Rosa
published in: Discrete Mathematics
publication date: 1994-10-10T00:00:00Z
review text: 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} \] {}.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 562600
zbMATH Keywords: pentagonal packing
zbMATH Keywords: pentagons
zbMATH Keywords: spectrum
zbMATH Keywords: eulerian graph
zbMATH Keywords: antieulerian graph
MaRDI profile type: Publication
cites work: Large cycles in graphs
cites work: Q5422499
cites work: On the construction of odd cycle systems
cites work: Q5181736
cites work: Q3983106
description: scientific article; zbMATH DE number 562600