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.