We consider a pair of MOLS (mutually orthogonal Latin squares) having holes, corresponding to missing sub-MOLS, which are disjoint and spanning. If the two squares are mutual transposes, we say that we have SOLS (self-orthogonal Latin squares) with holes. It is shown that a pair of SOLS with $n$ holes of size \(h \geq 2\) exist if and only if \(n \geq 4\) and it is also shown that a pair of SOLS with \(n\) holes of size \(2\) and one hole of size \(3\) exist for all \(n \geq 4, n \neq 13, 15\).

As an application, we prove a result concerning intersection numbers of transversal designs with four groups.

We survey here results and problems from the reconstruction theory of evolutionary trees, which involve enumeration and inversion.

It is proved in this paper that for any integer \(n \geq 100\), a \((v,n)\)-IODLS (incomplete orthogonal diagonal Latin squares) exists if and only if \(v \geq 3n+2\). Results for \(n=2\) are also mentioned.

In this note, we construct a \((39, \{5,6,7\}, 1)\)-PBD. Thus we have a finite generating set for the PBD-closed set \(N_5^{\infty}\) with at most three inessential elements, where \(N_5^\infty = \{1\} \cup \{v: v \geq 5\}\).

In this paper, we prove the NP-hardness of the bottleneck graph bipartition problem and study the complexity status of possible approximation algorithms for some related problems.

This paper concerns neighbour designs in which the elements of each block are arranged on the circumference of a circle. Most of the designs considered comprise a general class of balanced Ouchterlony neighbour designs, which include the balanced circuit designs of Rosa and Huang \([30]\), the neighbour designs of Rees \([29]\), and the more general neighbour designs of Hwang and Lin \([13]\). The class of Rees neighbour designs includes schemes given in 1892 by Lucas \([22]\) for round dances. Isomorphism, species, and adjugate set are defined for balanced Ouchterlony neighbour designs, and some seemingly new methods of constructing such designs are presented. A new class of quasi Rees neighbour designs is defined to cover a situation where Rees neighbour designs cannot exist but where a next best thing may be needed by experimental scientists. Even-handed quasi Rees neighbour designs and even-handed balanced Ouchterlony neighbour designs are defined too, the latter being closely related to serially balanced sequences. This paper does not provide a complete survey of known results, but aims to give the flavour of the subject and to indicate many openings for further research.

A dependence system on a set \(S\) is defined by an operator \(f\), a function on the power set of \(S\) which is extensive (\(A\) is included in \(f(A)\)) and monotone (if \(A\) is included in \(B\), then \(f(A)\) is included in \(f(B)\)). In this paper, the structure of the set \(F(S)\) of all dependence systems on a given set \(S\) is studied. The partially ordered set of operators (\(f < g\) if for every set \(A\), \(f(A)\) is included in \(g(A)\)) is a bounded, complete, completely distributive, atomic, and dual atomic lattice with an involution. It is shown that every operator is a join of transitive operators (usually called closure operators, operators which are idempotent \(ff = f\)). The study of the class of transitive operators that join-generate all operators makes it possible to express \(F(n)\) (the cardinality of the set \(F(S)\) of all operators on a set \(S\) with \(n\) elements) by the Dedekind number \(D(n)\). The formula has interesting consequences for dependence system theory.

Let \(p(k)\) (\(q(k)\)) be the smallest number such that in the projective plane, every simple arrangement of \(n \geq p(k)\) (\( \geq q(k)\)) straight lines (pseudolines) contains \(k\) lines which determine a \(k\)-gonal region. The values \(p(6) = q(6) = 9\) are determined and the existence of \(q(k) (\geq p(k))\) is proved.

We introduce a complex version of Golay sequences and show how these may be applied to obtain new Hadamard matrices and complex Hadamard matrices. We also show how to modify the Goethals-Seidel array so that it can be used with complex sequences.

In this paper, we improve the best known algorithm on symmetric equivalence of Hadamard matrices by considering the eigenvalues of symmetric Hadamard matrices. As a byproduct, the eigenvalues of skew Hadamard matrices are also discussed.

The spectrum for \(k\)-perfect \(3k\)-cycle systems is considered here for arbitrary \(k \not\equiv 0 \pmod{3}\). Previously, the spectrum when \(k = 2\) was dealt with by Lindner, Phelps, and Rodger, and that for \(k = 3\) by the current authors. Here, when \(k \equiv 1\) or \(5 \pmod{6}\) and \(6k + 1\) is prime, we show that the spectrum for \(k\)-perfect \(3k\)-cycle systems includes all positive integers congruent to \(1 \pmod{6k}\) (except possibly the isolated case \(12k + 1\)). We also complete the spectrum for \(k = 4\) and \(5\) (except possibly for one isolated case when \(k = 5\)), and deal with other specific small values of \(k\).

An efficient dominating set \(S\) for a graph \(G\) is a set of vertices such that every vertex in \(G\) is in the closed neighborhood of exactly one vertex in \(S\). If \(G\) is connected and has no vertices of degree one, then \(G\) has a spanning tree which has an efficient dominating set. An \(O(n)\) algorithm for finding such a spanning tree and its efficient dominating set is given.

Numbers similar to the van der Waerden numbers \(w(n)\) are studied, where the class of arithmetic progressions is replaced by certain larger classes. If \(\mathcal{A}’\) is such a larger class, we define \(w'(n)\) to be the least positive integer such that every \(2\)-coloring of \(\{1, 2, \ldots, w'(n)\}\) will contain a monochromatic member of \(\mathcal{A}’\). We consider sequences of positive integers \(\{x_1, \ldots, x_n\}\) which satisfy \(x_i = a_i x_{i-1} + b_i x_{i-2}\) for \(i = 3, \ldots, n\) with various restrictions placed on the \(a_i\) and \(b_i\). Upper bounds are given for the corresponding functions \(w'(n)\). Further, it is shown that the existence of somewhat stronger bounds on \(w'(n)\) would imply certain bounds for \(w(n)\).

For any graph \(G\), and all \(s = 2^k\), we show there is a partition of the vertex set of \(G\) into \(s\) sets \(U_1, \ldots, U_s\), so that both:
\(e(G[U_i]) \leq \frac{e(G)}{s^2} + \sqrt{\frac{e(G)}{s}}, \quad \text{for } i = 1, \ldots, s\) and \(\sum\limits_{i=1}^s e(G[U_i]) \leq \frac{e(G)}{s}.\)

The basic interpolation theorem states that if graph \(G\) contains spanning trees having \(m\) and \(n\) leaves, with \(m < n\), then for each integer \(k\) such that \(m < k < n\), \(G\) contains a spanning tree having \(k\) leaves. Various generalizations and related topics will be discussed.

We find the set of integers \(v\) for which \(\lambda K_v\) may be decomposed into sets of four triples forming Pasch configurations, for all \(\lambda\). We also remove the remaining exceptional values of \(v\) for decomposing \(K_v\) into sets of other four-triple configurations.

In this paper, we consider some combinatorial structures called balanced arrays (\(B\)-arrays) with a finite number of elements, and we derive some necessary conditions in the form of inequalities for the existence of these arrays. The results obtained here make use of the H\”{o}lder Inequality.

We present efficient algorithms for computing the matching polynomial and chromatic polynomial of a series-parallel graph in \(O(n^{3})\) and \(O(n^2)\) time respectively. Our algorithm for computing the matching polynomial generalizes and improves the result in \([13]\) from \(O(n^3 \log n)\) time for trees and the chromatic polynomial algorithm improves the result in \([18]\) from \(O(n^4)\) time. The salient features of our results are the following:
Our techniques for computing the graph polynomials can be applied to certain other graph polynomials and other classes of graphs as well. Furthermore, our algorithms can also be parallelized into NC algorithms.

Given positive integers \(p\) and \(q\), a \((p, q)\)-colouring of a graph \(G\) is a mapping \(\theta: V(G) \rightarrow \{1, 2, \ldots, q\}\) such that \(\theta(u) \neq \theta(v)\) for all distinct vertices \(u, v\) in \(G\) whose distance \(d(u, v) \leq p\). The \(p\)th order chromatic number \(\chi^{(p)}(G)\) of \(G\) is the minimum value of \(q\) such that \(G\) admits a \((p, q)\)-colouring. \(G\) is said to be \((p, q)\)-maximally critical if \(\chi^{(p)}(G) = q\) and \(\chi^{(p)}(G + e) > q\) for each edge \(e\) not in \(G\).
In this paper, we study the structure of \((2, q)\)-maximally critical graphs. Some necessary or sufficient conditions for a graph to be \((2, q)\)-maximally critical are obtained. Let \(G\) be a \((2, q)\)-maximally critical graph with colour classes \(V_1, V_2, \ldots, V_q\). We show that if \(|V_1| = |V_2| = \cdots = |V_k| = 1\) and \(|V_{k+1}| = \cdots = |V_q| = h \geq 1\) for some \(k\), where \(1 \leq k \leq q-1\), then \(h \leq h^*\), where

\[h^* = \max \left\{k, \min\{q – 1, 2(q – 1 – k)\}\right\}.\]

Furthermore, for each \(h\) with \(1 \leq h \leq h^*\), we are able to construct a \((2, q)\)-maximally critical connected graph with colour classes \(V_1, V_2, \ldots, V_q\) such that \(|V_1| = |V_2| = \cdots = |V_k| = 1\) and \(|V_{k+1}| = \cdots = |V_q| = h\).