×

zbMATH — the first resource for mathematics

Minimum coverings of \(K_ n\) with hexagons. (English) Zbl 0879.05056
It is known that the complete graph \(K_n\) can be decomposed into 6-cycles if and only if \(n\) is congruent to 1 or 9 modulo 12. The author completely settles the problem of the minimum number of edges that need to be added to \(K_n\) so that the resulting multigraph can be decomposed into 6-cycles.

MSC:
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C38 Paths and cycles
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite