We examine the problem of finding longest cycles in inner triangulations, that is, \(2\)-connected planar graphs in which all interior faces are triangles. These include the important family of geometric graphs called Delaunay triangulations In particular, we present two efficient heuristics for finding a longest cycle in an inner triangulation. The heuristics operate by considering at each step a local set of faces adjacent to the current cycle as candidates for inclusion in the cycle.

A dominating set in a graph \(G\) is a set \(D\) of nodes such that every node of \(G\) is either in \(D\) or is adjacent to some node in \(D\). The domination number \(\alpha(G)\) is the minimum size of a dominating set. The purpose of this paper is to explore the changing or unchanging of \(\alpha(G)\) when either a node is deleted, or an edge is added or deleted.

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.