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.

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.