Search

We prove that an almost $$2$$2-perfect $$6$$6-cycle system of order $$n$$n exists if and only if $$n \equiv 1$$n?1 or $$9\ (mod\ 12)$$9(mod12), and that an almost $$2$$2-perfect maximum packing with $$6$$6-cycles of order $$n$$n exists for all $$n \ge 6$$n?6.

In this paper, we will give intersection numbers for two simple 2-fold (3n, n, 3) group divisible designs. More precisely, we will develop constructions which show that there exists two simple 2-fold (3n, n, 3) group divisible designs which intersect in precisely $${k \in \{0, 1, 2, \ldots, 2n^2\}{\setminus} \{2n^2-1, 2n^2-2, 2n^2-3, 2n^2-5\}}$$ k ? { 0 , 1 , 2 , ? , 2 n 2 } \ { 2 n 2 - 1 , 2 n 2 - 2 , 2 n 2 - 3 , 2 n 2 - 5 } triples for $${n \geq 5}$$ n ? 5 . There are some exceptions for n = 2, 3, 4.

In a simple twofold triple system ( X , B ) , any two distinct triples T 1 , T 2 with | T 1 ∩ T 2 | = 2 form a matched pair. Let F be a pairing of the triples of B into matched pairs (if possible). Let D be the collection of double edges belonging to the matched pairs in F , and let F ∗ be the collection of 4 -cycles obtained by removing the double edges from the matched pairs in F . If the edges belonging to D can be assembled into a collection of 4 -cycles D ∗ , then ( X , F ∗ ∪ D ∗ ) is a twofold 4 -cycle system called a metamorphosis of the twofold triple system ( X , B ) . Previous work (Gionfriddo and Lindner, 2003 [7] ) has shown that the spectrum for twofold triple systems having a metamorphosis into a twofold 4 -cycle system is precisely the set of all n ≡ 0 , 1 , 4 or 9 ( m o d 12 ) , n ≥ 9 . In this paper, we extend this result as follows. We construct for each n ≡ 0 , 1 , 4 or 9 ( m o d 12 ) , n ≠ 9 or 12 , a twofold triple system ( X , B ) with the property that the triples in B can be arranged into three sets of matched pairs F 1 , F 2 , F 3 having metamorphoses into twofold 4 -cycle systems ( X , F 1 ∗ ∪ D 1 ∗ ) , ( X , F 2 ∗ ∪ D 2 ∗ ) , and ( X , F 3 ∗ ∪ D 3 ∗ ) , respectively, with the property that D 1 ∪ D 2 ∪ D 3 = 2 K n . In this case we say that ( X , B ) has a triple metamorphosis. Such a twofold triple system does not exist for n = 9 , and its existence for n = 12 remains an open and apparently a very difficult problem.

In this note, we will give intersection numbers for two simple 2-fold ( 3 n , n , 3 ) group divisible designs (GDD). More precisely, we note that there exists two simple 2-fold ( 3 n , n , 3 ) GDDs which intersect in precisely k ∈ { 0 , 1 , 2 , … , 2 n 2 } \ { 2 n 2 − 1 , 2 n 2 − 2 , 2 n 2 − 3 , 2 n 2 − 5 } triples for n ⩾ 5 . There are some exceptions for n = 3 , 4 .

Squashed 6-cycle systems are introduced as a natural counterpart to 2-perfect 6-cycle systems. The spectrum for the latter has been determined previously in [5]. We determine completely the spectrum for squashed 6-cycle systems, and also for squashed 6-cycle packings.

It is well known that when or , there exists a Steiner triple system (STS) of order n decomposable into triangles (three pairwise intersecting triples whose intersection is empty). A triangle in an STS determines naturally two more triples: the triple of “vertices” , and the triple of “midpoints” . The number of these triples in both cases, that of “vertex” triples (inner) or that of “midpoint triples” (outer), equals one-third of the number of triples in the STS. In this paper, we consider a new problem of trinal decompositions of an STS into triangles. In this problem, one asks for three distinct decompositions of an STS of order n into triangles such that the union of the three collections of inner triples (outer triples, respectively) from the three decompositions form the set of triples of an STS of the same order. These decompositions are called trinal inner and trinal outer decompositions, respectively. We settle the existence question for trinal inner decompositions completely, and for trinal outer decompositions with two possible exceptions.

A bowtie is a closed trail whose graph consists of two 3-cycles with exactly one vertex in common. A 2-fold bowtie system of order n is an edge-disjoint decomposition of 2K n into bowties. A 2-fold bowtie system is said to be 2-perfect provided that every pair of distinct vertices is joined by two paths of length 2. It is said to be extra provided these two paths always have distinct midpoints. The extra property guarantees that the two paths x, a, y and x, b, y between every pair of vertices form a 4-cycle (x, a, y, b), and that the collection of all such 4-cycles is a four-fold 4-cycle system. We show that the spectrum for extra 2-perfect 2-fold bowtie systems is precisely the set of all n ≡ 0 or 1 (mod 3), $${n\,\geqslant\,6}$$ . Additionally, with an obvious definition, we show that the spectrum for extra 2-perfect 2-fold maximum packings of 2K n with bowties is precisely the set of all n ≡ 2 (mod 3), $${n\,\geqslant\,8}$$ .

Let (X, C) be a k-cycle system of order n, with vertex set X (of cardinality n) and collection of k-cycles C. Suppose n=kq+r where r

If the complete graph K n has vertex set X, a maximum packing of K n with 4-cycles, (X, C, L), is an edge-disjoint decomposition of K n into a collection C of 4-cycles so that the unused edges (the set L) is as small a set as possible. Maximum packings of K n with 4-cycles were shown to exist by Schonheim and Bialostocki (Can. Math. Bull. 18:703–708, 1975). An almost parallel class of a maximum packing (X, C, L) of K n with 4-cycles is a largest possible collection of vertex disjoint 4-cycles (so with $${\lfloor/4\rfloor}$$ 4-cycles in it). In this paper, for all orders n, except 9, which does not exist, and possibly 23, 41 and 57, we exhibit a maximum packing of K n with 4-cycles so that the 4-cycles in the packing are resolvable into almost parallel classes, with any remaining 4-cycles being vertex disjoint. [Note: The three missing orders have now been found, and appear in Billington et al. (to appear).]

We give a complete solution of the following two problems: (1)For which (n, x) does there exist a pair of hexagon triple systems of order n having x inside triples in common?(2)For which (n, x) does there exist a pair of hexagon triple systems having x outside triples in common?

A hexagon triple is a graph consisting of three triangles of the form (a, x, b), (b, y, c), and (c,z,a), where a, b, c, x, y, z are distinct. The triangle (a, b, c) is called the inside triangle and the triangles (a, x, b), (b,y,c), and (c, z, a) are called outside triangles. A 3k-fold hexagon triple system of order n is a pair (X, H), where H is an edge-disjoint collection of hexagon triples which partitions the edge set of 3kKn with vertex set X. Note that the outside triangles form a 3k-fold triple system. If the 3k-fold hexagon triple system (X, H) has the additional property that the inside triangles form a k-fold triple system, then (X, H) is said to be perfect. A covering of 3kKn with hexagon triples is a triple (X, H, P) such that: 1. 3kKn has vertex set X. 2. P is a subset of E(λ Kn) with vertex set X for some λ, and 3. H is an edge disjoint partition of E(3kKn)∪ P with hexagon triples. If P is as small as possible (X, H, P) is called a minimum covering of 3kKn with hexagon triples. If the inside triangles of the hexagon triples in H form a minimum covering of kKn with triangles, the covering is said to be perfect. A complete solution for the problem of constructing perfect 3k-fold hexagon triple system and perfect maximum packing of 3kKn with hexagon triples was given recently by the authors l2r. In this work, we give a complete solution of the problem of constructing perfect minimum covering of 3kKn with hexagon triples.