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.

In this paper, we obtain results on the number of constraints \(m\) for some balanced arrays of strength \(4\) when the parameters \(\mu_2\), \(\mu_3\) assume the values \(1\) and \(0\) respectively. It is shown that the maximum value of \(m\) is \(\mu_1 + 4\), and the existence of such an array is established.

A basis is exhibited for the first homology space of a surface over a field. This basis is found by extending a basis of the boundary cycle space of an embedded graph to the cycle space of the graph.

Let \(C(v)\) denote the least number of quintuples of a \(v\)-set \(V\) with the property that every pair of distinct elements of \(V\) occurs in at least one quintuple. It is shown, for \(v \equiv 3 \text{ or } 11\; \text{modulo} \;20\) and \(v \geq 11\), that \(C(v) = \lceil(v-1)/{4}\rceil\) with the possible exception of \(v \in \{83, 131\}\).

An undirected graph of diameter \(D\) is said to be \(D\)-critical if the addition of any edge decreases its diameter. The structure of \(D\)-critical graphs can be conveniently studied in terms of vertex sequences. Following on earlier results, we establish, in this paper, fundamental properties of \(K\)-edge-connected \(D\)-critical graphs for \(K\geq8\) and \(D\geq7\). In particular, we show that no vertex sequence corresponding to such a graph can contain an “internal” term less than \(3\), and that no two non-adjacent internal terms can exceed \(\text{K}-\lceil{2}\sqrt{\text{K}}\rceil+1\). These properties will be used in forthcoming work to show that every subsequence (except at most one) of length three of the vertex sequence contains exactly \(K+1\) vertices, a result which leads to a complete characterization of edge-maximal vertex sequences.

Lander Conjectured: If \(D\) is a \((\text{v, k}, \lambda)\) difference set in an abelian group G with a cyclic Sylow p-subgroup, then p does not divide \((v, n)\), where \(\text{n} = \text{k} – \lambda \).

In a previous paper, the above conjecture was verified for \(\lambda = 3\) and \(\text{k} \leq 500\), except for \(\text{k} = 228, 282\) and \(444\). These three exceptional values are dealt with in this note, thereby verifying Lander’s conjecture completely for \(\lambda = 3\) and \(\text{k} \leq 500\).

Generalized Moore graphs are regular graphs that satisfy an additional distance condition, namely, that there be the maximum number of vertices as close as possible to any particular vertex, when that vertex is considered as root vertex. These graphs form a useful model for the study of various theoretical properties of computer communications networks. In particular, they lend themselves to a discussion of lower bounds for network cost, delay, reliability, and vulnerability. A considerable number of papers have already been published concerning the existence and properties of generalized Moore graphs of valence three, and some initial studies have discussed generalized Moore graphs of valence four, when the number of vertices is less than fourteen. This paper continues the previous studies for those cases when the graph contains a number of vertices that is between fourteen and twenty. In the case of valence three, the graph with a complete second level exists; it is just the Petersen graph. The situation is quite different for valence four; not only does the graph with a complete second level not exist, but the graphs in its immediate “neighbourhood” also fail to exist.

In this paper, we investigate the existence of skew frames with sets of skew transversals. We consider skew frames of type \(1^n\) and skew frames of type \((2^m)^q\) with sets of skew transversals. These frames are equivalent to three-dimensional frames which have complementary \(2\)-dimensional projections with special properties.

All graphs meeting the basic necessary conditions to be the leave graph of a maximal partial triple system with at most thirteen elements are generated. A hill-climbing algorithm is developed to determine which of these candidates are in fact leave graphs. Improved necessary conditions for a graph to be a leave graph are developed.

Some new lower bounds for higher Ramsey numbers are presented. Results concerning generalized hypergraph Ramsey numbers are also given.