A graph \(H\) is \underline{collapsible} if for every even subset \(W \subseteq V(H)\), \(H\) has a spanning connected subgraph whose set of odd-degree vertices is \(W\). In a graph \(G\), there is a unique collection of maximal collapsible subgraphs, and when all of them are contracted, the resulting contraction of \(G\) is a reduced graph. Reduced graphs have been shown to be useful in the study of supereulerian graphs, hamiltonian line graphs, and double cycle covers, (see[2], [3], [4] [6] ), among others. It has been noted that subdividing an edge of a collapsible graph may result in a noncollapsible graph. In this note we characterize the reduced graphs of elementary subdivision of collapsible graphs of diameter at most two. We also obtain a converse of a result of Catlin [3] when restricted to graphs of diameter at most two. The main result is used to study some hamiltonian property of line graphs.

The \(F\)-free chromatic number \(\chi(M:-F)\) of a graph \(M\) is defined as the least number of classes in a partition of the vertices of \(M\) such that \(F\) does not occur as an induced subgraph in the subgraph induced by any of the colour classes. Two graphs \(G\) and \(H\) are called chromatically related if, for each positive integer \(k\), there exists a graph \(M\) such that \(\chi(M:-G) = \chi(M:-H) = k\), and distantly related whenever a chain of such relatednesses exists between them. Using a basic theorem of Folkman [3], we show that every two graphs on at least two vertices are distantly related.

BIBRC (balanced incomplete block with nested rows and columns) designs were introduced by Singh and Dey [1979] and these designs were mostly obtained by trial and error. Agrawal and Prasad [1983] gave some systematic methods of construction of these designs. We provide further systematic and general methods of construction of BIBRC designs in the present note.

An exponent bound is presented for abelian \((p^{i+j}, p^i, p^{i+j},p^j)\) relative difference sets: this bound can be met for \(i \leq j\).

A smallest transversal of a \(k\)-graph (or \(k\)-uniform hypergraph) is any smallest set of vertices that intersects all edges. We investigate smallest transversals of small (up to ten vertex) \(3\)-graphs. In particular, we show how large the smallest transversal of small \(3\)-graphs can be as a function of the number of edges and vertices. Also, we identify all \(3\)-graphs with up to nine vertices that have largest smallest transversals. This work is related to a problem of Turán, and to the covering problem. In particular, extremal \(3\)-graphs correspond to covering designs with blocks of size \(n-3\).

We determine those triples \((g, u, k)\) for which there exists a pair of group divisible designs with block size \(3\), each on the same \(u\) groups of size \(g\), having exactly \(k\) blocks in common.

Using the explicit determination of all ovals in the 3 non-Desarguesian projective planes of order 9 given in [4] or [8], we prove that there are no other Benz planes of order 9 than the three miquelian planes and the Minkowski plane over the Dickson near-field of type \(\{3,2\}\).

Sufficient conditions depending on the minimum degree and the independence number of a simple graph for the existence of a \(k\)-factor are established.

In this paper, we shall establish some construction methods for resolvable Mendelsohn designs, including constructions of the product type. As an application,we show that the necessary condition for the existence of a \((v, 4, \lambda)\)-RPMD, namely,
\(v \equiv 0\) or \(1\) (mod 4), is also sufficient for \(\lambda > 1\) with the exception of pairs \((v,\lambda)\)
where \(v = 4\) and \(\lambda\) odd. We also obtain a (v, 4, 1)-RPMD for \(v = 57\) and \(93\).

A counterexample is presented to the following conjecture of Jackson: If \(G\) is a 2-connected graph on at most \(3k + 2\) vertices with degree sequence \((k, k, \ldots, k, k+1, k+1)\), then \(G\) is hamiltonian.