Decomposing complete tripartite graphs into cycles of lengths 3 and 4

Necessary and sufficient conditions are given for the edge-disjoint decomposition of a complete tripartite graph K-r,K-s,K-t into exactly alpha 3-cycles and beta 4-cycles. (C) 1999 Elsevier Science B.V. All rights reserved.

The line structure of balanced ternary designs with block size three, index three and rho(2) = 1, 2

In this paper necessary and sufficient conditions for a vector to be the fine structure of a balanced ternary design with block size 3, index 3 and rho(2) = 1 and 2 are determined with one unresolved case.

Proportionally balanced designs: Some further results and general constructions

Proportionally balanced designs were introduced by Gray and Matters in response to a need for the allocation of markers of the Queensland Core Skills Test to have a certain property. Put simply, markers were allocated to pairs of units in proportions that reflected the relative numbers of markers allocated in total to each unit. In this paper, the first author extends the theoretical results relating to such designs and provides further instances, and two general constructions, in the case that the design comprises blocks of precisely two sizes.

Smallest weak and smallest totally weak critical sets in the latin squares of order at most seven

A critical set in a latin square of order n is a set of entries in a latin square which can be embedded in precisely one latin square of order n. Also, if any element of the critical set is deleted, the remaining set can be embedded in more than one latin square of order n. In this paper we find smallest weak and smallest totally weak critical sets for all the latin squares of orders six and seven. Moreover, we computationally prove that there is no (totally) weak critical set in the back circulant latin square of order five and we find a totally weak critical set of size seven in the other main class of latin squares of order five.

On the intersection problem for 1-factorizations and near 1-factorizations of K-v

The number of 1-factors (near 1-factors) that mu 1-factorizations (near 1-factorizations) of the complete graph K-v, v even (v odd), can have in common, is studied. The problem is completely settled for mu = 2 and mu = 3.

Thue's theorem and the diophantine equation x2 - Dy2 = ±N

A constructive version of a theorem of Thue is used to provide representations of certain integers as x(2) - Dy-2, where D = 2, 3, 5, 6, 7.

Factorizations of and by powers of complete graphs

Let K-k(d) denote the Cartesian product of d copies of the complete graph K-k. We prove necessary and sufficient conditions for the existence of a K-k(r)-factorization of K-pn(s), where p is prime and k > 1, n, r and s are positive integers. (C) 2002 Elsevier Science B.V. All rights reserved.

Existence of multiple solutions for second-order discrete boundary value problems

We give conditions on f involving pairs of discrete lower and discrete upper solutions which lead to the existence of at least three solutions of the discrete two-point boundary value problem yk+1 - 2yk + yk-1 + f (k, yk, vk) = 0, for k = 1,..., n - 1, y0 = 0 = yn,, where f is continuous and vk = yk - yk-1, for k = 1,..., n. In the special case f (k, t, p) = f (t) greater than or equal to 0, we give growth conditions on f and apply our general result to show the existence of three positive solutions. We give an example showing this latter result is sharp. Our results extend those of Avery and Peterson and are in the spirit of our results for the continuous analogue. (C) 2002 Elsevier Science Ltd. All rights reserved.

Further decompositions of complete tripartite graphs into 5-cycles

Let K(r,s,t) denote the complete tripartite graph with partite sets of sizes r, s and t, where r less than or equal to s less than or equal to t. Necessary and sufficient conditions are given for decomposability of K(r, s, t) into 5-cycles whenever r, s and t are all even. This extends work done by Mahmoodian and Mirza-khani (Decomposition of complete tripartite graphs into 5-cycles, in: Combinatorics Advances, Kluwer Academic Publishers, Netherlands, 1995, pp. 235-241) and Cavenagh and Billington. (C) 2002 Elsevier Science B.V. All rights reserved.

Factorizations of the complete graph into C-5-factors and 1-factors

In this paper, we show that K-10n can be factored into alpha C-5-factors and beta 1-factors for all non-negative integers alpha and beta satisfying 2alpha + beta = 10(n) - 1.

Breadth-first search and the Andrews-Curtis conjecture

Andrews and Curtis conjectured in 1965 that every balanced presentation of the trivial group can be transformed into a standard presentation by a finite sequence of elementary transformations. Recent computational work by Miasnikov and Myasnikov on this problem has been based on genetic algorithms. We show that a computational attack based on a breadth-first search of the tree of equivalent presentations is also viable, and seems to outperform that based on genetic algorithms. It allows us to extract shorter proofs (in some cases, provably shortest) and to consider the length thirteen case for two generators. We prove that, up to equivalence, there is a unique minimum potential counterexample.

Common multiples of complete graphs and a 4-cycle

A graph G is a common multiple of two graphs H-1 and H-2 if there exists a decomposition of G into edge-disjoint copies of H-1 and also a decomposition of G into edge-disjoint copies of H-2. In this paper, we consider the case where H-1 is the 4-cycle C-4 and H-2 is the complete graph with n vertices K-n. We determine, for all positive integers n, the set of integers q for which there exists a common multiple of C-4 and K-n having precisely q edges. (C) 2003 Elsevier B.V. All rights reserved.