We give a constructive and very simple proof of a theorem by Chech and Colbourn [7] stating the existence of a cyclic \((4p, 4, 1)\)-BIBD (i.e. regular over \({Z}_{4p}\)) for any prime \(p \equiv 13 \mod 24\). We extend the theorem to primes \(p \equiv 1 \mod 24\) although in this case the construction is not explicit. Anyway, for all these primes \(p\), we explicitly construct a regular \((4p, 4, 1)\)-BIBD over \({Z}_{2}^{2} \oplus {Z}_p\).

In this paper, we prove the gracefulness of a new class of graphs denoted by \(K_{n}\otimes S_{2^{{n-1}}-\binom{n}{2}}\).
We also prove that the graphs consisting of \(2m + 1\) internally disjoint paths of length \(2r\) each, connecting two fixed vertices, are also graceful.

Erdős and Sésg conjectured in 1963 that if \(G\) is a graph of order \(p\) and size \(q\) with \(q > \frac{1}{2}p(k-1)\), then \(G\) contains every tree of size \(k\). This is proved in this paper when the girth of the complement of \(G\) is greater than \(4\).

Using path counting arguments, we prove
\(min\{\binom{x_1+x_2+y_1+y_2}{x_1,x_2,(y_1+y_2)},\binom{(x_1+x_2+y_1+y_2)}{(x_1+x_2),y_1,y_2}\}\leq\binom{x_1+y_1}{x_1}\binom{x_1+y_2}{x_1}\binom{x_2+y_1}{x_2}\binom{x_2+y_2}{x_2}\)

This inequality, motivated by graph coloring considerations, has an interesting geometric interpretation.

The existence of holey self-orthogonal Latin squares with symmetric orthogonal mates (HSOLSSOMs) of types \(h^n\) and \(1^{n}u^1\) is investigated. For type \(h^n\), new pairs of \((h, n)\) are constructed so that the possible exceptions of \((h, n)\) for the existence of such HSOLSSOMs are reduced to \(11\) in number. Two necessary conditions for the existence of HSOLSSOMs of type \(1^{n}u^1\) are (1) \(n \geq 3u + 1\) and (2) \(n\) must be even and \(u\) odd. Such an HSOLSSOM gives rise to an incomplete SOLSSOM. For \(3 \leq u \leq 15\), the necessary conditions are shown to be sufficient with seven possible exceptions. It is also proved that such an HSOLSSOM exists whenever even \(n \geq 5u + 9\) and odd \(u \leq 9\).

We prove: A connected magic graph with \(n\) vertices and \(q\) edges exists if and only if \(n = 2\) and \(q = 1\) or \(n \geq 5\) and \(\frac{5n}{4} < q < \frac{n(n-1)}{2} \).

Sharp bounds are presented for the \(\lambda\)-number of the Cartesian product of a cycle and a path, and of the Cartesian product of two cycles.

A set \(S = \{v_1, v_2, \ldots, v_n\}\) of vertices in a graph \(G\) with associated sequence \(k_1, k_2, \ldots, k_n\) of nonnegative integers is called a step domination set if every vertex of \(G\) is at distance \(k_i\) from \(v_i\) for exactly one \(i\) (\(1 \leq i \leq n\)). The minimum cardinality of a step domination set is called the step domination number of \(G\). This parameter is determined for several classes of graphs and is investigated for trees.

We completely determine the spectrum (i.e. set of orders) of complete \(4\)-partite graphs with at most one odd part which are decomposable into two isomorphic factors with a finite diameter. For complete \(4\)-partite graphs with all parts odd we solve the spectrum problem completely for factors with diameter \(5\). As regards the remaining possible finite diameters, \(2, 3, 4\), we present partial results, focusing on decompositions of \(K_{n,n,n,m}\) and \(K_{n,n,m,m}\) for odd \(m\) and \(n\).