ACTA MATHEMATICA UNIVERSITATIS COMENIANAE

ACTA MATHEMATICA UNIVERSITATIS COMENIANAE

Vol. 65, 2 (1996)
pp. 215-227

MAXIMAL PENTAGONAL PACKINGS
A. CERNY, P. HORAK, A. ROSA and S. ZNAM

Abstract. For $n\geq 5$, a pentagonal packing of size $t$ is a set of $t$ edge-disjoint pentagons (cycles of length five) in the complete graph $K_n$. A pentagonal packing $\Cal P$ is maximal, denoted as $MPP(n)$, if the complement of the union of all pentagons from $\Cal P$ is pentagon-free. The spectrum $S^(5)(n)$ for maximal pentagonal packings is the set of all possible sizes of $MPP(n)$. We formulate a conjecture on the structure of the spectrum $S^(5)(n)$, and prove the conjecture for all $n=40k+3$, $% k\geq 2$.

AMS subject classification.
Keywords.

Download: Adobe PDF

Compressed Postscript

Acta Mathematica Universitatis Comenianae
Institute of Applied Mathematics
Faculty of Mathematics, Physics and Informatics
Comenius University
842 48 Bratislava, Slovak Republic
Telephone: + 421-2-60295111 Fax: + 421-2-65425882
e-Mail: amuc@fmph.uniba.sk Internet: www.iam.fmph.uniba.sk/amuc