The translation planes of order 16 have been classified by Dempwolff and Reifart \([4]\). Using this classification, and in particular the spreads given in that paper, we have conducted a complete computer search for the hyperovals (18-arcs) in each of these planes. With few exceptions, the hyperovals obtained are hyperbolic (having two points on the special line at infinity) and are of a type we call translation hyperovals. The only exceptions occur in the plane over the semifield with kernel \({GF}(2)\). In this plane there also appear a class of elliptic (having no points on the special line at infinity) hyperovals and two classes of hyperbolic hyperovals which are not translation hyperovals. The automorphism groups of the hyperovals are also determined.

The problem we consider is: Given a complete multipartite graph \(G\) with integral weights on the edges, and given an integer \(m\), find a clique \(C\) in \(G\) such that the weight-sum of the edges of \(C\) is greater than or equal to \(m\). We prove that where \(G\) has \(k\) parts, each with at most two nodes, the edge-weights are \(0-1\), and \(m = \binom{k}{2}\), this problem is equivalent to \(2\)-conjunctive normal form satisfiability, and hence is polynomially solvable. However, if either each part has at most three nodes or \(m\) is arbitrary, the problem is NP-complete. We also show that a related problem which is equivalent to a \(0-1\) weighted version of \(2\)-CNF satisfiability is NP-complete.

The maximum edge-weighted clique problem in complete multipartite graphs arises in transit scheduling, where it is called the schedule synchronization problem.

We describe an algorithm which combines a discrete optimization heuristic with the construction due to Ringel and Sachs (independently) for self-complementary graphs. The algorithm is applied to some problems from Generalized Ramsey Theory.

Let \(k\) and \(\ell\) be nonnegative integers, not both zero, and \(D \subseteq {N} – \{1\}\). A (connected) graph \(G\) is defined to be \((k, \ell, D)\)-stable if for every pair \(u, v\) of vertices of \(G\) with \(d_G(u, v) \in D\) and every set \(S\) consisting of at most \(k\) vertices of \(V(G) – \{u, v\}\) and at most \(\ell\) edges of \(E(G)\), the distance between \(u\) and \(v\) in \(G – S\) equals \(d_G(u, v)\). For a positive integer \(m\), let \({N}_{\geq m} = \{x \in {N} \mid x \geq m\}\). It is shown that a graph is \((k, \ell, \{m\})\)-stable if and only if it is \((k, \ell, {N}_{\geq m})\)-stable. Further, it is established that for every positive integer \(x\), a graph is \((k + x, \ell, \{2\})\)-stable if and only if it is \((k, \ell+x, \{2\})\)-stable. A generalization of \((k, \ell, \{m\})\)-stable graphs is considered. For a planar \((k, 0, \{m\})\)-stable graph, \(m \geq 3\), a sharp bound for \(k\) in terms of \(m\) is derived.

Given a graph \(G\) with weighting \(w: E(G) \to Z^+\), the strength of \(G(w)\) is the maximum weight on any edge. The sum of a vertex in \(G(w)\) is the sum of the weights of all its incident edges. \(G(w)\) is \({irregular}\) if the vertex sums are distinct. The \({irregularity \; strength}\) of a graph is the minimum strength of the graph under all irregular weightings. We present fast heuristic algorithms, based on hill-climbing and simulated annealing, for finding irregular weightings of a given strength. The heuristics are compared empirically, and the algorithms are then used to formulate a conjecture.

A graph \(G\) is said to be maximal clique irreducible if each maximal clique in \(G\) contains an edge which is not contained in any other maximal clique of \(G\). In 1981, Opsut and Roberts proved that any interval graph is maximal clique irreducible. In this paper, we generalize their result and consider the question of characterizing maximal clique irreducible graphs.

It is shown that the obvious necessary condition \(\lambda h(h – 1)m^2 \equiv 0 \pmod{k}\) for the existence of a \((v, k, \lambda)\)-perfect Mendelsohn design with \(h\) holes of size \(m\) is sufficient in the case of block size three, except for a nonexisting \((6, 3, 1)\)-PMD.

We introduce neighborhood intersection graphs and multigraphs of loop-graphs to generalize the standard notions of square and distance-two graphs. These neighborhood (multi)graphs are then used to construct self-dual graphs and multigraphs (embedded on surfaces of varying genus) which have involutory vertex-face mappings.

As stated in \([2]\), there is a conjecture that the determinant function maps the set of \(n \times n\) \((0, 1)\)-matrices onto a set of consecutive integers for any given \(n\). While this is true for \(n \leq 6\), it is shown to be false for \(n = 7\). In particular, there is no \(7 \times 7\) determinant in the range \(28 – 31\), but there is one equal to \(32\). Then the more general question of the range of the determinant function for all \(n\) is discussed. A lower bound is given on the largest string of consecutive integers centered at \(0\), each of which is a determinant of an \(n \times n\) \((0, 1)\)-matrix.