Let \(x_1, x_2, \ldots, x_v\) be commuting indeterminates over the integers. We say an \(v \times v \times v \ldots \times v \) n-dimensional matrix is a proper \(v\)-dimensional orthogonal design of order \(v\) and type \((s_1, s_2, \ldots, s_r)\) (written \(\mathrm{OD}^n(s_1, s_2, \ldots, s_r)\)) on the indeterminates \(x_1, x_2, \ldots, x_r\) if every 2-dimensional axis-normal submatrix is an \(\mathrm{OD} (s_1, s_2, \ldots, s_r)\) of order \(v\) on the indeterminates \(x_1, x_2, \ldots, x_r\). Constructions for proper \(\mathrm{OD}^n(1^2)\) of order 2 and \(\mathrm{OD}^n(1^4)\) of order 4 are given in J. Seberry (1980) and J. Hammer and J. Seberry (1979, 1981a), respectively. This paper contains simple constructions for proper \(\mathrm{OD}^n(1^{2})\), \(\mathrm{OD}^n(1^{4})\), and \(\mathrm{OD}^n(1^{ 8})\) of orders 2, 4, and 8, respectively. Prior to this paper no proper higher dimensional OD on more than 4 indeterminates was known.

Bondy and Fan recently conjectured that if we associate non-negative real weights to the edges of a graph so that the sum of the edge weights is \(W\), then the graph contains a path whose weight is at least \(\frac{2W}{n}\). We prove this conjecture.

Let \(H(V, E)\) be an \(r\)-uniform hypergraph. Let \(A \subset V\) be a subset of vertices and define \(\deg_H(A) = |\{e \in E : A \subset e\}|\).

We say that \(H\) is \((k, m)\)-divisible if for every \(k\)-subset \(A\) of  \(V(H)\), \(\deg_H(A) \equiv 0 \pmod{m}\). (We assume that \(1 \leq k < r\)).

Given positive integers \(r \geq 2\), \(k \geq 1\) and \(q\) a prime power, we prove that if \(H\) is an \(r\)-uniform hypergraph and \(|E| > (q-1) \binom{\mid V \mid}{k} \), then \(H\) contains a nontrivial subhypergraph \(F\) which is \((k, q)\)-divisible.

It is well known that there exist complete \(k\)-caps in \(\mathrm{PG}(3,q)\) with \(k \geq \frac{q^2+q+4}{2}\) and it is still unknown whether or not complete \(k\)-caps of size \(k < \frac{q^2+q+4}{2}\) and \(q\) odd exist. In this paper sufficient conditions for the existence of complete \(k\)-caps in \(\mathrm{PG}(3,q)\), for good \(q \geq 7\) and \(k < \frac{q^2+q+4}{2}\), are established and a class of such complete caps is constructed.

It is proved in this paper that for any given odd integer \(\lambda \geq 1\), there exists an integer \(v_0 = v_0(\lambda)\), such that for \(v > v_0\), the necessary and sufficient conditions for the existence of an indecomposable triple system \(B(3,\lambda; v)\) without repeated blocks are \(\lambda(v – 1) \equiv 0 \pmod{2}\) and \(\lambda{v(v – 1)} \equiv 0 \pmod{6}.\)

We prove that if \(G\) is a 1-tough graph with \(n = |V(G)| \geq 13\) such that
the degree sum of any three independent vertices is at least \(\frac{3n-14}{2}\), then \(G\) is hamiltonian.

This paper deals with the problem of labeling the vertices, edges, and interior faces of a grid graph in such a way that the label of the face itself and the labels of vertices and edges surrounding that face add up to a value prescribed for that face.

Let \(G\) be a 3-edge-connected simple triangle-free graph of order \(n\) . Using a contraction method, we prove that if \(\delta(G) \geq 4\) and if \(d(u) + d(v) > n/10\) whenever \(uv \in E(G)\) (or whenever \(uv \notin E(G)\) ), then the graph \(G\) has a spanning eulerian sub-
graph. This implies that the line graph \(L(G)\) is hamiltonian. We shall also characterize the extremal graphs.

Let \(k,n\) be positive integers. Define the number \(f(k,n)\) by\\
\(f(k,n) = \min \left\{\max \left\{|S_i|: i=1,\ldots,k\right\}\right\},\)
where the minimum is taken over all \(k\)-tuples \(S_1,\ldots,S_k\) of cliques of the complete graph \(K_n\), which cover its edge set. Because there exists an \((n,m,1)\)-BIBD if and only if \(f(k,n) = m\), for \(k=\frac{n(n-1)}{m(m-1)}\), the problem of evaluating \(f(k,n)\) can also be considered as a generalization of the problem of existence of balanced incomplete block designs with \(\lambda=1\).

In the paper, the values of \(f(k,n)\) are determined for small \(k\) and some asymptotic properties of \(f\) are derived. Among others, it is shown that for all \(k\) \(\lim_{n\to\infty} \frac {f(k,n)}{n} \) exists.

A new method of construction of balanced ternary designs from PBIB designs, which yields two new designs, is given.

A dominating set \(X\) of a graph \(G\) is a k-minimal dominating set of \(G\) iff the
removal of any \(\ell \leq k\) vertices from \(X\) followed by the addition of any \(\ell \sim 1\) vertices of G
results in a set which does not dominate \(G\). The \(k\)-minimal domination number IWRC)
of \(G\) is the largest number of vertices in a k-minimal dominating set of G. The sequence
\(R:m_1 \geq m_2 \geq… \geq m_k \geq …. \geq\) n of positive integers is a domination sequence iff
there exists a graph \(G\) such that \(\Gamma_1 (G) = m_1, \Gamma_2(G) = m_2,… \Gamma_k(G) = m_k,…,\)
and \(\gamma(G) = n\), where \(\gamma(G)\) denotes the domination number of G. We give sufficient
conditions for R to be a domination sequence.

Using the definition of \(k\)-free, a known result can be re-stated as follows: If \(G\) is not edge-reconstructible then \(G\) is \(k\)-free, for all even \(k\). To get closer, therefore, to settling the Edge-Reconstruction Conjecture, an investigation is begun into which graphs are, or are not, \(k\)-free (for different values of \(k\), in particular for \(k = 2\)); we also discuss which graphs are \(k\)-free, for all \(k\).

A \((v, k, \lambda)\) covering design of order \(v\), block size \(k\), and index \(\lambda\) is a collection of \(k\)-element subsets, called blocks of a set \(V\) such that every \(2\)-subset of \(V\) occurs in at least \(\lambda\) blocks. The covering problem is to determine the minimum number of blocks in a covering design. In this paper we solve the covering problem with \(k = 5\) and \(\lambda = 4\) and all positive integers \(v\) with the possible exception of \(v = 17, 18, 19, 22, 24, 27, 28, 78, 98\).

Let \(\rho\) be an \(h\)-ary areflexive relation. We study the complexity of finding a strong \(h\)-coloring for \(\rho\), which is defined in the same way for \(h\)-uniform hypergraphs.In particular we reduce the \(H\)-coloring problem for graphs to this problem, where \(H\) is a graph depending on \(\rho\). We also discuss the links of this problem with the problem of
finding a completeness criterion for finite algebras.

Let \( {Z}_k\) be the cyclic group of order \( k\). Let \( H\) be a graph. A function \( c: E(H) \to {Z}_k\) is called a \( {Z}_k\)-coloring of the edge set \( E(H)\) of \(H\). A subgraph \( G \subseteq H\) is called zero-sum (with respect to a \( {Z}_k\)-coloring) if \( \sum_{e \in E(G)} c(e) \equiv 0 \pmod{k}\). Define the zero-sum Turán numbers as follows. \( T(n, G, {Z}_k)\) is the maximum number of edges in a \( {Z}_k\)-colored graph on \( n\) vertices, not containing a zero-sum copy of \( G\). Extending a result of [BCR], we prove:

THEOREM.
Let \( m \geq k \geq 2\) be integers, \( k | m\). Suppose \( n > 2(m-1)(k-1)\), then
\[T(n,K_{1,m},{Z}_k) =
\left\{
\begin{array}{ll}
\frac{(m+k-2)-n}{2}-1, & if \;\; n-1 \equiv m \equiv k \equiv 0 \pmod{2}; \\
\lfloor \frac{(m+k-2)-n}{2} \rfloor, & otherwise.
\end{array}
\right.\]

A tricover of pairs by quintuples on a \(v\)-element set \(V\) is a family of 5-element subsets of \(V\), called blocks, with the property that every pair of distinct elements of \(V\) occurs in at least three blocks. If no other such tricover has fewer blocks, the tricover is said to be minimum, and the number of blocks in a minimum tricover is the tricovering number \(C_3(v,5,2)\), or simply \(C_3(v)\). It is well known that \(C_3(v) \geq \lceil \frac{{v} \lceil \frac {3(v-1)}{4} \rceil} {5} \rceil = B_3(v)\), where \(\lceil x\rceil\) is the smallest integer that is at least \(x\). It is shown here that if \(v \equiv 1 \pmod{4}\), then \(C_3(v) = B_3(v) + 1\) for \(v \equiv 9\) or \(17 \pmod{20}\), and \(C_3(v) = B_3(v)\) otherwise.

We investigate collections \( {H} = \{H_1, H_2, \ldots, H_m\}\) of pairwise disjoint \(w\)-subsets \(H_i\) of an \(r\)-dimensional vector space \(V\) over \( {GF}(q)\) that arise in the construction of byte error control codes. The main problem is to maximize \(m\) for fixed \(w, r,\) and \(q\) when \({H}\) is required to satisfy a subset of the following properties: (i) each \(H_i\) is linearly independent; (ii) \(H_i \cap H_j = \{0\}\) if \(i \neq j\); (iii) \((H_i) \cap (H_j) = \{0\}\) if \(i \neq j\);( iv) any two elements of \(H_i \cup H_j\) are linearly independent;(v) any three elements of \(H_1 \cup H_2 \cup \cdots \cup H_m\) are linearly independent.
Here \((x)\) denotes the subspace of \(V\) spanned by \(X\). Solutions to these problems yield linear block codes which are useful in controlling various combinations of byte and single bit errors in computer memories. For \(r = w + 1\) and for small values of \(w\) the problem is solved or nearly solved. We list a variety of methods for constructing such partial partitions and give several bounds on \(m\).

There is a conjecture of Golomb and Taylor that asserts that the Welch construction for Costas sequences with length \(p-1\), \(p\) prime, is the only one with the property of single periodicity.

In the present paper we present and prove a weaker conjecture: the Welch construction is the only one with the property that its differences are a shift of the original sequence.

In this paper we give a necessary condition for the Steiner system \(S(3,4,16)\) obtained from a one-point extension of the points and lines of \( {PG}(3,2)\) to be further extendable to a Steiner system \(S(4,5,17)\).

The edge-toughness \(\tau_1(G)\) of a graph \(G\) is defined as

\[\tau_1(G) = \min\left\{\frac{|E(G)|}{w(G-X)} \mid X { is an edge-cutset of } G\right\},\]

where \(w(G-X)\) denotes the number of components of \(G-X\). Call a graph \(G\) balanced if \(\tau_1(G) = \frac{|E(G)|}{w(G-E(G))-1}\). It is known that for any graph \(G\) with edge-connectivity \(\lambda(G)\),
\(\frac{\lambda(G)}{2} < \tau_1(G) \leq \lambda(G).\) In this paper we prove that for any integer \(r\), \(r > 2\) and any rational number \(s\) with \(\frac{r}{2} < s \leq r\), there always exists a balanced graph \(G\) such that \(\lambda(G) = r\) and \(\tau_1(G) = s\).

Using the permutation action of the group \( {PSL}_2(2^m)\) on its dihedral subgroups of order \(2(2^m + 1)\) for the description of the class of designs \(W(2^m)\) derived from regular ovals in the Desarguesian projective plane of order \(2^m\), we construct a \(2\)-design of ovals for \(W(2^m)\) for \(m \geq 3\), and thus determine certain properties of the binary codes of these classes of designs.

We give a complete solution to the intersection problem for a pair of Steiner systems \(S(2,4,v)\), leaving a handful of exceptions when \(v = 25, 28,\) {and } \(37\).

A scheme for classifying hamiltonian cycles in \(P_m \times P_n\), is introduced.We then derive recurrence relations, exact and asymptotic values for the number of hamiltonian cycles in \(P_4 \times P_n\) and \(P_5 \times P_n\).

If each pair of vertices in a graph \(G\) is connected by a long path, then the cycle space of \(G\) has a basis consisting of long cycles. We propose a conjecture regarding the above relationship. A few results supporting the conjecture are given.

For any tree \(T\), let \(\gamma(T)\) represent the size of a minimum dominating set. Let \({E}_0\) represent the collection of trees with the property that, regardless of the choice of edge \(e\) belonging to the tree \(T\), \(\gamma(T – e) = \gamma(T)\). We present a constructive characterization of \({E}_0\).

A procedure based on the Kronecker product yields \(\pm 1\)-matrices \(X,Y\) of order \(8mn\), satisfying
\(XX^t + YY^t = 8mnI \quad {and} \quad XY^t = YX^t = 0,\)
given Hadamard matrices of orders \(4m\) and \(4n\). This allows the construction of some infinite classes of Hadamard matrices – and in particular orders \(8mnp\), for values of \(p\) including (for \(j \geq 0\)) \(5, 9^j, 25, 9^j, \), improving the usual Kronecker product construction by at least a factor of \(2\). A related construction gives Hadamard matrices in orders \(4 \cdot 5^i \cdot 9^j, 0 \leq i \leq 4\). To this end we introduce some disjoint weighing matrices and exploit certain Williamson matrices studied by Turyn and Xia. Some new constructions are given for symmetric and skew weighing matrices, resolving the case of skew \(W(N, 16)\) for \(N = 30, 34, 38\).

The set of Lyndon words of length \(N\) is obtained by choosing those strings of length \(n\) over a finite alphabet which are lexicographically least in the aperiodic equivalence classes determined by cyclic permutation. We prove that interleaving two Lyndon words of length \(n\) produces a Lyndon word of length \(2n\). For the binary alphabet \(\{0, 1\}\) we represent the set of Lyndon words of length \(n\) as vertices of the \(n\)-cube. It is known that the set of Lyndon words of length \(n\) form a connected subset of the \(n\)-cube. A path of vertices in the \(n\)-cube is a list of strings of length \(n\) in which adjacent strings differ in a single bit. Using paths of Lyndon words in the \(n\)-cube we construct longer paths of Lyndon words in higher order cubes by shuffling and concatenation.

A tricover of pairs by quintuples of a \(v\)-set \(V\) is a family of \(5\)-subsets of \(V\) (called blocks) with the property that every pair of distinct elements from \(V\) occurs in at least three blocks. If no other such tricover has fewer blocks, the tricover is said to be minimum, and the number of blocks in a minimum tricover is the covering number \(C_3(v, 5, 2)\), or simply \(C_3(v)\). It is well known that\(C_3(v) \geq \lceil \frac{{v} \lceil \frac {3(v-1)}{4} \rceil} {5} \rceil = B_3(v)\) , where \(\lceil x \rceil\) is the least integer not less than \(x\). It is shown here that if \(v \equiv 0 \pmod{4}\) and \(v \geq 8\), then \(C_3(v) = B_3(v)\).

The concept of rectangular designs with varying replicates is introduced. A class of such designs is constructed with an example.

We study the isomorphic factorization of complete bipartite graphs into trees. It is known that for complete bipartite graphs, the divisibility condition is also a sufficient condition for the existence of isomorphic factorization. We give necessary and sufficient conditions for the divisibility, that is, necessary and sufficient conditions for a pair \([m,n]\) such that \(mn\) is divisible by \((m+n-1)\), and investigate structures of the set of pairs \([m,n]\) satisfying divisibility. Then we prove that the divisibility condition is also sufficient for the existence of an isomorphic tree factor of a complete bipartite graph by constructing the tree dividing \(K({m,n})\).