Let $G$ be a simple graph, and let $p$ be a positive integer. A subset $D\subseteq V(G)$ is a $p$-$dominatingset$ of the graph $G$ if every vertex $v\in V(G)–D$ is adjacent to at least $p$ vertices of $D$. The $p$-$dominationnumber$ ${\gamma }_p(G)$ is the minimum cardinality among the $p$-dominating sets of $G$. Note that the $1$-domination number ${\gamma }_1(G)$ is the usual $dominationnumber$ $\gamma (G)$.
In $1985$, Fink and Jacobson showed that for every graph $G$ with $n$ vertices and $m$ edges the inequality $y$,${\gamma }_p(G)\ge n—m/p$ holds. In this paper we present a generalization of this theorem and analyze the $2$-domination number ${\gamma }_2$ in cactus graphs $G$ with respect on its relation to the matching number ${\alpha }_0$ and the number of odd or rather even cycles in $G$. Further we show that ${\gamma }_2(G)\ge \alpha (G)$ for the cactus graphs $G$ with at most one even cycle and characterize those which
fulfill ${\gamma }_2(G)=\alpha (G)$ or rather ${\gamma }_2(G)=\alpha (G)+1$.

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)\le \frac{2n}{3}$, while $r_2(G)\le \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)\le \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 $(\genfrac{}{}{0ex}{}{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)\le i(G)\le \beta (G)\le \mathrm{\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 $s{f}_k(G)$ and ${\text{SF}}_k(G)$ satisfy $s{f}_k(G)\le i_k(G)\le {\beta }_k(G)\le {\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 $s{f}_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 \le \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|\ge |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,\dots ,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}\ge {\theta }_i\ge {\lambda }_{i+r}$. For the standard Laplacian we have ${\lambda }_i\ge {\theta }_i\ge {\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\ge {\theta }_i\ge {\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 $generalizeddie$ is a list $(x_1,\dots ,x_n)$ of integers. For integers $n\ge 1,a\le b$ and $s$, let $D(n,a,b,s)$ be the set of all dice with $a\le x_1\le \dots \le x_n\le 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\ne 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(\mathrm{mod}16)$. It is shown here that their methodology can be generalized completely to deal with primes of the form $p\equiv (2^k+1)(\mathrm{mod}{2}^{k+1})$, $k\ge 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\ge 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.