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.

In this paper, we prove that for any even integer \(m \geq 4\), there exists a nested \(m\)-cycle system of order \(n\) if and only if \(n \equiv 1 \mod{2m}\), with at most \(13\) possible exceptions (for each value of \(m\)). The proof depends on the existence of certain group-divisible designs that are of independent interest. We show that there is a group-divisible design having block sizes from the set \(\{5, 9, 13, 17, 29, 49\}\), and having \(u\) groups of size \(4\), for all \(u \geq 5\), \(u \neq 7, 8, 12, 14, 18, 19, 23, 24, 33, 34\).

We give a general construction of a triangle-free graph on \(4p\) points whose complement does not contain \(K_{p+2} – e\) for \(p \geq 4\). This implies that the Ramsey number \(R(K_3, K_k – e) \geq 4k – 7\) for \(k \geq 6\). We also present a cyclic triangle-free graph on \(30\) points whose complement does not contain \(K_9 – e\). The first construction gives lower bounds equal to the exact values of the corresponding Ramsey numbers for \(k = 6, 7,\) and \(8\). The upper bounds are obtained by using computer algorithms. In particular, we obtain two new values of Ramsey numbers \(R(K_3, K_8 – e) = 25\) and \(R(K_3, K_9 – e) = 31\), the bounds \(36 \leq R(K_3, K_{10} – e) \leq 39\), and the uniqueness of extremal graphs for Ramsey numbers \(R(K_3, K_6 – e)\) and \(R(K_3, K_7 – e)\).