We show that for infinitely many \(n\), there exists a Cayley graph \(\Gamma\) of order \(n\) in which any two largest cliques have a nonempty intersection. This answers a question of Hahn, Hell, and Poljak. Further, the graphs constructed have a surprisingly small clique number \(c_\Gamma = \left\lfloor \sqrt{2n} \right\rfloor\) (and we do not know if the constant \(\sqrt{2}\) can be made smaller).

\(D\)-optimal exact designs in a completely randomized statistical set-up are constructed, for comparing \(n > 2\) qualitative factors (treatments), making \(r\) observations per treatment level in the presence of \(n\) (or less) quantitative or continuous factors (regression factors or covariates) of influence. Their relation with cyclic supplementary difference sets \(2-{(u; k_1, k_2; \lambda)}\) is shown, when \(n = 2u \equiv 2 \pmod{4}\), \(r \equiv 1 \pmod{2}\), \(r \neq 1\), \(r < u\) and \(k_1, k_2, \lambda\) are defined by \(1 \leq k_1 \leq k_2 \leq (u-1)/2\), \((u-2k_1)^2 + (u-2k_2)^2 = 2(ur+u-r)\), \(\lambda = k_1 + k_2 – (u-r)/2\). Making use of known cyclic difference sets, the existence of a multiplier and the non-periodic autocorrelation function of two sequences, such supplementary difference sets are constructed for the first time. A list of all 201 supplementary difference sets \(2-{(u; k_1, k_2; \lambda)}\) for \(n = 2u < 100\) is given.

In this paper, we consider a permutation \(\sigma \in S_n\) as acting on an arbitrary tree with \(n\) vertices (labeled \(1, 2, 3, \ldots, n\)). Each edge \([a, b]\) of \(T\) corresponds to a transposition \((a, b) \in S_n\), and such a “tree of transpositions” forms a minimal generating set for \(S_n\). If \(\sigma \in S_n\), then \(\sigma\) may be written as a product of transpositions from \(T, \sigma = t_k t_{k-1} \ldots t_2t_1\). We will refer to such a product as a \(T\)-factorization of \(\sigma\) of length \(k\). The primary purpose of this paper is to describe an algorithm for producing \(T\)-factorizations of \(\sigma\). Although the algorithm does not guarantee minimal factorizations, both empirical and theoretical results indicate that the factorizations produced are “nearly minimal”. In particular, the algorithm produces factorizations that never exceed the known upper bounds.

The linear vertex-arboricity of a surface \(S\) is the maximum of the linear vertex-arboricities of all graphs embeddable into \(S\). Poh showed that the linear vertex-arboricity of a sphere is three. We show that the linear vertex-arboricities of a projective plane and a torus are three and four, respectively. Moreover, we show that the linear vertex-arboricity of a Klein bottle is three or four.

We consider a pair of MOLS (mutually orthogonal Latin squares) having holes, corresponding to missing sub-MOLS, which are disjoint and spanning. If the two squares are mutual transposes, we say that we have SOLS (self-orthogonal Latin squares) with holes. It is shown that a pair of SOLS with \(n\) holes of size \(h \geq 2\) exist if and only if \(n \geq 4\) and it is also shown that a pair of SOLS with \(n\) holes of size \(2\) and one hole of size \(3\) exist for all \(n \geq 4, n \neq 13, 15\).

As an application, we prove a result concerning intersection numbers of transversal designs with four groups.

Let \(V\) be a finite set of order \(v\). A \((v, \kappa, \lambda)\) covering design of index \(\lambda\) and block size \(\kappa\) is a collection of \(\kappa\)-element subsets, called blocks, such that every \(2\)-subset of \(V\) occurs in at least \(\lambda\) blocks. The covering problem is to determine the minimum number of blocks, \(\alpha(v, \kappa, \lambda)\), in a covering design. It is well known that
\(\alpha(v, \kappa, \lambda) \geq \lceil \frac{v}{\kappa}\lceil\frac{v-1}{\kappa -1}\lambda\rceil\rceil = \phi(v, \kappa, \lambda)\)
where \(\lceil x \rceil\) is the smallest integer satisfying \(x \leq \lceil x \rceil\). It is shown here that
\(\alpha(v, 5, 6) = \phi (v, 5, 6)\) for all positive integers \(v \geq 5\), with the possible exception of \(v = 18\).

In an edge-colored graph, a cycle is said to be alternating, if the successive edges in it differ in color. In this work, we consider the problem of finding alternating cycles through \(p\) fixed vertices in \(k\)-edge-colored graphs, \(k \geq 2\). We first prove that this problem is NP-Hard even for \(p = 2\) and \(k = 2\). Next, we prove efficient algorithms for \(p = 1\) and \(k\) non-fixed, and also for \(p = 2\) and \(k = 2\), when we restrict ourselves to the case of \(k\)-edge-colored complete graphs.

It is shown that the obvious necessary condition for the existence of a \(\text{B}(8,7; v)\) is sufficient, with the possible exception of \(v \in \{48, 56, 96, 448\}\).

We prove that for any tree \(T\) of maximum degree three, there exists a subset \(S\) of \(E(T)\) with \(|S| = O(\log n)\) and a two-coloring of the edges of the forest \(T \setminus S\) such that the two monochromatic forests are isomorphic, where \(n\) is the number of vertices of \(T\) of degree three.