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)\).

The concept of ladder tableaux is introduced, which may be considered as a natural extension of the shifted tableaux. By means of the dominance technique, a pair of determinantal expressions in terms of symmetric functions, for the generating function of ladder tableaux with a fixed shape, is established. As applications, the particular cases yield the generating functions for column-strict reverse plane partitions, symmetrical reverse plane partitions, and column-strict shifted reverse plane partitions with a given shape and with no part-restrictions.

Gyárfás and Lehel conjectured that any collection of trees \(T_2, T_3, \ldots, T_n\) on \(2, 3, \ldots, n\) vertices respectively, can be packed into the complete graph on \(n\) vertices. Fishburn proved that the conjecture is true for some classes of trees and for all trees up to \(n = 9\). Pritikin characterized the trees for which Fishburn’s proof works and extended the classes of trees for which the conjecture is known to be true. Using a computer, we have shown that the conjecture is true through \(n = 11\), but also that an approach suggested by Fishburn is unlikely to work in general.

The \({domination \; number}\) \(\gamma(G)\) of a graph \(G = (V, E)\) is the smallest cardinality of a \({dominating}\) set \(X\) of \(G\), i.e., of a subset \(X\) of vertices such that each \(v \in V – X\) is adjacent to at least one vertex of \(X\). The \(k\)-\({minimal \; domination \; number}\) \(\Gamma_k(G)\) is the largest cardinality of a dominating set \(Y\) which has the following additional property: For every \(\ell\)-subset \(Z\) of \(Y\) where \(\ell \leq k\), and each \((\ell-1)\)-subset \(W\) of \(V – Y\), the set \((Y – Z) \cup W\) is not dominating. In this paper, for any positive integer \(k \geq 2\), we exhibit self-complementary graphs \(G\) with \(\gamma(G) > k\) and use this and a method of Graham and Spencer to construct \(n\)-vertex graphs \(F\) for which \(\Gamma_k(F)\Gamma_k(\overline{F})>n\).