In this paper, scheduling problems with communication delays are considered. Formally, we are given a partial order relation \(\prec\) on a set of tasks \(T\), a set of processors \(P\), and a deadline \(d\). Supposing that a unit communication delay between two tasks \(a\) and \(b\) such that \(a \prec b\) occurs whenever \(a\) and \(b\) are scheduled on different processors, the question is: Can the tasks of \(T\) be scheduled on \(P\) within time \(d\)? It is shown here that the problem is NP-complete even if \(d = 4\). Also, for an unlimited number of processors, C. Picouleau has shown that for \(d = 8\) the problem is NP-complete. Here it is shown that it remains NP-complete for \(d \geq 6\) but is polynomially solvable for \(d < 6\), which closes the gap between P and NP for this problem, as regards the deadline.

Let \(V\) be a finite set of order \(v\). A \((v, k, \lambda)\) covering design of index \(\lambda\) and block size \(k\) is a collection of \(k\)-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, k, \lambda)\), in a covering design. It is well known that \(\alpha(v,k,\lambda) \geq \lceil\frac{v}{k}\lceil\frac{v-1}{k-1}\lambda\rceil\rceil = \phi(v, k, \lambda)\), where \(\lceil x \rceil\) is the smallest integer satisfying \(x \leq \lceil x \rceil\). It is shown here that \(\alpha(v,5,7) = \phi(v, 5, 7)\) for all positive integers \(v \geq 5\) with the possible exception of \(v = 22, 28, 142, 162\).

A graph \(G\) is called \(k\)-critical if \( \chi (G) = k\) and \( \chi (G – e) k\) is at most \(n – k + 3\) if \(k \leq 7\).

Let \(g\) and \(f\) be integer-valued functions defined on \(V(G)\) with \(f(v) \geq g(v) \geq 1\) for all \(v \in V(G)\). A graph \(G\) is called a \((g, f)\)-graph if \(g(v) \leq d_G(v) \leq f(v)\) for each vertex \(v \in V(G)\), and a \((g, f)\)-factor of a graph \(G\) is a spanning \((g, f)\)-subgraph of \(G\). A graph is \((g, f)\)-factorable if its edges can be decomposed into \((g, f)\)-factors.
The purpose of this paper is to prove the following three theorems: (i) If \(m \geq 2\), every \(\left((2mg+2m-2)t+(g+1)s, (2mf-2m+2)t+(f-1)s\right)\)-graph \(G\) is \((g, f)\)-factorable. (ii) Let \(g(x)\) be even and \(m > 2\). (1) If \(m\) is even, and \(G\) is a \(\left((2mg+2)t+(g+1)s, (2mf-2m+4)t+(f-1)s\right)\)-graph, then \(G\) is \((g, f)\)-factorable; (2) If \(m\) is odd, and \(G\) is a \(((2mg+4)t+(g+1)s$, $(2mf-2m+2)t+(f-1)s)\)-graph, then \(G\) is \((g, f)\)-factorable. (iii) Let \(f(x)\) be even and \(m > 2\). (1) If \(m\) is even, and \(G\) is a \(\left((2mg+2m-4)t+(g+1)s, (2mf-2)t+(f-1)s\right)\)-graph, then \(G\) is \((g, f)\)-factorable;
(2) If \(m\) is odd, and \(G\) is a \(((2mg+2m-2)t+(g+1)s\), \((2mf-4)t+(f-1)s)\)-graph, then \(G\) is \((g, f)\)-factorable.
where \(t\), \(m\) are integers and \(s\) is a nonnegative integer.

All Williamson matrices in this Note are symmetric circulants. Eight non-equivalent sets of Williamson matrices of order \(25\) are known. They were discovered by Williamson (\(2\) sets), Baumert and Hall (\(2\) sets), and Sawade (\(4\) sets). Sawade carried out a complete search and reported that there are exactly eight non-equivalent such sets of matrices. Subsequently, this was confirmed by Koukouvinos and Kounias. It is surprising that we have found two more such sets. Hence, there are ten non-equivalent sets of Williamson matrices of order \(25\).

Only three non-equivalent sets of Williamson matrices of order \(37\) were known so far. One of them was discovered by each of Williamson, Turyn, and Yamada. We have found one more such set.

In this paper, we derive and present some necessary conditions for the existence of certain combinatorial arrays (called balanced arrays (\(B\)-arrays)) with two elements by making use of some classical inequalities. We discuss briefly the usefulness of these arrays in combinatorics and statistical design of experiments.

An explicit recurrence is obtained for the clique polynomial of a short ladder in which the two diagonals are drawn in each cell. From this result, an explicit formula for the number of decompositions of the ladder into triangles and \(4\)-cliques is obtained. The recurrence is then used to obtain results for the matching polynomial of the ladder. Finally, an association is made with a particular tiling problem.

Let \(G\) be a finite graph and \(x\) be its vertex. The \({neighbourhood}\) of \(x\) in \(G\), denoted \(N_G(x)\), is a subgraph of \(G\) induced by all vertices adjacent to \(x\). \(G\) is a \({graph \; with \; a \; constant \; neighbourhood}\) if there exists a graph \(H\) such that \(N_G(x)\) is isomorphic to \(H\) for every vertex \(x\) of \(G\).

We completely characterize graphs with constant neighbourhoods isomorphic to complements of regular disconnected graphs.

A \({numbering}\) of a graph \(G = (V, E)\) is a bijection \(f: V \rightarrow \{1, 2, \ldots, p\}\) where \(|V| = p\). The \({additive \; bandwidth \; of \; numbering}\) \(f\) is \(B^+(G, f) = \max\{|f(u) + f(v) – (p + 1)| : uv \in E\}\), and the \({additive \; bandwidth}\) of \(G\) is \(B^+(G) = \min\{B^+(G, f) : f \text{ a numbering of } G\}\). Labeling \(V\) by a numbering which yields \(B^+(G)\) has the effect of causing the \(1\)’s in the adjacency matrix of \(G\) to be placed as near as possible to the main counterdiagonal, a fact which offers potential storage savings for some classes of graphs. Properties of additive bandwidth are discussed, including relationships with other graphical invariants, its value for cycles, and bounds on its value for extensions of full \(k\)-ary trees.