×

Nesting and almost resolvability of pentagon systems. (English) Zbl 0718.05011

A pentagon system of order n is a partition of the edges of \(K_ n\) into 5-cycles: and exists if and only if \(n\equiv 1, 5\) (mod 10) [A. Rosa, Casopis Pest. Mat. 91, 53-63 (1966; Zbl 0151.335)]. A pentagon system of order n is nested if there is a mapping \(\rho\) from \({\mathbb{P}}\) (the set of 5-cycles in the system) to the vertices of \(K_ n\) so that \(\{\rho(P)a, \rho(P)b, \rho(P)c, \rho(P)d, \rho(P)e:\;P=(a,b,c,d,e)\in {\mathbb{P}}\}=E(K_ n).\) For such a nested system it is necessary that \(n\equiv 1(mod 10)\) and it is shown here that if \(n\not\in \{111, 201, 221, 231, 261, 301, 381, 511, 581, 591, 621\},\) then the system exists. In the cases when \(n\equiv 5 (mod 10)\) such systems are impossible but it is shown that if two parallel classes of 5-cycles are deleted from \(K_ n\), then, provided \(n\not\in \{15, 25\},\) a nested pentagon system on the remaining graph exists. It is also shown that a nested pentagon system on the graph \(2K_ n\), \(n\geq 6\), exists if and only if \(n\equiv 0,1 (mod 5),\quad n\not\in \{10, 15, 30\}.\) Finally, the authors consider the existence of nested pentagon systems on \(2K_ n\), \(n\equiv 1 (mod 5),\) which are almost resolvable; that is, in which the 5-cycles can be partitioned into partial parallel classes each consisting of (n-1)/5 5- cycles. These are shown to exist for all admissible n except \(n\in \{26, 201, 221, 231, 261, 581, 591, 621\}\).

MSC:

05B07 Triple systems
05C35 Extremal problems in graph theory
05B30 Other designs, configurations
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Citations:

Zbl 0151.335
Full Text: DOI

References:

[1] Brayton, R. K.; Coppersmith, D.; Hoffman, A. J., Self-orthogonal latin squares of all orders n ≠ 2, 3, or 6, Bull. Amer. Math. Soc., 80, 116-118 (1974) · Zbl 0277.05011
[2] Colbourn, C. J.; Colbourn, M. J., Nested triple systems, Ars Combinatoria, 16, 27-34 (1983) · Zbl 0538.05007
[3] Hanani, H., On resolvable balanced incomplete block designs, J. Comb. Theory, 17, 275-289 (1974) · Zbl 0305.05010
[4] Hoffman, D. G.; Lindner, C. C.; Mullin, R. C., A few more BIBD’s with \(k = 6\) and λ = 1, Annals of Discrete Math., 34, 379-384 (1987) · Zbl 0647.05009
[5] Lindner, C. C., How to nest a Steiner triple system, Invited Lectures for the International Conference on Graphs, Steiner Systems, and their Applications (September 12-17, 1986), Universita di Catania: Universita di Catania Catania, Sicily, (to appear)
[6] Lindner, C. C.; Rodger, C. A., The spectrum of nested Steiner triple systems of order 3 (mod 6), Ars Combinatoria, 23, 75-80 (1987) · Zbl 0621.05006
[7] Lindner, C. C.; Stinson, D. R., The spectrum for the conjugate invariant subgroups of perpendicular arrays, Ars Combinatoria, 18, 51-60 (1983) · Zbl 0557.05015
[8] Lindner, C. C.; Stinson, D. R., Steiner pentagon systems, Discr. Math., 52, 67-74 (1984) · Zbl 0549.05010
[9] Stinson, D. R., The spectrum of skew Room squares, J. Aust. Math. Soc. A, 31, 475-480 (1981) · Zbl 0491.05014
[10] Stinson, D. R., The spectrum of nested Steiner triple systems, Graphs and Combinatorics, 1, 189-191 (1985) · Zbl 0583.05015
[11] Stinson, D. R., On the existence of skew Room frames of type \(2^n\), Ars Combinatoria, 24, 115-128 (1987) · Zbl 0641.05009
[12] D.R. Stinson, University of Manitoba, private communication.; D.R. Stinson, University of Manitoba, private communication.
[13] Rosa, A., On the cyclic decomposition of the complete graph into polygons with an odd number of edges, Casop. Pestov. Mat., 19, 53-63 (1966), (in Slovak) · Zbl 0151.33501
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.