Suppose that one is given \(v\) elements, and wishes to form a design that covers all \(t\)-sets from these elements exactly once. The design is to obey the further restriction that the longest block in the design has \(k\) elements in it; furthermore, we wish the design to contain as few blocks as possible.

The number of blocks in such a minimal design is denoted by the symbol \(\text{g}^{(\text{k})}(1,t;v)\); determination of this number is closely connected with the behaviour of Steiner Systems. Recently, much progress has been made in two important cases, namely, when \(t = 2\) (pairwise balanced designs) and \(t = 3\) (designs with balance on triples). This survey paper presents the subject from its inception up to current results.

Recent examples of perfect 1-factorizations arising from dicyclic groups have led to the question of whether or not dicyclic groups have symmetric sequencings. For every positive integer \(n\geq2\), there is a dicyclic group of order \(4n\). It is known that if \(n \geq 3\) is odd, then the dicyclic group of order \(4n\) has a symmetric sequencing. In this paper, a new proof is given for the odd case; a consequence being that in this situation sequencings abound. A generalization of the original proof is exploited to show that if \(n\geq 4\) is even and is not twice an odd number, then the dicyclic group of order \(4n\) has a symmetric sequencing.

Let \(L\) be an \(n \times m\) Latin rectangle on a set of \(v\) symbols with the property that each symbol occurs in precisely \(r\) cells of \(L\). Then \(L\) is said to have the row-column intersection property if each row and column of \(L\) have precisely \(r\) symbols in common. It is shown here that the trivial necessary conditions

1. \(rv = mn\) and
2. \(r \leq \min\{m,n\}\)

are sufficient to guarantee the existence of such a Latin rectangle.

For positive integers \(d\) and \(m\), let \(\text{P}_{\text{d,m}}(\text{G})\) denote the property that between each pair of vertices of the graph \(G\), there are m vertex disjoint (except for the endvertices) paths each of length at most \(d\). Minimal conditions involving various combinations of the connectivity, minimal degree, edge density, and size of a graph \(G\) to insure that \(\text{P}_{\text{d,m}}(\text{G})\) is satisfied are investigated. For example, if a graph \(G\) of order n has connectivity exceeding \((\text{n-m})/\text{d + m} – 1\), then \(\text{P}_{\text{d,m}}(\text{G})\) is satisfied. This result is the best possible in that there is a graph which has connectivity \((\text{n-m})/\text{d + m} – 1\) that does not satisfy \(\text{P}_{\text{d,m}}(\text{G})\). Also, if an \(m\)-connected graph \(G\) of order \(n\) has minimal degree at least \(\lfloor{(\text{n – m} + 2)}/\lfloor{(\text{d} + 4)}/3\rfloor\rfloor+\text{m}-2\), then \(G\) satisfies \(\text{P}_{\text{d,m}}(\text{G})\). Examples are given that show that this minimum degree requirement has the correct order of magnitude, and cannot be substantially weakened without losing Property \(\text{P}_{\text{d,m}}\).

A necessary and sufficient condition for a family of finite sets to possess a collection of \(n\) compatible systems of distinct representatives (SDR’s) is given. A decomposition of finite family of sets into partial SDR’s is also studied.

Let \(T(n)\) be the set of all trees with at least one and no more than \(n\) edges. A \(T(n)\)-factor of a graph \(G\) is defined to be a spanning subgraph of \(G\) each component of which is isomorphic to one of \(T(n)\). If every \(\text{K}_{1 .\text{k}}\) subgraph of \(G\) is contained in a \(T(n)\)-factor of \(G\), then \(G\) is said to be \(T(n)\)-factor \(k\)-covered. In this paper, we give a criterion for a graph to be a \(T(n)\)-factor \(k\)-covered graph.

The foundation of an analytic graph theory is developed.

The integrity of a graph, \(I(G)\), is given by \(I(G) = \min_{S} (|S| + m(G – S))\) where \(S \subseteq V(G)\) and \(m(G – S)\) is the maximum order of the components of \(G – S\). It is shown that, for arbitrary graph \(G\) and arbitrary integer \(k\), the determination of whether \(I(G) \leq k\) is NP-complete even if \(G\) is restricted to be planar. On the other hand, for every positive integer \(k\) it is decidable in time \(O(n^2)\) whether an arbitrary graph \(G\) of order \(n\) satisfies \(I(G) \leq k\). The set of graphs \(\mathcal{G}_k = \{G | I(G) \leq k\}\) is closed under the minor ordering and by the recent results of Robertson and Seymour the set \(\mathcal{O}_k\) of minimal elements of the complement of \(\mathcal{G}_k\) is finite. The lower bound \(|\mathcal{O}_k| \geq (1.7)^k\) is established for \(k\) large.

It is shown that unlike the chromatic polynomial, which does not characterize unions of non-trivial graphs, the circuit polynomial characterizes the unions of many families of graphs. They include unions of chains, cycles and mixtures of these graphs, also unions of complete graphs. It is also shown that in general, if a Hamiltonian graph is characterized by its circuit polynomial, then so also is the union of the graph with itself.