Token-passing algorithms are a well-known way of solving distributed mutual exclusion problems in computer networks. A simple abstraction of the concept of tokens allows the use of elementary constructions in general hypergraphs to show that certain sets of tokens are minimal. This suggests other problems about hypergraphs worthy of exploration. As an application, we introduce a new mutual exclusion problem, the \({Excluded \; Taxpayer \; Problem}\), which requires exponentially many tokens even though it can be solved in linear time by other methods.

A PBD construction for six MOLS of order \(76\) is given.

Two algorithms to compute monotone stabbers for convex polygons are presented. More precisely, given a set of \(m\) convex polygons with \(n\) vertices in total, we want to stab the polygons with an \(x\)-monotone polygonal chain such that each polygon is entered at its leftmost point and exited at its rightmost point. Since such a stabber does not exist in general, we study two related problems. The first problem requests a monotone stabber that stabs as many convex polygons as possible. The second problem is to compute the minimal number of \(x\)-monotone stabbers that are necessary to stab all given convex polygons. We present optimal \(O(m \log m + n)\) algorithms for both problems.

Several algorithms for geometric constructions on the real projective plane are described. These methods also apply to Euclidean plane geometry. The concept of an augmented determining set is fundamental to the algorithms. A backtracking algorithm to find augmented determining sets is described. Algorithms for animating constructions, and an incidence-forcing algorithm are also presented. These algorithms have been implemented on an \(X\)-Windows system.

A tournament design, \({TD}(n, c)\), is a \(c\)-row array of the \(\binom{n}{2}\) pairs of elements from an \(n\)-set such that every element appears at most once in each column and there are no empty cells. An interval balanced tournament design, \(\text{IBTD}(n, c)\), satisfies the added condition that the appearances of each element are equitably distributed amongst the columns of the design. We settle the existence question for all \(\text{IBTD}(n,c)\)s by showing that they can be constructed for all admissible parameters and discuss the application of \(\text{IBTD}\)s to scheduling round robin tournaments fairly with respect to the amount of rest allocated to each participant.

We provide two new upper bounds on the total chromatic number of all hypergraphs and give two conjectures related to both the Total Colouring Conjecture for graphs and the Erdős-Faber-Lovász Conjecture.

The first serious mathematical study of whist tournament designs was carried out in the 1890s by E.H. Moore. In this survey, I shall outline briefly the subsequent work which culminated in the proof of the existence of whist tournaments of all possible orders by Baker, Wilson, and Hanani in the 1970s, and then describe some more recent work, mainly by N.J. Finizio, Y.S. Liaw, and the author, on the construction of cyclic whist tournaments. In particular, triple whist tournaments will be discussed.

A graph \(G\) on \(n\) vertices is \({pancyclic}\) if \(G\) contains cycles of all lengths \(\ell\) for \(3 \leq \ell \leq n\) and \(G\) is \({cycle \; extendable}\) if for every non-hamiltonian cycle \(C \subset G\) there is a cycle \(C’ \subset G\) such that \(V(C) \subset V(C’)\) and \(|V(C’) \setminus V(C)| = 1\). We prove that

1. every \(2\)-connected \(K_{1,3}\)-free graph is pancyclic, if \(G\) is \(P_5\)-free and \(n \geq 6\), if \(G\) is \(P_6\)-free and \(n \geq 10\), or if \(G\) is \(P_7\)-free, deer-free and \(n \geq 14\), and
2. every \(2\)-connected \(K_{1,3}\)-free and \(Z_2\)-free graph on \(n \geq 10\) vertices is cycle extendible using at most two chords of the cycle.

The problem of finding the distance between two graphs is known to be NP-complete. In this paper, we describe a heuristic algorithm that uses simulated annealing to find an upper bound for the distance between two graphs. One of the motivations for developing such an algorithm comes from our interest in finding the diameter of families of non-isomorphic extremal graphs. We tested our algorithm on each family of extremal graphs with up to \(16\) vertices and show that the exact distance was obtained in all cases.

\(Z\)-cyclic whist tournaments for \(q+1\) players, \({Wh}(q+1)\), where \(q\) is a prime, \(q \equiv 3 \pmod{4}\), are quite rare. Solutions for \(q = 3, 7, 11, 19, 23,\) and \(31\) were known in the early to mid 1890’s. Since that time no new such \({Wh}(q +1)\) have appeared.
Here we present \(Z\)-cyclic \({Wh}(q + 1)\) for \(q = 43, 47, 59\). Also presented for the first time is a \(Z\)-cyclic \({Wh}(45)\) and a \(Z\)-cyclic \({Wh}(40)\) that has the three person property. All of these results were obtained via the computer.