Search

An H -decomposition of a graph G is a partition P of E ( G ) into blocks, each element of which induces a copy of H . An ( s , p ) -equitable block-coloring of the H -decomposition is a coloring of the blocks in P with exactly s colors such that each vertex u is incident with blocks colored with exactly p colors, the blocks containing u being shared out as evenly as possible among the p color classes. Early results in the literature consider the existence of ( s , p ) -equitable block-colorings of K 3 - and C 4 -decompositions of G ∈ { K v , K v − F } , focusing on finding the value of χ p ′ ( v ) , the smallest s for which such a coloring exists. More recently the structure of such colorings has been considered, defining the color vector V ( E ) = ( c 1 ( E ) , c 2 ( E ) , … , c s ( E ) ) of an ( s , p ) -equitable block-coloring E of G , arranged in non-decreasing order, where c i ( E ) is the number of vertices in G incident with a block of color i . The most interesting cases are where χ p ′ ( v ) > p , finding the range of c 1 ( E ) and of c s ( E ) among all ( s , p ) -equitable block-colorings E of G being the main aim. The largest c 1 can be and the smallest c s can be for C 4 -decompositions of K v − F have been previously found. In this paper the value of the remaining two parameters of most interest are found; namely the smallest c 1 can be and the largest c s can be. The extreme colorings found in the main results follow from another problem addressed in this paper: finding extreme ( s , p ) -equitable edge-colorings of K v . An important facet of the paper is that the powerful proof technique of graph amalgamations is used for the first time to obtain ( s , p ) -equitable block-colorings.

Let G = K ( n 0 , … , n p − 1 ; λ 1 , λ 2 ) be the graph with p parts V 0 , V 1 , … , V p − 1 of n 0 , … , n p − 1 vertices, respectively, where there are λ 1 edges between each pair of vertices from the same part and λ 2 edges between each pair of vertices from distinct parts. A holey hamilton cycle of deficiency V i of G is a hamilton cycle of G − V i for some i satisfying 0 ≤ i ≤ p − 1 . A holey hamiltonian decomposition is a set of holey hamilton cycles whose edges partition E ( G ) . Representing each (holey) hamilton cycle as a color class in an edge-coloring, a (holey) hamiltonian decomposition of G is said to be fair if between each pair of (not necessarily distinct) parts the (permitted) color classes have size within one of each other—so the edges between a pair of parts are shared “evenly” among the (permitted) color classes. Similarly, a (holey) factorization of G is said to be internally fair if within each color class the edges between vertices of distinct parts are shared evenly among all pairs of distinct parts (for which that color class is permitted), and if within each color class the edges joining vertices from the same part are shared evenly among all parts (for which that color class is permitted). In this paper the existence of fair hamiltonian and fair holey hamiltonian decompositions of G are each settled except in a few cases. Simultaneously we settle the existence of internally fair and internally fair holey hamiltonian decompositions of G in a slightly more general setting.

In this paper, necessary and sufficient conditions are found for embedding a maximal partial 3-path design of order n into a 3-path design of specified order. Also solved is the more general problem of finding necessary and sufficient conditions for the embedding of a partial 3-path design of order n into a 3-path design of order k ? n + 2 .

This paper makes progress towards settling the long-standing conjecture that the total chromatic number ? ? of the complete p -partite graph K = K ( r 1 , ? , r p ) is Δ ( K ) + 1 if and only if K ? K r , r and if K has an even number of vertices then Σ v ? V ( K ) ( Δ ( K ) - d K ( v ) ) is at least the number of parts of odd size. Graphs of even order that are fairly close to being regular are the ones for which ? ? ( K ) remains in doubt. In this paper we show that K is of Type 1 if | V ( K ) | is even and r 2 < r 3 (with parts arranged in non-decreasing order of size), thereby improving on the result of Dong and Yap published in 2000. Furthermore, it is shown using this result together with the novel approach of graph amalgamations that all complete multipartite graphs of the form K ( r , r , ? , r , r + 1 ) are of Type 1.

In this paper we consider the existence of ( s , p )-equitable block-colorings of 4-cycle decompositions of K v - F , where F is a 1-factor of K v . In such colorings, the 4-cycles are colored with s colors in such a way that, for each vertex u , the 4-cycles containing u are colored with p colors so that the number of such 4-cycles of each color is within one of the number of such 4-cycles of each of the other p - 1 colors. Of primary interest is settling the values of ? p ' ( v ) and ? ? p ' ( v ) , namely the least and greatest values of s for which there exists such a block-coloring of some 4-cycle decomposition of K v - F . In this paper, several general results are established, both existence and non-existence theorems. These are then used to find, for all possible values of v , the values of ? p ' ( v ) when p ? { 2 , 3 , 4 } and ? ? 2 ' ( v ) , and to provide good upper bounds on ? ? 3 ' ( v ) .

Let K n r ; λ 1 , λ 2 be the r -partite multigraph in which each part has size n , where two vertices in the same part or different parts are joined by exactly λ 1 edges or λ 2 edges, respectively. It is proved that there exists a maximal set of t edge-disjoint Hamilton cycles in K n r ; λ 1 , λ 2 for λ 2 n ⌊ r + 3 4 ⌋ ≤ t ≤ m i n { ⌊ λ 2 n 2 ( r − 1 ) 2 ⌋ , ⌊ λ 1 ( n − 1 ) + λ 2 n ( r − 1 ) 2 ⌋ } , the upper bound being best possible. The results proved make use of the method of amalgamations.

An H-decomposition of G is a partition P of E(G) into blocks, each element of which induces a copy of H. Amalgamations of graphs have proved to be a valuable tool in the construction of H-decompositions. The method can force decompositions to satisfy fairness notions. Here the use of the method is further applied to (s, p)-equitable block-colorings of H-decompostions: a coloring of the blocks using exactly s colors such that each vertex v is incident with blocks colored with exactly p colors, the blocks containing v being shared out as evenly as possible among the p color classes. Recently interest has turned to the color vector \(V(E)=(c_1(E), c_2(E),\) \(\dots , c_s(E))\) of such colorings. Amalgamations are used to construct (s, p)-equitable block-colorings of \(C_4\)-decompositions of \(K_n - F\) and \(K_2\)-decompositions of \(K_{n}\), focusing on one unsolved case with each where \(c_1\) is as small as possible and \(c_2\) is as large as possible.

A k-factor of a graph G is a k-regular spanning subgraph of G. A k-factorization is a partition of E(G) into k-factors. Let K(n, p) be the complete multipartite graph with p parts, each of size n. If $$V_{1},\ldots , V_{p}$$V1,?,Vp are the p parts of V(K(n, p)), then a holeyk-factor of deficiency $$V_{i}$$Vi of K(n, p) is a k-factor of $$K(n,p)-V_{i}$$K(n,p)-Vi for some i satisfying $$1\le i \le p$$1≤i≤p. Hence a holeyk-factorization is a set of holey k-factors whose edges partition E(K(n, p)). Representing each (holey) k-factor as a color class in an edge-coloring, a (holey) k-factorization of K(n, p) is said to be fair if between each pair of parts the color classes have size within one of each other (so the edges are shared "evenly" among the permitted (holey) factors). In this paper the existence of fair 1-factorizations of K(n, p) is completely settled, as is the existence of fair holey 1-factorizations of K(n, p). The latter result can be used to provide a new construction for symmetric quasigroups of order np with holes of size n. Such quasigroups have the additional property that the permitted symbols are shared as evenly as possible among the cells in each $$n \times n$$n×n "box". These quasigroups are in some sense as far from frames produced by direct products as possible.

Necessary and sufficient conditions are given for the existence of a graph decomposition of the Kneser Graph KGn,2 and of the Generalized Kneser Graph GKGn,3,1 into paths of length three.

Necessary and sufficient conditions are given for the existence of a graph decomposition of the Kneser Graph K G n , 2 into paths of length four.

Using the Katona-Kierstead definition of a Hamilton cycle in a uniform hypergraph, we settle the existence of wrapped Hamilton cycle decompositions (WHDs) of the λ -fold complete tripartite graph λ K n , n , n with one possible exception. The existence of large sets of WHDs of λ K n , n , n is also settled for all n ? 0 , 1 or 3 ( mod 4 ) .We also investigate the existence of wrapped Hamilton cycle decompositions of the λ -fold complete 3-uniform tripartite hypergraph λ K n , n , n ( 3 ) which have the additional property that they can themselves be partitioned into WHDs (a result reminiscent of partitioning Steiner Quadruple Systems into BIBDs with block size 4).

A k -factor of a graph G = ( V ( G ) , E ( G ) ) is a k -regular spanning subgraph of G . A k -factorization is a partition of E ( G ) into k -factors. Let K ( n , p ) be the complete multipartite graph with p parts, each of size n . If V 1 , ? , V p are the p parts of V ( K ( n , p ) ) , then a holey ? k -factor of deficiency V i of K ( n , p ) is a k -factor of K ( n , p ) - V i for some i satisfying 1 ? i ? p . Hence a holey k -factorization is a set of holey k -factors whose edges partition E ( K ( n , p ) ) . A holey hamiltonian decomposition is a holey 2-factorization of K ( n , p ) where each holey 2-factor is a connected subgraph of K ( n , p ) - V i for some i satisfying 1 ? i ? p . A (holey) k -factorization of K ( n , p ) is said to be fair if the edges between each pair of parts are shared as evenly as possible among the permitted (holey) factors. In this paper the existence of fair holey hamiltonian decompositions of K ( n , p ) is completely settled. This result simultaneously settles the existence of cycle frames of type n p for cycles of the longest length, being a companion for results in the literature for frames with short cycle length.

A k -cycle system of a multigraph G is an ordered pair ( V , C ) where V is the vertex set of G and C is a set of k -cycles, the edges of which partition the edges of G . A k -cycle system of λ K v is known as a λ -fold k -cycle system of order v . A k -cycle system of λ K v ( V , C ) is said to be enclosed in a k -cycle system of ( λ + m ) K v + u ( V ? U , P ) if C ? P and u , m ? 1 . In this paper the enclosing problem for 5 -cycle systems is settled in the general situation where the three parameters λ , m , and v are allowed to vary freely and u is constrained to the difficult case of adding two vertices. New graph theoretic approaches are introduced to handle this situation developing an avenue of research that is of interest in its own right.

A graph G is said to be even if all vertices of G have even degree. Given a k-edge-coloring of a graph G, for each color i∈Zk={0,1,…,k-1} let G(i) denote the spanning subgraph of G in which the edge-set contains precisely the edges colored i. A k-edge-coloring of G is said to be an even k-edge-coloring if for each color i∈Zk, G(i) is an even graph. A k-edge-coloring of G is said to be evenly-equitable if for each color i∈Zk, G(i) is an even graph, and for each vertex v∈V(G) and for any pair of colors i,j∈Zk, |degG(i)(v)-degG(j)(v)|∈{0,2}. For any pair of vertices {v,w} let mG({v,w}) be the number of edges between v and w in G (we allow v=w, where {v,v} denotes a loop incident with v). A k-edge-coloring of G is said to be balanced if for all pairs of colors i and j and all pairs of vertices v and w (possibly v=w), |mG(i)({v,w})-mG(j)({v,w})|≤1. Hilton proved that each even graph has an evenly-equitable k-edge-coloring for each k∈N. In this paper we extend this result by finding a characterization for graphs that have an evenly-equitable, balanced k-edge-coloring for each k∈N. Correspondingly we find a characterization for even graphs to have an evenly-equitable, balanced 2-edge-coloring. Then we give an instance of how evenly-equitable, balanced edge-colorings can be used to determine if a certain fairness property of factorizations of some regular graphs is satisfied. Finally we indicate how different fairness notions on edge-colorings interact with each other.

Using the Katona–Kierstead (K–K) definition of a Hamilton cycle in a uniform hypergraph, we investigate the existence of wrapped K–K Hamilton cycle decompositions of the complete bipartite 3-uniform hypergraph and their large sets, settling their existence whenever n is prime.

It has long been conjectured that the total chromatic number $$ \chi ^{\prime \prime }(K)$$??(K) of the complete $$p$$p-partite graph $$K = K(r_1, \dots , r_p)$$K=K(r1,?,rp) is $$\Delta (K) + 1$$Δ(K)+1 if and only if both $$K \ne K_{r,r}$$K?Kr,r and $$|V(K)| \equiv $$|V(K)|?0 (mod 2) implies that $$\Sigma _{v \in V(K)}(\Delta (K) - d_K(v))$$Σv?V(K)(Δ(K)-dK(v)) is at least the number of parts of odd size. It is known that $$\chi ^{\prime \prime }(K) \le \Delta (K) + 2$$??(K)≤Δ(K)+2. In this paper, a new approach is introduced to attack the conjecture that makes use of amalgamations of graphs. The power of this approach is demonstrated by settling the conjecture for all complete 5-partite graphs.

Let $G$ be a multipartite multigraph without loops. Then $G$ is said to be internally fair if its edges are shared as evenly as possible among all pairs of its partite sets. An internally fair factorization of $G$ is an edge-decomposition of $G$ into internally fair regular spanning subgraphs. A holey factor of $G$ is a regular subgraph spanning all vertices but one partite set. An internally fair holey factorization is an edge-decomposition of $G$ into internally fair holey factors. In this paper, we settle the existence of internally fair (respectively, internally fair holey) factorizations of the complete equipartite multigraph into factors (respectively, holey factors) with prescribed regularity.

In this paper necessary and sufficient conditions are found for the existence of a $$4$$4-cycle system of a complete graph on $$n$$n vertices with leave a nearly $$2$$2-regular graph (that is, a not necessarily spanning graph in which all vertices have degree 2 except for one of degree greater than 2).

In this paper, we consider group divisible designs with two associate classes, completely settling the existence problem for K 3 -designs of λ 1 K n ∨ λ 2 λ 1 K m when m = 2 and when λ 1 ≥ λ 2 . We also extend a classic result of Colbourn and Rosa on quadratic leaves, finding necessary and sufficient conditions for the existence of a K 3 -decomposition of λ K n − E ( Q ) , where Q is any 2-regular subgraph of K n .

In this paper, two related problems are completely solved, extending two classic results by Colbourn and Rosa. In any partial triple system (V,B) of 2Kn, the neighborhood of a vertex v is the subgraph induced by {{x,y}∣{v,x,y}∈B}. For n≡2 (mod 3) with n≠2, it is shown that for any 2-factor F on n−1 or n−2 vertices, there exists a maximum packing of 2Kn with triples such that F is the neighborhood of some vertex if and only if (n,F)≠(5,C2∪C2), thus extending the corresponding result for the case where n≡0 or 1 (mod 3) by Colbourn and Rosa. This result, along with the companion result of Colbourn and Rosa, leads to a complete characterization of quadratic leaves of λ-fold partial triple systems for all λ≥2, thereby extending the solution where λ=1 by Colbourn and Rosa.

A k-cycle system of a multigraph G is an ordered pair (V, C) where V is the vertex set of G and C is a set of k-cycles, the edges of which partition the edges of G. A k-cycle system of is known as a λ-fold k-cycle system of order V. A k-cycle system of (V, C) is said to be enclosed in a k-cycle system of if and . We settle the difficult enclosing problem for λ-fold 5-cycle systems with u = 1.

A spanning tree of a properly edge-colored complete graph, $K_n$, is rainbow provided that each of its edges receives a distinct color. In 1996, Brualdi and Hollingsworth conjectured that if $K_{2m}$ is properly $(2m-1)$-edge-colored, then the edges of $K_{2m}$ can be partitioned into $m$ rainbow spanning trees except when $m=2$. By means of an explicit, constructive approach, in this paper we construct $\lfloor \sqrt{6m+9}/3 \rfloor$ mutually edge-disjoint rainbow spanning trees for any positive value of $m$. Not only are the rainbow trees produced, but also some structure of each rainbow spanning tree is determined in the process. This improves upon best constructive result to date in the literature which produces exactly three rainbow trees., Comment: 13 pages

In this paper, two results are obtained on a hypergraph embedding problem. The proof technique is itself of interest, being the first time amalgamations have been used to address the embedding of hypergraphs. The first result finds necessary and sufficient conditions for the embedding a hyperedge-colored copy of the complete 3-uniform hypergraph of order $m$, $K_m^3$, into an $r$-factorization of $K_n^3$, providing that $n> 2m+(-1+\sqrt{8m^2-16m-7})/2$. The second result finds necessary and sufficient conditions for an embedding when not only are the colors of the hyperedges of $K_m^3$ given, but also the colors of all the "pieces" of hyperedges on these $m$ vertices are prescribed (the "pieces" of hyperedges are eventually extended to hyperedges of size 3 in $K_n^3$ by adding new vertices to the hyperedges of size 1 and 2 during the embedding process). Both these results make progress towards settling an old question of Cameron on completing partial 1-factorizations of hypergraphs.

Let $K(a^{(p)};\lambda,\mu )$ be a graph with $p$ parts, each part having size $a$, in which the multiplicity of each pair of vertices in the same part (in different parts) is $\lambda$ ($\mu $, respectively). In this paper we consider the following embedding problem: When can a graph decomposition of $K(a^{(p)};\lambda,\mu )$ be extended to a Hamiltonian decomposition of $K(a^{(p+r)};\lambda,\mu )$ for $r>0$? A general result is proved, which is then used to solve the embedding problem for all $r\geq \frac{\lambda}{\mu a}+\frac{p-1}{a-1}$. The problem is also solved when $r$ is as small as possible in two different senses, namely when $r=1$ and when $r=\frac{\lambda}{\mu a}-p+1$.

In this paper, a theorem is proved that generalizes several existing amalgamation results in various ways. The main aim is to disentangle a given edge-colored amalgamated graph so that the result is a graph in which the edges are shared out among the vertices in ways that are fair with respect to several notions of balance (such as between pairs of vertices, degrees of vertices in the both graph and in each color class, etc). The connectivity of color classes is also addressed. Most results in the literature on amalgamations focus on the disentangling of amalgamated complete graphs and complete multipartite graphs. Many such results follow as immediate corollaries to the main result in this paper, which addresses amalgamations of graphs in general, allowing for example the final graph to have multiple edges. A new corollary of the main theorem is the settling of the existence of Hamilton decompositions of the family of graphs $K(a_1,\dots, a_p;\lambda_1, \lambda_2)$; such graphs arose naturally in statistical settings.

A graph G is said to be primitive if it contains no proper factors. In this paper, by using the amalgamation technique, we find sufficient conditions for the existence of a d-regular graph G on n vertices which: 1.has a Hamilton decomposition, and 2.has a complement in K"m^p that is primitive. These general results are then used to consider the bounds on m when p and d are fixed. The case p=6 for all m and d is considered in more detail.

The existence of group divisible designs with two associate classes has been studied for over 50 years. Probably the most difficult cases to solve are those in which the number of groups is less than the size of the blocks. Recently, such an existence problem was solved in the case where the groups have the same size and the blocks have size 3. In this paper, we continue to focus on blocks of size 3, solving the existence problem when the required designs are gregarious (each block intersects each group). These designs are tight to construct in the sense that they satisfy equality in one of the bounds required for GDDs to exist.

In this paper we solve the problem of enclosing a λ-fold 4-cycle system of order v into a (λ + m)-fold 4-cycle system of order v + u for all m > 0 and u ≥ 1. An ingredient is constructed that is of interest on its own right, namely the problem of finding equitable partial 4-cycle systems of λ Kv. This supplementary solution builds on a result of Raines and Staniszlo.

A hexagon triple is the graph consisting of the three triangles (triples) {a,b,c},{c,d,e}, and {e,f,a}, where a,b,c,d,e, and f are distinct. The triple {a,c,e} is called an inside triple. A hexagon triple system of order n is a pair (X,H) where H is a collection of edge disjoint hexagon triples which partitions the edge set of Kn with vertex set X. The inside triples form a partial Steiner triple system. We show that any Steiner triple system of order n can be embedded in the inside triples of a hexagon triple system of order approximately 3n.

Recently, Lindner showed that every partial 4-cycle system of order n and index 1 could be embedded in a 4-cycle system of order ν and index 1 with v ≤ 2n + 15. While the technique he used does not immediately extend to any higher index, here we develop his ideas to show that every partial 4-cycle system of order n and index λ can be embedded in a 4-cycle system of order v and index λ for all λ-admissible $$\nu \geq 8 \lceil n /4 \rceil + 7, \nu \ne 8 \lceil n /4 \rceil + 8$$. This improves on the best known bounds of v = 4n and v = 8n + 1 when λ > 1 is even and odd respectively.

The complete multipartite graph Kn(m) with n parts of size m is shown to have a decomposition into n-cycles in such a way that each cycle meets each part of Kn(m); that is, each cycle is said to be gregarious. Furthermore, gregarious decompositions are given which are also resolvable.

A set S of edge-disjoint hamilton cycles in a graph T is said to be maximal if the hamilton cycles in S form a subgraph of T such that T-E(S) has no hamilton cycle. The spectrum of a graph T is the set of integers m such that T contains a maximal set of m edge-disjoint hamilton cycles. This spectrum has previously been determined for all complete graphs, all complete bipartite graphs, and many complete multipartite graphs. One of the outstanding problems is to find the spectrum for the graphs formed by removing the edges of a 1-factor, F, from a complete graph, K"2"p. In this paper we completely solve this problem, giving two substantially different proofs. One proof uses amalgamations, and is of interest in its own right because it is the first example of an amalgamation where vertices from different parts are amalgamated. The other is a neat direct proof.

Let @l"1K"a denote the graph on a vertices with @l"1 edges between every pair of vertices. Take p copies of this graph @l"1K"a, and join each pair of vertices in different copies with @l"2 edges. The resulting graph is denoted by K(a,p;@l"1,@l"2), a graph that was of particular interest to Bose and Shimamoto in their study of group divisible designs with two associate classes. The existence of z-cycle decompositions of this graph have been found when z@?{3,4}. In this paper we consider resolvable decompositions, finding necessary and sufficient conditions for a 4-cycle factorization of K(a,p;@l"1,@l"2) (when @l"1 is even) or of K(a,p;@l"1,@l"2) minus a 1-factor (when @l"1 is odd) whenever a is even.

For any two 2-regular spanning subgraphs G and H of the complete multipartite graph K, necessary and sufficient conditions are found for the existence of a 2-factorization of K in which 1. the first and second 2-factors are isomorphic to G and H respectively, and 2. each other 2-factor is a hamilton cycle in the case where K has an odd number of vertices.

A maximum packing of any ?-fold complete multipartite graph (where there are ? edges between any two vertices in different parts) with edge-disjoint 4-cycles is obtained and the size of each minimum leave is given. Moreover, when ?=2, maximum 4-cycle packings are found for all possible leaves.

We introduce a class of “chromatic” graph parameters that include the chromatic number, the circular chromatic number, the fractional chromatic number, and an uncountable horde of others. We prove some basic results about this class and pose some problems.

In this paper, we completely solve the embedding problem for (3,2)-path coverings of complete graphs.

In this paper we define an infinite family of varieties of algebraic quasigroups, where for m⩾3 the variety Vm satisfies a particular set of defining identities Im. It is shown that the finite members of Vm are precisely the quasigroups that can be obtained via a standard construction from certain decompositions of a complete graph into closed trails of lengths that each divide m. The result is presented from a graph theoretical perspective.

The bound for embedding a partial 2k-cycle system of order n, k ≥ 3, is dramatically improved from kn + d(k)√n, where d(k) is a function of k, to kn+c(k), where c(k) is a quadratic function of k. The best known bound for 4-cycles remains 2n + 10√n.

A balanced sampling plan excluding contiguous units (or BSEC for short) was first introduced by Hedayat, Rao and Stufken in 1988. These designs can be used for survey sampling when the units are arranged in one-dimensional ordering and the contiguous units in this ordering provide similar information. In this paper, we generalize the concept of a BSEC to the two-dimensional situation and give constructions of two-dimensional BSECs with block size 3. The existence problem is completely solved in the case where λ = 1.

A fair hamilton decomposition of the complete multipartite graph G is a set of hamilton cycles in G whose edges partition the edges of G in such a way that, for each pair of parts and for each pair of hamilton cycles H1 and H2, the difference in the number of edges in H1 and H2 joining vertices in these two parts is at most one. In this paper we completely settle the existence of such decompositions. The proof is constructive, using the method of amalgamations (graph homomorphisms).

In this paper necessary and sufficient conditions are found for an edge-colored graph H to be the homomorphic image of a 2-factorization of a complete multipartite graph G in which each 2-factor of G has the same number of components as its corresponding color class in H. This result is used to completely solve the problem of finding hamilton decompositions of Ka,b − E(U) for any 2-factor U of Ka,b. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 460–467, 2001

In this paper we completely solve the problem of finding a maximum packing of any complete multipartite graph with edge-disjoint 4-cycles, and the minimum leaves are explicitly given.

In 1983, necessary and sucient conditions were obtained for an incomplete idempotent latin square of order n to be embedded in an idempotent latin square of order 2n, providing n>16. In this paper we consider the case where n616. c 2000 Elsevier Science B.V. All rights reserved.

In this article, we prove that there exists a maximal set of m Hamilton cycles in K-n,K-n if and only if n/4 < m less than or equal to n/2. (C) 2000 John Wiley & Sons, Inc.

In this paper we find necessary and sufficient conditions for the existence of a group divisible design GDD(n, m) of index (λ1, λ2) in whichn=2 orm=2, thereby completing the solution of the existence problem for alln,m,λ1, andλ2. In the process, necessary and sufficient conditions are found for the existence of anx-regular partial triple system whose complement inλKnhas a 1-factorization.

In this paper, we show that any partial extended triple system (partial totally symmetric quasigroup) of order n can be embedded in a totally symmetric quasigroup of order v , v ⩾ 4 n + 6, v  2 (mod 4). This bound can be lowered to 4 n + 2 in most cases.

A critical set C of order n is a partial latin square of order n which is uniquely completable to a latin square, and omitting any entry of the partial latin square destroys this property. The size s(C) of a critical set C is the number of filled cells in the partial latin square. The size of a minimum critical set of order n is s(n). It is likely that s(n) is approximately 1 4 n 2 , though to date the best-known lower bound is that s(n) ⩾ n + 1. In this paper, we obtain some conditions on C which force s(C) ⩾ [ (n − 1) 2 ] 2 . For n > 20, this is used to show that in general s(n) ⩾ [ (7n − 3) 6 ] , thus improving the best-known result.