Decompositions of complete graphs into theta graphs with fewer than ten edges

A theta graph is a graph consisting of three pairwise internally disjoint paths with common end points. Methods for decomposing the complete graph K-nu into theta graphs with fewer than ten edges are given.

Large sets of large sets of Steiner triple systems of order 9

We describe a direct method of partitioning the 840 Steiner triple systems of order 9 into 120 large sets. The method produces partitions in which all of the large sets are isomorphic and we apply the method to each of the two non-isomorphic large sets of STS(9).

Induction in the timed interval calculus

The Timed Interval Calculus, a timed-trace formalism based on set theory, is introduced. It is extended with an induction law and a unit for concatenation, which facilitates the proof of properties over trace histories. The effectiveness of the extended Timed Interval Calculus is demonstrated via a benchmark case study, the mine pump. Specifically, a safety property relating to the operation of a mine shaft is proved, based on an implementation of the mine pump and assumptions about the environment of the mine. (C) 2002 Elsevier Science B.V. All rights reserved.

Decompositions of complete tripartite graphs into triangles with an edge attached

Let K(r, s, t) denote the complete tripartite graph with partite sets of size r, s and t, where r less than or equal to s less than or equal to t. Let D be the graph consisting of a triangle with an edge attached. We show that K(r, s, t) may be decomposed into copies of D if and only if 4 divides rs + st + rt and t less than or equal to 3rs/(r + s).

Balanced critical sets in Latin squares

In this note we first introduce balanced critical sets and near balanced critical sets in Latin squares. Then we prove that there exist balanced critical sets in the back circulant Latin squares of order 3n for n even. Using this result we decompose the back circulant Latin squares of order 3n, n even, into three isotopic and disjoint balanced critical sets each of size 3n. We also find near balanced critical sets in the back circulant Latin squares of order 3n for n odd. Finally, we examine representatives of each main class of Latin squares of order up to six in order to determine which main classes contain balanced or near balanced critical sets.

A census of critical sets in the Latin squares of order at most six

A critical set in a Latin square of order n is a set of entries from the square which can be embedded in precisely one Latin square of order n, Such that 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 all the critical sets of different sizes in the Latin squares of order at most six. We count the number of main and isotopy classes of these critical sets and classify critical sets from the main classes into various strengths. Some observations are made about the relationship between the numbers of classes, particularly in the 6 x 6 case. Finally some examples are given of each type of critical set.

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.