Results are presented on the eternal domination problem: defending a graph from an infinite sequence of attacks, so that each attack is defended by a guard at most distance one from the attack. We first consider the model where at most one guard moves to defend an attack. Our focus is on the relationship between the number of guards and the independence and clique covering numbers of the graph. We establish results concerning which triples of these parameters can be attained by some graph, and determine the exact value of the number of guards for graphs in certain classes. We then turn our attention to the variant of the problem in which every guard can relocate to an adjacent vertex in defence of an attack. We give a linear algorithm to determine the minimum number of guards necessary to defend a tree, and use it to answer another question about defending trees.

A \({generalized\; die}\) is a list \( (x_1,\ldots,x_n) \) of integers. For integers \( n \geq 1, a \leq b \) and \( s \), let \( D(n,a,b,s) \) be the set of all dice with \( a \leq x_1 \leq \ldots \leq x_n \leq b \) and \( \sum x_i = s \). Two dice \( X \) and \( Y \) are \({tied}\) if the number of pairs \( (i,j) \) with \( x_i y_j \). We prove the following: with one exception (unique up to isomorphism), if \( X \neq Y \in D(n,a,b,s) \) are tied dice neither of which ties all other elements of \( D(n,a,b,s) \), then there is a third die \( Z \in D(n,a,b,s) \) which ties neither \( X \) nor \( Y \).

I. Anderson and L. Ellison [7] demonstrated the existence of \( Z \)-cyclic Directed Triplewhist Tournament Designs and \( Z \)-cyclic Ordered Triplewhist Tournament Designs for all primes \( p \equiv 9 \pmod{16} \). It is shown here that their methodology can be generalized completely to deal with primes of the form \( p \equiv (2^k + 1) \pmod{2^{k+1}} \), \( k \geq 4 \).

An \( \mathbb{L}(n,d) \) is a linear space with constant point degree \( n+1 \), lines of size \( n \) and \( n-d \), and with \( v = n^2 – d \) points. Denote by \( b = n^2 + n + z \) the number of lines of an \( \mathbb{L}(n,d) \), then \( z \geq 0 \) and examples are known only if \( z = 0, 1 \) [7]. The linear spaces \( \mathbb{L}(n, d) \) were introduced in [7] in relation with some classification problems of finite linear spaces. In this note, starting from the symmetric configuration \( 45_7 \) of Baker [1], we give an example of \( \mathbb{L}(n,d) \), with \( n=7, d=4 \) and \( z=4 \).

We propose a multilevel cooperative search algorithm to compute upper bounds for \( C_\lambda(v,k,t) \), the minimum number of blocks in a \( t-(v,k,\lambda) \) covering design. Multilevel cooperative search is a search heuristic combining cooperative search and multilevel search. We first introduce a coarsening strategy for the covering design problem which defines reduced forms of an original \( t-(v,k,\lambda) \) problem for each level of the multilevel search. A new tabu search algorithm is introduced to optimize the problem at each level. Cooperation operators between tabu search procedures at different levels include new re-coarsening and interpolation operators. We report the results of tests that have been conducted on \( 158 \) covering design problems. Improved upper bounds have been found for \( 34 \) problems, many of which exhibit a tight gap. The proposed heuristic appears to be a very promising approach to tackle other similar optimization problems in the field of combinatorial design.

A Steiner tree for a set \( S \) of vertices in a connected graph \( G \) is a connected subgraph of \( G \) of smallest size that contains \( S \). The Steiner interval \( I(S) \) of \( S \) is the union of all vertices of \( G \) that belong to some Steiner tree for \( S \). A graph is strongly chordal if it is chordal and has the property that every even cycle of length at least six has an odd chord. We develop an efficient algorithm for finding Steiner intervals of sets of vertices in strongly chordal graphs.

A legal placement of Queens is any placement of Queens on an order \(N\) chessboard in which any two attacking Queens can be separated by a Pawn. The Queens’ independence separation number is the minimum number of Pawns which can be placed on an \(N \times N\) board to result in a separated board on which a maximum of \(m\) independent Queens can be placed. We prove that \(N + k\) Queens can be separated by \(k\) Pawns for large enough \(N\) and provide some results on the number of fundamental solutions to this problem. We also introduce separation relative to other domination-related parameters for Queens, Rooks, and Bishops.