In this paper we present an efficient exhaustive search strategy on symmetric Boolean functions having the Walsh spectrum values constrained in a range at certain points. Exploiting the structure in Walsh spectrum of a symmetric Boolean function and its relationship with Krawtchouk matrix, we extend the concept of folded vectors and pruning introduced by Gathen and Roche in 1997. The strategy is applied to search for highly nonlinear symmetric Boolean functions and nonlinear symmetric resilient and correlation immune functions. We also experimentally justify that our method provides further efficiency than the search strategy presented by Gathen and Roche.

In 2001, Kristiansen, Hedetniemi, and Hedetniemi [9] first defined the concept of a defensive alliance in a graph, to be a subset \( S \subset V \) of a graph \( G = (V,E) \) having the property that every vertex \( v \in S \) has at most one more neighbor in \( V \setminus S \) than it has in \( S \) (i.e. \( |N[v] \cap S| \geq |N[v] \setminus S| \)). Since then, several other types of alliances have been defined and studied including strong, offensive, global, powerful, and secure alliances. To date, no algorithms or complexity analyses have been developed for alliances in graphs. This is the subject of this paper.

Wythoff quasigroups are a generalization of Wythoff’s game, which in turn is a modification of nim. This paper studies the algebraic structure of Wythoff quasigroups, and in particular the existence of subquasigroups and the question of isomorphism. It is shown that the quasigroups are mutually non-isomorphic, and that there are few possible subquasigroups. The paper concludes with an application to combinatorial games.

A complete enumeration is given of orientable biembeddings involving five of the \( 80 \) Steiner triple systems of order \( 15 \). As a consequence, it follows that each of the \( 80 \) systems has a biembedding in an orientable surface, and precisely \( 78 \) of the systems have orientable self-embeddings.

Given a graph \( G \), the adjacency matrix \( A(G) \), the standard Laplacian \( L(G) \), and the normalized Laplacian \( \mathcal{L}(G) \) have been studied intensively. In this paper, interlacing inequalities are given for each of these three matrices under the two operations of removing an edge or a vertex from \( G \). Examples are given to show that the inequalities are the best possible of their type. In addition, an interlacing result is proven for the adjacency matrix when two vertices of \( G \) are contracted. Among the results given are the following.

Let \( G \) be a graph and let \( H \) be a graph obtained from \( G \) by removing an edge or a vertex of degree \( r \). Let \( \lambda_i \), \( i = 1, 2, \ldots, n \) be the eigenvalues associated with \( A(G) \), \( L(G) \), or \( \mathcal{L}(G) \) and let \( \theta_i \) be the eigenvalues associated with \( A(H) \), \( L(H) \), or \( \mathcal{L}(H) \), where both sets of eigenvalues are in nonincreasing order.

In the case of removing a vertex so that \( H = G – v \), for the normalized Laplacian we have \( \lambda_{i – r + 1} \geq \theta_i \geq \lambda_{i+r} \). For the standard Laplacian we have \( \lambda_i \geq \theta_i \geq \lambda_{i+r} \). In the case of removing an edge so that \( H = G – e \), where \( e \) is an edge incident on a vertex of degree \( 1 \), for the normalized Laplacian we have \( \lambda_i \geq \theta_i \geq \lambda_{i+1} \).

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.