In the paper [3], the theorem that at least $\frac{n–1}{2}$ queens are required to dominate the $n\times n$ chessboard was attributed to P. H. Spencer, in [1]. A proof of this result appeared in the earlier work [2].

A set $D$ of vertices in a graph $G$ is irredundant if every vertex $v$ in $D$ has at least one private neighbour in $N[v,G]\setminus N[D\setminus \{v\},G]$. A set $D$ of vertices in a graph $G$ is a minimal dominating set of $G$ if $D$ is irredundant and every vertex in $V(G)\setminus D$ has at least one neighbour in $D$. Further, irredundant sets and minimal dominating sets of maximal cardinality are called $IR$-sets and $\mathrm{\Gamma }$-sets, respectively. A set $I$ of the vertex set of a graph $G$ is independent if no two vertices in $I$ are adjacent, and independent sets of maximal cardinality are called $\alpha$-sets.

In this paper, we prove that bipartite graphs and chordal graphs have a unique $\alpha$-set if and only if they have a unique $\mathrm{\Gamma }$-set if and only if they have a unique $IR$-set. Some related results are also presented.

Static mastermind is like normal mastermind, except that the codebreaker must supply at one go a list of questions (candidate codes), the answers to which must uniquely determine the secret code. We confirm the minimum size list for some small values. Then we solve the game for up to 4 positions. In particular, we show that for $k$ sufficiently large, the minimum size of a list for 4 positions and $k$ colours is $k–1$.

It is shown that for $n\ge 16$, the sum of cardinalities of open irredundant sets in an $n$-vertex graph and its complement is at most $\frac{3n}{4}$.

The redundance $R(G)$ of a graph $G$ is the minimum, over all dominating sets $S$, of $\sum _{v\in S}(1+\mathrm{deg}(v))$, where $\mathrm{deg}(v)$ is the degree of vertex $v$. We use some dynamic programming algorithms to compute the redundance of complete grid graphs $G_{m,n}$ for $1\le m\le 21$ and all $n$, and to establish good upper and lower bounds on the redundance for larger $m$. We conjecture that the upper bound is the redundance when $m>21$.

Heinrich et al. [4] characterized those simple eulerian graphs with no Petersen-minor which admit a triangle-free cycle decomposition, a TFCD. If one permits Petersen minors then no such characterization is known even for $E(4,2)$, the set of all the eulerian graphs of maximum degree 4. Let $EM(4,2)\subset E(4,2)$ be the set of all graphs $H$ such that all triangles of $H$ are vertex disjoint, and each triangle contains a degree 2 vertex in $H$. In the paper it is shown that to each $G\in E(4,2)$ there exists a finite subset $S\subset EM(4,2)$ so that $G$ admits a TFCD if and only if some $H\in S$ admits a TFCD. Further, some sufficient conditions for a graph $G\in E(4,2)$ to possess a TFCD are given.

Let $\nu$ be some graph parameter and let $\mathcal{G}$ be a class of graphs for which $\nu$ can be computed in polynomial time. In this situation, it is often possible to devise a strategy to decide in polynomial time whether $\nu$ has a unique realization for some graph in $\mathcal{G}$. We first give an informal description of the conditions that allow one to devise such a strategy, and then we demonstrate our approach for three well-known graph parameters: the domination number, the independence number, and the chromatic number.

A $k$-line-distinguishing coloring of a graph $G=(V,E)$ is a partition of $V$ into $k$ sets $V_1,\dots ,V_k$ such that $q(⟨V_i⟩)\le 1$ for $i=1,\dots ,k$ and $q(V_i,V_j)\le 1$ for $1\le i\le j\le k$. If the color classes in a line-distinguishing coloring are also independent, then it is called a harmonious coloring. A coloring is minimal if, when two color classes are combined, we no longer have a coloring of the given type.

The upper harmonious chromatic number, $H(G)$, is defined as the maximum cardinality of a minimal harmonious coloring of a graph $G$, while the upper line-distinguishing chromatic number, $H^{\prime }(G)$, is defined as the maximum cardinality of a minimal line-distinguishing coloring of a graph $G$. For any graph $G$ of maximum degree $\mathrm{\Delta }(G)$, $H^{\prime }(G)\ge \mathrm{\Delta }(G)$ and $H(G)\ge \mathrm{\Delta }(G)+1$.

We characterize connected graphs $G$ that contain neither a triangle nor a 5-cycle for which $H(G)=\mathrm{\Delta }(G)+1$. We show that a triangle-free connected graph $G$ satisfies $H^{\prime }(G)=\mathrm{\Delta }(G)$ if and only if $G$ is a star $K_{1,\mathrm{\Delta }(G)}$. A partial characterization of connected graphs $G$ for which $H^{\prime }(G)=\mathrm{\Delta }(G)$ is obtained.

There are at least 52432 symmetric $(100,45,20)$ designs on which ${\text{Frob}}_{10}\times {\mathbb{Z}}_2$ acts as an automorphism group. All these designs correspond to Bush-type Hadamard matrices of order 100, and each leads to an infinite class of twin designs with parameters
$$v=100({81}^m+{81}^{m-1}+\dots +81+1),k=45(81{)}^m,\lambda =20(81{)}^m,$$
and an infinite class of Siamese twin designs with parameters
$$v=100({121}^m+{121}^{m-1}+\dots +121+1),k=55(121{)}^m,\lambda =30(121{)}^m,$$
where $m$ is an arbitrary positive integer. One of the constructed designs is isomorphic to that used by Z. Janko, H. Kharaghani, and V. D. Tonchev [4].

We define the $B_2$ block-intersection graph of a balanced incomplete block design $(V,\mathfrak{B})$ having order $n$, block size $k$, and index $\lambda$, or BIBD$(n,k,\lambda )$, to be the graph with vertex set $\mathfrak{B}$ in which two vertices are adjacent if and only if their corresponding blocks have exactly two points of $V$ in common. We define an undirected (resp. directed) hinge to be the multigraph with four vertices which consists of two undirected (resp. directed) 3-cycles which share exactly two vertices in common. An undirected (resp. directed) hinge system of order $n$ and index $\lambda$ is a decomposition of $\lambda K_n$ (resp. $\lambda K_n^{\ast }$) into undirected (resp. directed) hinges. In this paper, we show that each component of the $B_2$ block-intersection graph of a simple BIBD$(n,3,2)$ is 2-edge-connected; this enables us to decompose pure Mendelsohn triple systems and simple 2-fold triple systems into directed and undirected hinge systems, respectively. Furthermore, we obtain a generalisation of the Doyen-Wilson theorem by giving necessary and sufficient conditions for embedding undirected (resp. directed) hinge systems of order $n$ in undirected (resp. directed) hinge systems of order $v$. Finally, we determine the spectrum for undirected hinge systems for all indices $\lambda \ge 2$ and for directed hinge systems for all indices $\lambda \ge 1$.

Vince asked whether for each rational $r$ between 2 and 4 there was a planar graph of circular chromatic number $r$. Moser and Zhu showed that the answer is yes, the first for $2<r<3$, the second for $3<r<4$. This paper gives another family of planar graphs with circular chromatic number between 2 and 3.

We present a new proof that the optimal fast solutions to the gossip problem, for an even number of participants $n>2^{\lceil {\log }_{2}n\rceil }–2^{\lfloor \lceil {\log }_{2}n\rceil /2\rfloor }$, require exactly $\frac{n}{2}\lceil {\log }_{2}n\rceil$ calls.

We establish that up to an isomorphism there are exactly $88$ perfect $1$-factorizations of $K_{16}$ having nontrivial automorphism group. We also present some related results.

We consider the firefighter problem. We begin by proving that the associated decision problem is NP-complete even when restricted to bipartite graphs. We then investigate algorithms and bounds for trees and square grids.

Face two-colourable triangular embeddings of complete graphs $K_n$ correspond to biembeddings of Steiner triple systems. Such embeddings exist only if $n$ is congruent to 1 or 3 modulo 6. In this paper, we present the number of these embeddings for $n=13$.

The resolvable $2$-$(14,7,12)$ designs are classified in a computer search: there are 1,363,486 such designs, 1,360,800 of which have trivial full automorphism group. Since every resolvable $2$-$(14,7,12)$ design is also a resolvable $3$-$(14,7,5)$ design and vice versa, the latter designs are simultaneously classified. The computer search utilizes the fact that these designs are equivalent to certain binary equidistant codes, and the classification is carried out with an orderly algorithm that constructs the designs point by point. As a partial check, a subset of these designs is constructed with an alternative approach by forming the designs one parallel class at a time.

The trace of a degree $n$ polynomial $p(x)$ over $\text{GF}(2)$ is the coefficient of $x^{n-1}$, and the $subtrace$ is the coefficient of $x^{n-2}$. We derive an explicit formula for the number of irreducible degree $n$ polynomials over $\text{GF}(2)$ that have a given trace and subtrace. The trace and subtrace of an element $\beta \in \text{GF}(2^n)$ are defined to be the coefficients of $x^{n-1}$ and $x^{n-2}$, respectively, in the polynomial $q(x)=\prod _{i=0}^{n-1}(x+{\beta }^{2^i}).$ We also derive an explicit formula for the number of elements of $\text{GF}(2^n)$ of given trace and subtrace. Moreover, a new two-equation Möbius-type inversion formula is proved.

In this paper, it has been verified, by a computer-based proof, that the smallest size of a complete arc is 12 in $\text{PG}(2,27)$ and 13 in $\text{PG}(2,29)$. Also, the spectrum of the sizes of the complete arcs of $\text{PG}(2,27)$ has been found. The classification of the smallest complete arcs of $\text{PG}(2,27)$ is given: there are seven non-equivalent 12-arcs, and for each of them, the automorphism group and some geometrical properties are presented. Some examples of complete 13-arcs of $\text{PG}(2,29)$ are also described.

For a factorization $F$ of a graph $G$ into factors $F_1,F_2,\dots ,F_k$, the chromatic number $\chi (F)$ of $F$ is the minimum number of elements $V_1,V_2,\dots ,V_m$ in a partition of $V(G)$ such that each subset $V_i$ $(1\le i\le m)$ is independent in some factor $F_j$ $(1\le j\le k)$. If $\chi (F)=m$, then $F$ is an $m$-chromatic factorization. For integers $k,m,n\ge 2$ with $n\ge m$, the cofactor number $c_m(k,n)$ is defined as the smallest positive integer $p$ for which there exists an $m$-chromatic factorization $F$ of the complete graph $K_p$ into $k$ factors $F_1,F_2,\dots ,F_k$ such that $\chi (F_i)\ge n$ for all integers $i$ $(1\le i\le k)$. The values of the numbers $c_m(k,n)$ are investigated for $m=3$ and $m=4$.The $k$-cofactorization number ${\chi }_k(G)$ of a graph $G$ is defined as $max\{\chi (F):F\text{ is a factorization of }G\text{ into }k\text{ factors}\}$. It is shown that ${\chi }_k(K_n)\ge \lfloor n^{1/k}\rfloor$ for $k\ge 2$ and $n\ge 4$. The numbers ${\chi }_k(K_n)$ are determined for several values of $k$ and $n$.