We enumerate the perfect one-factorizations of \(K_{50}\), which are generated by starters in \({Z}_{49}\), fixed by multiplication by \(18\) and \(30\). There are precisely \(67\) non-isomorphic examples.

Let the vertices of a graph denote computer processes which communicate by passing messages along edges. It has been a standard Computer Science problem to provide algorithms that let the processes solve problems jointly (e.g. leader election, clock synchronization). What if some of the processes are maliciously faulty, i.e. send messages calculated to sabotage joint algorithms? Here we review a few “byzantine agreement” algorithms with interesting graph-theoretic features and raise questions about graph connectivity and diameter (with a few answers).

Let the vertices of a graph denote processes in a distributed or time-shared computer system; let two vertices be connected by an edge if the two processes cannot proceed at the same time (they mutually exclude one another). Managing mutual exclusion and related scheduling problems has given rise to substantial literature in computer science. Some methods of attack include covering or partitioning the graph with cliques or threshold graphs. Here I survey some recent graph-theoretic results and examples motivated by this approach.

A triangle in a Steiner triple system \(S\) is a triple of blocks from \(S\) which meet pairwise and whose intersection is empty. If \(S\) contains \(b\) blocks, and \(b = 3q + 8\), where \(0 \leq 8 \leq 2\), then a triangulation of \(S\) is a collection of \(q\) triangles \(\{T_1, T_2, \ldots, T_q\}\) in \(S\) such that no two distinct triangles share a common block. It is shown that, for \(v \equiv 1\) or \(3 \pmod{6}\), there exists a Steiner triple system which admits a triangulation. Moreover, if \(8 = 2\), there is a triangulated triple system in which the pair of blocks not occurring in a triangle are disjoint, and a triangulated triple system in which they intersect.

The polynomial algorithms for isomorphism testing in \(3\)-regular graphs known to date use set-wise stabilisation in \(2\)-groups acting on singletons, pairs, and sometimes triples of vertices. In this note we describe a new, simpler way of “getting rid of the triples”. Although the order of the complexity of isomorphism testing remains \(O(\text{n}^3 \log \text{n})\), the resulting algorithm is more efficient, since this portion of the set-wise stabilisation in the algorithm will be faster.

In thie paper, various constructions for resolvable group divisible designs with block size \(4\) are given.

A group satisfies PP3 (the permutation property of degree \(3\)) if any product of \(3\) elements remains invariant under some nontrivial permutation of its factors, or equivalently, if \(G\) has at most one nontrivial commutator of order \(2\). A PP3 group is \(\underline{\text{elementary}}\) if it is a finite group of exponent at most \(4\). There is an algorithm that associates an elementary PP3 group to an arbitrary graph. It follows, for instance, that almost every nontrivial graph automorphism has order a power of \(2\) and that the first-order theory of (elementary) PP3 groups is hereditarily undecidable.

A generalization of Sperner’s labeling for simplices is considered. It allows us to give any label not only to points from the interior of the simplex but also to points from the relative interior of each facet, while the Sperner labeling rule is preserved for all points on the boundary of each facet. Some properties of this labeling and its behavior on the facets of the simplex are discussed. Also, necessary and sufficient conditions for the existence of an odd number of completely labelled simplices in any triangulation of the simplex are given.

Orthomorphism graphs of groups are defined and a correspondence, between cliques of orthomorphism graphs and difference matrices and generalized Hadamard matrices, is established. Some examples of orthomorphism graphs are given.
Also, for \(\lambda = 1\), known values and bounds for clique numbers of orthomorphism graphs of groups of small order are surveyed.

In this paper we consider the problem of characterizing directed graphs of specified diameter. We are especially interested in the minimal number of arcs \(\textbf{a(d,n)}\) required to construct a directed graph on \(n\) vertices with diameter \(d\). Classes of graphs considered include general digraphs, digraphs without cycles of length \(2\), and digraphs with regular indegree or regular outdegree. Upper bounds are developed in cases where the exact solutions are not known.

In assessing the “vulnerability” of a graph one determines the extent to which the graph retains certain properties after the removal of a number of vertices and/or edges. Four measures of vulnerability to vertex removal are compared for classes of graphs with edge densities ranging from that of trees to that of the complete graph.

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 = k}-\lambda\).

Various nonexistence theorems are used to verify the above conjecture (all hand calculations) for \(\text{k} \leq 500\), except for \(\text{k} = 228, 282\) and \(444\), when \(\lambda = 3\). Using a machine, it is possible to do the checking for large \(k\).