With the help of a computer, the third Ramsey number is determined for each of the \(25\) graphs with five edges, five or more vertices, and no trivial components.

In this paper, we prove that the size Ramsey number

\[\hat{r}(a_1K_{1,n_1}, a_2K_{1,n_2}, \ldots ,a_\ell K_{1,n_\ell}) = \left[\sum\limits_{i=1}^\ell {(a_i – 1)+1} \right] \left[\sum\limits_{i=1}^\ell {(n_i – 1)+1} \right].\]

We consider the following three problems: Given a graph \(G\),

1. What is the smallest number of cliques into which the edges of \(G\) can be partitioned?
2. How many cliques are needed to cover the edges of \(G\)?
3. Can the edges of \(G\) be partitioned into maximal cliques of \(G\)?

All three problems are known to be NP-complete for general \(G\). We show here that: (1) is NP-complete for \(\Delta(G) \geq 5\), but can be solved in polynomial time if \(\Delta(G) \leq 4\) (the latter has already been proved by Pullman \([P]\)); (2) is NP-complete for \(\Delta(G) \geq 6\), and polynomial for \(\Delta(G) \leq 5\); (3) is NP-complete for \(\Delta(G) \geq 8\) and polynomial time for \(\Delta(G) \leq 7\).

The total chromatic number \(\chi_2(G)\) of a graph \(G\) is the smallest number of colors which can be assigned to the vertices and edges of \(G\) so that adjacent or incident elements are assigned different colors. For a positive integer \(m\) and the star graph \(K_{1,n}\), the mixed Ramsey number \(\chi_2(m, K_{1,n})\) is the least positive integer \(p\) such that if \(G\) is any graph of order \(p\), either \(\chi_2(G) \geq m\) or the complement \(\overline{G}\) contains \(K_{1,n}\) as a subgraph.
In this paper, we introduce the concept of total chromatic matrix and use it to show the following lower bound: \(\chi_2(m, K_{1,n}) \geq m + n – 2\) for \(m \geq 3\) and \(n \geq 1\). Combining this lower bound with the known upper bound (Fink), we obtain that \(\chi_2(m, K_{1,n}) = m + n – 2\) for \(m\) odd and \(n\) even, and \(m + n – 2 \leq \chi_2(m, K_{1,n}) \leq m + n – 1\) otherwise.

An addition-multiplication magic square of order \(n\) is an \(n \times n\) matrix whose entries are \(n^2\) distinct positive integers such that not only the sum but also the product of the entries in each row, column, main diagonal, and back diagonal is a constant. It is shown in this paper that such a square exists for any order \(mn\), where \(m\) and \(n\) are positive integers and \(m, n \notin \{1, 2, 3, 6\}\).

A hypergraph is irregular if no two of its vertices have the same degree. It is shown that for all \(r \geq 3\) and \(n \geq r + 3\), there exist irregular \(r\)-uniform hypergraphs of order \(n\). For \(r \geq 6\) it is proved that almost all \(r\)-uniform hypergraphs are irregular. A linear upper bound is given for the irregularity strength of hypergraphs of order \(n\) and fixed rank. Furthermore, the irregularity strength of complete and complete equipartite hypergraphs is determined.

It is proven that for all \(v \equiv 1 \mod 3\), \(v \geq 7\) there is a \(2-(v,4,2)\) design whose blocks have pairwise at most two elements in common. Moreover, for \(v \equiv 1, 4 \mod 12\) we have shown that these designs can be generated by two copies of \(2-(v,4,1)\) designs.

Lyndon graphs are connected subgraphs of the \(n\)-cube which arise in the combinatorics of words. It is shown that these graphs are not Hamiltonian when \(n\) is even.

We consider the problem of preemptively scheduling a set of \(N\) independent jobs with release times on \(m \geq 1\) identical machines so as to minimize the number of late jobs. For a single machine, Lawler has given an \(O(N^5)\) time algorithm for finding a schedule with the minimum number of late jobs. However, for fixed \(m \geq 2\), the question of whether the problem can be shown to be solvable in polynomial time or shown to be NP-hard remained open over the last decade. In this paper, we answer this question by showing that it is NP-hard for every fixed \(m \geq 2\).

In this note, we give a characterization of regular graphs which are neutral.

It is known that a pair of mutually orthogonal Latin squares (MOLS) of order \(n\) can be embedded in a pair of MOLS of order \(t\) if \(t \geq 3n\). Here, we discuss the prospects of extending this result to the case when the smaller pair is only a pair of mutually orthogonal \({partial}\) Latin squares (MOPLS). We obtain some conditions, analogous to those of Ryser for embedding partial Latin squares in complete Latin squares, which we show are necessary for the embedding of MOPLS. We discuss also some implications if these conditions are, in fact, also sufficient.

We also discuss the analogous problem for pairs of partial Kirkman triple systems (PKTS).

If the non-zero entries of an incidence matrix \(X\) of BIBD\((v, b, r, k, 2)\) have been signed to produce a \((0, 1, -1)\) matrix \(Y\0 such that

\[YY^T = rI_v,\]

then we say it has been signed. The resulting matrix \(Y\) is said to be a Bhaskar Rao design BRD\((v, k, 2)\). We discuss the complexity of two signing problems, (i) Given \(v\), \(k\), and \(\lambda\), decide whether there is a BRD\((v, k, 2\lambda)\), (ii) Given a BIBD\((v, k, 2\lambda)\), decide whether it is signable.
The paper describes related optimisation problems. We show that the signing problems are equivalent to finding the real roots of certain multi-variable polynomials. Then we describe some linear constraints which reduce the size of the second problem, we show certain special cases have polynomial complexity, and we indicate how in some cases the second problem can be decomposed into smaller independent problems. Finally, we characterise signable Steiner triple systems in terms of their block-intersection graphs, and show that the complexity of deciding whether a twofold triple system can be signed is linear in the number of blocks.

Four \((1, -1, 0)\)-matrices of order \(m\), \(X = (x_{ij})\), \(Y = (y_{ij})\), \(Z = (z_{ij})\), \(U = (u_{ij})\) satisfying

1. \(XX^T + YY^T + ZZ^T + UU^T= 2mI_m\),
2. \(x_{ij}^2 + y_{ij}^2 + z_{ij}^2 + u_{ij}^2 = 2, i,j = 1,\ldots,m\),
3. \(X, Y, Z, U\) mutually amicable,

will be called semi Williamson type matrices of order \(m\). In this paper, we prove that if there exist Williamson type matrices of order \(n_1, \ldots, n_k\), then there exist semi Williamson type matrices of order \(N = \prod_{j=1}^k n_j^{r_j}\), where \(r_j\) are non-negative integers. As an application, we obtain a \(W(4N, 2N)\).
Although the paper presents no new \(W(4n, 2n)\) for \(n\) odd, \(n < 3000\), it is a step towards proving the conjecture that there exists a \(W(4n, 2n)\) for any positive integer \(n\). This conjecture is a sub-conjecture of the Seberry conjecture \([4, page 92]\) that \(W(4n, k)\) exist for all \(k = 0, 1, \ldots, 4n\). In addition, we find infinitely many new \(W(2n, n)\), \(n\) odd and the sum of two squares.

A multi-set design of order \(v\), \({MB}_t(v, k, \lambda)\), first defined by Assaf, Hartman, and Mendelsohn, is an ordered pair \((V, B)\), where \(V\) is a set of cardinality \(v\) and \(B\) is a collection of multi-subsets of \(V\) of size \(k\) (called blocks), with the property that every multi-subset of \(V\) of size \(t\) is contained a total of \(\lambda\) times in the blocks of \(B\). (For example, the multi-set \(\{a,b,b\}\) is contained \(\binom{2}{1}\binom{4}{2} = 12\) times in the multi-set \(\{a,a,b,b,b,b,c\}\) and not at all in the multi-set \(\{a,a,b,c\}\).) Previously, the first author had pointed out that any \(t\)-multi-set design is a \(1\)-design. Here, we show the pleasant yet not obvious fact that any \(t\)-multi-set design is a \(t’\)-multi-set design for any positive integer \(t’ \leq t\).

In this paper, we introduce the concept of node expansion. Node expansion is a generalization of edge subdivision and an inverse of subgraph contraction. A graph \(G_1 = (V_1, E_1)\) is an \(H\)-node expansion of \(G = (V, E)\) if and only if \(G_1\) contains a subgraph \(H = (V_H, E_H)\) such that \(V = V_1 – V_H \cup \{v\}\) and \(E = E_1 – E_H \cup \{vw | wh \in E_1 \;\text{and}\; h \in V_H\} \cup \{v\}\). The concept of node expansion is of considerable importance in modernization of networks.

We consider the node expansion problem of transforming a graph to a bipartite graph with a minimum number of node expansions using \(K_2\). We show that the \(K_2\)-node expansion problem is NP-Complete for general graphs and remains so if the input graph has maximum degree 3. However, we present a \(O({n}^2 \log n + mn + p^3)\) algorithm for the case when the input graph is restricted to be planar \(3\)-connected and output graph is required to be planar bipartite.

An algorithm is presented for finding all \((0,1)\)-solutions to the matrix problem \(AX = J\), where \(A\) is a \((0,1)\)-matrix and \(J\) is the all \(1\)’s column vector. It is applied to the problem of enumerating distinct cyclic Steiner systems and five new values are obtained. Specifically, the number of distinct solutions to \(S(2,3,55), S(2,3,57), S(2,3,61), S(2,3,63)\), and \(S(3,4,22)\) are \(121,098,240, 84,672,512, 2,542,203,904, 1,782,918,144\), and \(1140\), respectively.

Let \(g_k(n) = \sum_{\underline{v}\in C_k(n)} \binom{n}{v} 2^{v_1v_2 + v_2v_3 + v_3v_4 + \ldots +v_{k-1}v_k}\) where \(C_k(n)\) denote the set of \(k\)-compositions of \(n\). We show that

1. \(g_k(n+p-1) \equiv g_k(n) \pmod{p}\) for all \(k,n \geq 1\), prime \(p\);
2. \(g_k(n)\) is a polynomial in \(k\) of degree \(n\) for \(k \geq n+1\);

and, moreover, that these properties hold for wider classes of functions which are sums involving multinomial coefficients.