A Latin square of order \(n\) is an \(n \times n\) array such that each of the integers \(1, 2, \ldots, n\) (or any set of \(n\) distinct symbols) occurs exactly once in each row and each column. A Latin square \(L = [l_{i,j}]\) is said to be \underline{commutative} provided that \(l_{i,j} = l_{j,i}\) for all \(i\) and \(j\). Two Latin squares, \(L = [l_{i,j}]\) and \(M = [m_{i,j}]\), are said to have \underline{intersection} \(k\) if there are exactly \(k\) cells \((i,j)\) such that \(l_{i,j} = m_{i,j}\).

Let \(I[n] = \{0, 1, 2, \ldots, n^2-9, n^2-8, n^2-7, n^2-6,n^2\}\), \(H[n] = I[n] \cup \{n^2-7, n^2-4\}\), and \(J[n]\) be the set of all integers \(k\) such that there exists a pair of commutative Latin squares of order \(n$ which have intersection \(k\). In this paper, we prove that \(J[n] = I[n]\) for each odd \(n \geq 7\), \(J[n] = H[n]\) for each even \(n \geq 6\), and give a list of \(J[n]\) for \(n \leq 5\). This totally solves the intersection problem of two commutative Latin squares.

Golomb and Taylor (joined later by Etzion) have modified the notion of a complete Latin square to that of a Tuscan-\(k\) square. A Tuscan-\(k\) square is a row Latin square with the further property that for any two symbols \(a\) and \(b\) of the square, and for each \(m\) from \(1\) to \(k\), there is at most one row in which \(b\) is the \(m^{th}\) symbol to the right of \(a\). One question unresolved by a series of papers of the authors mentioned was whether or not \(n \times n\) Tuscan-\(2\) squares exist for infinitely many composite values of \(n+1\). It is shown here that if \(p\) is a prime and \(p \equiv 7 \pmod{12}\) or \(p \equiv 5 \pmod{24}\), then Tuscan-\(2\) squares of side \(2p\) exist. If \(p \equiv 7 \pmod{12}\), clearly \(2p + 1\) is always composite and if \(p \equiv 5 \pmod{24}\), \(2p+1\) is composite infinitely often. The squares constructed are in fact Latin squares that have the Tuscan-\(2\) property in both dimensions.

It is shown that if \([n] = X_1 \cup X_2 \cup \cdots \cup X_l\) is a partition of \([n]\) and if \(S_t\) is a family of \(t\)-valued functions intersecting on at least one element of \(k\) (circularly) consecutive blocks, then \(|S_t| < t^{n-k}\). If given \(a_1 < a_2 < \cdots < a_y \leq l \), \(\acute{S}_t\) is a family of \(t\)-valued functions intersecting on at least one element of \(X_{a_{1}+m}, X_{a_{2}+m}, \ldots, X_{a_{k}+m}\) for some \(m\) with \(1-a_1 \leq m \leq n – a_k\), then \(|\acute{S}_t| \leq t^{n-k}\). Both these results were conjectured by Faudree, Schelp, and Sós [FSS]. The main idea of our proofs is that of anticlusters introduced by Griggs and Walker [GW] which we discuss in some detail. We also discuss several related intersection theorems about sets, \(2\)-valued functions, and \(t\)-valued functions.

Let the edges of the complete graph \(K_n\) be \(2\)-colored. A Simple Hamiltonian Cycle is a Hamiltonian cycle in \(K_n\) that is either monochromatic or is a union of two monochromatic paths. The main result of this paper is that if \(n\) is an even integer greater than \(4\), then for every \(2\)-coloring of the edges of \(K_n\), there is a Simple Hamiltonian Cycle in \(K_n\) which is either monochromatic, or is a union of two monochromatic paths, where each path is of even length.

Uniquely pseudointersectable graphs are defined; this is closely related to the uniquely intersectable graphs introduced by Alter and Wang [1]. The S-property is necessary but not sufficient for a graph to be uniquely pseudointersectable. This condition is also sufficient for graphs with unique minimum cover. Finally, we show that for supercompact graphs, unique pseudointersectability and unique intersectability are equivalent. Thus we generalize some of the results in [1] to a wider class of graphs.

Suppose \(\Gamma\) is a finite multiplicative group and \(S \subseteq \Gamma\) satisfies \(1 \notin S\) and \(S^{-1} = \{x^{-1} | x \in S\} = S\). The abelian Cayley graph \(G = G(\Gamma, S)\) is the simple graph having vertex set \(V(G) = \Gamma\), an abelian group, and edge set \(E(G) = \{\{x, y\} | x^{-1}y \in S\}\). We prove the following regarding the chromatic index of an abelian Cayley graph \(G = G(\Gamma, S)\): if \(\langle S \rangle\) denotes the subgroup generated by \(S\), then \(\chi'(G) = \Delta(G)\) if and only if \(|\langle S \rangle|\) is even.

Let \(G\) be a graph and let \(D_1(G)\) denote the set of vertices of degree one in \(G\). In [1], Behocine, Clark, Kéhler, and Veldman conjectured that for a connected simple graph \(G\) of \(n\) vertices, if \(G – D_1(G)\) is \(2\)-edge-connected, and if for any edge \(xy \in E(G)\), \(d(x) + d(y) > \frac{2n}{5}-2\), then \(L(G)\) is hamiltonian.

In this note, we shall show that the conjecture above holds for a class of graphs that includes the \(K_{1,3}\)-free graphs, and we shall also characterize the extremal graphs.

A packing design (briefly packing) of order \(v\), block size \(k\), and index \(\lambda\) is a pair \((X,\mathcal{D})\) where \(X\) is a \(v\)-set (of points) and \(\mathcal{D}\) is a collection of \(k\)-subsets of \(X\) (called blocks) with cardinality \(b\) such that every \(2\)-subset of \(X\) is contained in at most \(\lambda\) blocks of \(\mathcal{D}\). We denote it by \(\mathrm{SD}(k,\lambda; v,b)\). If no other such packing has more blocks, the packing is said to be maximum, and the number of blocks in \(\mathcal{D}\) is the packing number \(\mathrm{D}(k,\lambda;v)\). For fixed \(k\),\(\lambda\) and \(v\), the packing problem is to determine the packing number. In this paper, the values of \(\mathrm{D}(5,2; v)\) are determined for all \(v \geq 5\) except \(48\) values of \(v\).

Behzad has conjectured that a simple graph G can always be totally coloured using two more colours than the maximum degree in G. The conjecture has been verified for several special classes of graphs by Behzad, Chartrand and Cooper, Rosenfeld,
and Meyer, and by Vijayaditya for graphs with maximum degree less than or equal to 3.We show algorithmically that the conjecture is true for graphs with maximum degree 4.