Temporal load-balancing – “spreading out” the executions of tasks over time — is desirable in many applications. A form of temporal load-balancing is introduced: scheduling to maximize minimum inter-completion time (MICT-scheduling). It is shown that MICT-scheduling is, in general, NP-hard. A number of restricted classes of task systems are identified, which can be efficiently MICT-scheduled.

Given a finite-dimensional vector space \(V\) over a finite field \(F\) of odd characteristic, and equipping \(V\) with an orthogonal (symplectic, unitary) geometry, the following two questions are considered:

1. Given some linearly independent vectors \(w_1, w_2, \ldots, w_k \in V\) and the \(k \times k\) matrix \(A = (\langle w_i, w_j\rangle)\), and given scalars \(\alpha_1, \alpha_2, \ldots, \alpha_k, \beta \in F\), how many vectors \(v \in V\), not in the linear span of \(w_1, w_2, \ldots, w_k\), satisfy \(\langle w_i, v\rangle = \alpha_i\) (\(i = 1, 2, \ldots, k\)) and \(\langle v, v\rangle = \beta\)?
2. Given a \(k \times k\) matrix \(A = (\lambda_{ij})\) with entries from \(F\), how many \(k\)-tuples \((v_1, v_2, \ldots, v_k)\) of linearly independent vectors from \(V\) satisfy \(\langle v_i, v_j\rangle = \lambda_{ij}\) (\(i, j= 1, 2, \ldots k\))?

An exact answer to the first question is derived. Here there are two cases to consider, depending on whether or not the column vector \((\alpha_i)\) is in the column space of \(A\). This result can then be applied iteratively to address the second question.

Let \(G\) be a finite graph and let \(\mu\) be an eigenvalue of \(G\) of multiplicity \(k\). A star set for \(\mu\) may be characterized as a set \(X\) of \(k\) vertices of \(G\) such that \(\mu\) is not an eigenvalue of \(G – X\). It is shown that if \(G\) is regular then \(G\) is determined by \(\mu\) and \(G – X\) in some cases. The results include characterizations of the Clebsch graph and the Higman-Sims graph.

We modify the Knuth-Klingsberg Gray code for unrestricted integer compositions to obtain a Gray code for integer compositions each of whose parts is bounded between zero and some positive integer. We also generalize Ehrlich’s method for loop-free sequencing to implement this Gray code in \(O(1)\) worst-case time per composition. The \((n-1)\)-part compositions of \(r\) whose \(i\)th part is bounded by \(n-i\) are the inversion vectors of the permutations of \(\{1,\ldots,n\}\) with \(r\) inversions; we thus obtain a Gray code and a loop-free sequencing algorithm for this set of permutations.

The following problem was introduced at a conference in 1995. Fires start at \(F\) nodes of a graph and \(D\) defenders (firefighters) then protect \(D\) nodes not yet on fire. Then the fires spread to any neighbouring unprotected nodes. The fires and the firefighters take turns until the fires can no longer spread. We examine two cases: when the fires erupt at random and when they start at a set of nodes which allows the fires to maximize the damage. In the random situation, for a given number of nodes, we characterize the graphs which minimize the damage when \(D = F = 1\) and we show that the Star is an optimal graph for \(D = 1\) regardless of the value of \(F\). In the latter case, optimal graphs are given whenever \(D\) is at least as large as \(F\).

In this paper, we are concerned with the existence of sets of mutually quasi-orthogonal Latin squares (MQOLS). We establish a correspondence between equidistant permutation arrays and MQOLS, which has facilitated a computer search to identify all sets of MQOLS of order \(\leq 6\). In particular, we report that the maximum number of Latin squares of order 6 in a mutually quasi-orthogonal set is 3, and give an example of such a set. We also report on a non-exhaustive computer search for sets of 3 MQOLS of order 10, which, whilst not identifying such a set, has led to the identification of all the resolutions of each \((10, 3, 2)\)-balanced incomplete block design. Improvements are given on the existence results for MQOLS based on groups, and a new construction is given for sets of MQOLS based on groups from sets of mutually orthogonal Latin squares based on groups. We show that this construction yields sets of \(2^n – 1\) MQOLS of order \(2^n\), based on two infinite classes of groups. Finally, we give a new construction for difference matrices from mutually quasi-orthogonal quasi-orthomorphisms, and use this to construct a \((2^n, 2^n; 2)\)-difference matrix over \({C}_2^{n-2} \times {C}_4\).

For a countable bounded principal ideal poset \(P\) and a natural number \(r\), there exists a countable bounded principal ideal poset \(P’\) such that for an arbitrary \(r\)-colouring of the points (resp. two-chains) of \(P’\), a monochromatically embedded copy of \(P\) can be found in \(P’\). Moreover, a best possible upper bound for the height of \(P’\) in terms of \(r\) and the height of \(P\) is given.

A vertex set \(S \subseteq V(G)\) is a perfect code or efficient dominating set for a graph \(G\) if each vertex of \(G\) is dominated by \(S\) exactly once. Not every graph has an efficient dominating set, and the efficient domination number \(F(G)\) is the maximum number of vertices one can dominate given that no vertex is dominated more than once. That is, \(F(G)\) is the maximum influence of a packing \(S \subseteq V(G)\). In this paper, we begin the study of \(LF(G)\), the lower efficient domination number of \(G\), which is the minimum number of vertices dominated by a maximal packing. We show that the decision problem associated with deciding if \(LF(G) \leq K\) is an NP-complete problem. The principal result is a characterization of trees \(T\) where \(LF(T) = F(T)\).

We introduce a new class of colorings of graphs and define and study two new graph coloring parameters. A \({coloring}\) of a graph \(G = (V,E)\) is a partition \(\Pi = \{V_1, V_2, \ldots, V_k\}\) of the vertices of \(G\) into independent sets \(V_i\), or \({color\; classes}\). A vertex \(v_i \in V_i\) is called \({colorful}\) if it is adjacent to at least one vertex in every color class \(V_j\), \(i \neq j\). A \({fall \;coloring}\) is a coloring in which every vertex is colorful. If a graph \(G\) has a fall coloring, we define the \({fall\; chromatic\; number}\) (\({fall \;achromatic\; number}\)) of \(G\), denoted \(\chi_f(G)\), (\(\psi_f(G)\)) to equal the minimum (maximum) order of a fall coloring of \(G\), respectively. In this paper, we relate fall colorings to other colorings of graphs and to independent dominating sets in graphs.

This paper revises Park’s proof of Shannon inequality and also gives a new simple proof.