The concept of self-complementary (s.c.) graphs is extended to almost self-complementary graphs. We define an \(n\)-vertex graph to be almost self-complementary (a.s.c.) if it is isomorphic to its complement with respect to \(K_n – e\), the complete graph with one edge removed. A.s.c. graphs with \(n\) vertices exist if and only if \(n \equiv 2\) or \(3 \pmod{4}\), i.e., precisely when s.c. graphs do not exist. We investigate various properties of a.s.c. graphs.

A triangulation of a surface is \(\delta\)-regular if each vertex is contained in exactly \(\delta\) edges. For each \(\delta \geq 7\), \(\delta\)-regular triangulations of arbitrary non-compact surfaces of finite genus are constructed. It is also shown that for \(\delta \leq 6\) there is a \(\delta\)-regular triangulation of a non-compact surface \(\sum\) if and only if \(\delta = 6\) and \(\sum\) is homeomorphic to one of the following surfaces: the Euclidean plane, the two-way-infinite cylinder, or the open Möbius band.

The packing number \(D(2,k,v)\) is defined to be the maximum cardinality of a family of \(k\)-subsets, chosen from a set of \(v\) elements, such that no pair of elements appears in more than one \(k\)-subset. We examine \(D(2,k,v)\) for \(v < k(k-1)\) and determine such numbers for the case \(k=5\), \(v < 20\).

Ho and Shee [5] showed that for a graph \(G\) of order \(n\) \((\geq4)\) and size \(m\) to be cordial, it is necessary that \(m\) must be less than \(\frac{n(n-1)}{2} – \left\lceil\frac{n}{2}\right\rceil + 2\).

In this paper, we prove that there exists a cordial graph of order \(n\) and size \(m\), where
\(n-1\leq m\leq\frac{n(n-1)}{2} – \left\lceil\frac{n}{2}\right\rceil + 1.\)

Let \(B_n = K(1,1,n)\) denote the \(n\)-book. In this paper we (i) calculate \(\lambda(C_5, B_n)\) for all \(n\),
(ii) prove that if \(m\) is an odd integer \(\geq 7\) and \(n \geq 4m – 13\) then \(r(C_m, B_n) = 2n + 3\),and (iii)
prove that if \(m \geq 2n + 2\) then \(r(C_m, B_n) = 2m – 1\).

The notion of fusion in association schemes is developed and then applied to group schemes. It is shown that the association schemes derived in [1] and [4] are special cases of \(A\)-fused schemes of group schemes \(X(G)\), where \(G\) is abelian and \(A\) is a group of automorphisms of \(G\). It is then shown that these latter schemes give rise to PBIB designs under constructions identical to those found in [1] and [4].

Let \(G = (X, E)\) be any graph. Then \(D \subset X\) is called a dominating set of \(G\) if for every vertex \(x \in X – D\), \(x\) is adjacent to at least one vertex of \(D\). The domination number, \(\gamma(G)\), is \(\min \{|D| \mid D\) { is a dominating set of } \(G\}\). In 1965 Vizing gave the following conjecture: For any two graphs \(G\) and \(H\)

\[\gamma(G \times H) \geq \gamma(G) . \gamma(H).\]

In this paper, it is proved that \(\gamma(G \times H) > \gamma(G) . \gamma(H)\) if \(H\) is either one of the following graphs: (a) \(H = G^-\), i.e., complementary graph of \(G\), (b) \(H = C_m\), i.e., a cycle of length \(m\) or (c) \(\gamma(H) \leq 2\).

In [1],[2], there are many assignment models. This paper gives a new assignment model and an algorithm for solving this problem.

Let \(v, k\), and \(n\) be positive integers. An incomplete perfect Mendelsohn design, denoted by \(k\)-IMPD\((v, n)\), is a triple \((X, Y, B)\) where \(S\) is a \(v\)-set (of points), \(Y\) is an \(n\)-subset of \(X\), and \(B\) is a collection of cyclically ordered \(k\)-subsets of \(X\) (called blocks) such that every ordered pair \((a, b) \in (X \times X) \setminus (Y \times Y)\) appears \(t\)-apart in exactly one block of \(B\) and no ordered pair \((a, b) \in Y \times Y\) appears in any block of \(B\) for any \(t\), where \(1 \leq t \leq k – 1\). In this paper, some basic necessary conditions for the existence of a \(k\)-IMPD\((v, n)\) are easily obtained, namely,
\((v – n)(v – (k – 1)n – 1) \equiv 0 \pmod{k} \quad {and} \quad v > (k – 1)n + 1.\) It is shown that these basic necessary conditions are also sufficient for the case \(k = 3\), with the one exception of \(v = 6\) and \(n = 1\). Some problems relating to embeddings of perfect Mendelsohn designs and associated quasigroups are mentioned.