We introduce a \( k \)-response set as a set of vertices where responders can be placed so that given any set of \( k \) emergencies, these responders can respond, one per emergency, where each responder covers its own vertex and its neighbors. A weak \( k \)-response set does not have to worry about emergencies at the vertices of the set. We define \( R_k \) and \( r_k \) as the minimum cardinality of such sets. We provide bounds on these parameters and discuss connections with domination invariants. For example, for a graph \( G \) of order \( n \) and minimum degree at least \( 2 \), \( R_2(G) \leq \frac{2n}{3} \), while \( r_2(G) \leq \frac{n}{2} \) provided \( G \) is also connected and not \( K_3 \). We also provide bounds for trees \( T \) of order \( n \). We observe that there are, for each \( k \), trees for which \( r_k(T) \leq \frac{n}{2} \), but that the minimum \( R_k(T) \) appears to grow with \( k \); a novel computer algorithm is used to show that \( R_3(T) > \frac{n}{2} \). As expected, these parameters are NP-hard to compute, and we provide a linear-time algorithm for trees for fixed \( k \).

Suppose \( 2n \) voters vote sequentially for one of two candidates. For how many such sequences does one candidate have strictly more votes than the other at each stage of the voting? The answer is \( \binom{2n}{n} \) and, while easy enough to prove using generating functions, for example, only three combinatorial proofs exist, due to Kleitman, Gessel, and Callan. In this paper, we present two new bijective proofs.

In [10], Fink and Jacobson gave a generalization of the concepts of domination and independence in graphs which extends only partially the well-known inequality chain \( \gamma(G) \leq i(G) \leq \beta(G) \leq \Gamma(G) \) between the usual parameters of domination and independence. If a \( k \)-independent set is defined as a subset of vertices inducing in \( G \) a subgraph of maximum degree less than \( k \), we introduce the property which makes a \( k \)-independent set maximal. This leads us to the notion of a \( k \)-star-forming set. The corresponding parameters \( sf_k(G) \) and \( \text{SF}_k(G) \) satisfy \( sf_k(G) \leq i_k(G) \leq \beta_k(G) \leq \text{SF}_k(G) \) where \( i_k(G) \) and \( \beta_k(G) \) are respectively the minimum and the maximum cardinality of a maximal \( k \)-independent set. We initiate the study of \( sf_k(G) \) and \( \text{SF}_k(G) \) and give some results in particular classes of graphs such as trees, chordal graphs, and \( K_{1,r} \)-free graphs.

If \( D \) is a digraph, \( \delta \) its minimum degree, and \( \lambda \) its edge-connectivity, then \( \lambda \leq \delta \). A digraph \( D \) is called super-edge-connected or super-\( \lambda \) if every minimum edge-cut consists of edges adjacent to or from a vertex of minimum degree. Clearly, if \( D \) is super-\( \lambda \), then \( \lambda = \delta \). A digraph without any directed cycle of length \( 2 \) is called an oriented graph. Sufficient conditions for digraphs to be super-edge-connected were given by several authors. However, closely related results for oriented graphs have received little attention until recently. In this paper, we will present some degree sequence conditions for oriented graphs as well as for oriented bipartite graphs to be super-edge-connected.

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.