Bailey (1989) defined a \(k \times v\) double Youden rectangle (DYR), with \(k 3\) is a prime power with \(k \equiv 3 \pmod{4}\). We now provide a general construction for DYRs of sizes \(k \times (2k+1)\) where \(k > 5\) is a prime power with \(k \equiv 1 \pmod{4}\). We present DYRs of sizes \(9 \times 19\) and \(13 \times 27\).

We show by an elementary argument that, given any greedy clique decomposition of a graph \(G\) with \(n\) vertices, the sum of the orders of the cliques is less than \(\frac{5}{8}n^2\). This gives support to a conjecture of Peter Winkler.

We study the signed domination number \(\gamma_s\), the minus domination number \(\gamma^-\) and the majority domination number \(\gamma_{\mathrm{maj}}\). In this paper, we establish good lower bounds for \(\gamma_s\), \(\gamma^-\) and \(\gamma_{\mathrm{maj}}\), and give sharp lower bounds for \(\gamma_s\), \(\gamma^-\) for trees.

In this paper, nineteen new binary linear codes are presented which improve the bounds on the maximum possible minimum distance. These codes belong to the class of quasi-cyclic (QC) codes, and have been constructed using a stochastic optimization algorithm, tabu search. Six of the new codes meet the upper bound on minimum distance and so are optimal.

This game is a mixture of Searching and Cops and Robber. The Cops have partial information provided by sensing devices called photo radar. The Robber has perfect information. We give bounds on the number of photo radar units required by one Cop to capture a Robber on a tree and, with less tight bounds, on a copwin graph.

Cographs—complement-reducible graphs—can be viewed as intersection graphs (of \(k\)-dimensional boxes), as intersections of graphs (of \(P_4 ,C_4\)-free graphs), and as common tieset graphs of two-terminal graphs. This approach connects cographs with other topics such as chordal, interval, and series-parallel graphs, and it provides a natural dimension for cographs.

We consider reconstruction problems involving square-celled animals and other, similar, problems. Our main results, Corollary 3.2 and Theorem 3.3, give positive answers to the problems raised at the end of [4] by Harary and Manvel.

We present connections between \(T\)-colorings of graphs and regular vertex-coloring for distance graphs. Given a non-negative integral set \(T\) containing \(0\), a \(T\)-coloring of a simple graph assigns each vertex a non-negative integer (color) such that the difference of colors of adjacent vertices cannot fall in \(T\). Let \(\omega(T)\) be the minimum span of a \(T\)-coloring of an \(n\)-vertex complete graph. It is known that the asymptotic coloring efficiency of \(T\), \(R(T) = \lim_{n\to\infty} \frac{\omega(n)}{n}\), exists for any \(T\). Given a positive integral set \(D\), the distance graph \(G(\mathcal{Z}, D)\) has as vertex set all integers \(\mathbb{Z}\), and two vertices are adjacent if their difference is in \(D\). We prove that the chromatic number of \(G(\mathcal{Z}, D)\), denoted as \(\chi(\mathcal{Z}, D)\), is an upper bound of \(\lceil R(T) \rceil\), provided \(D=T \setminus \{0\}\). This connection is used in calculating \(\chi_a(m, k)\), chromatic number of \(G(\mathcal{Z},D)\) as \(D = \{1,2,3,\ldots,m\} \setminus \{k\}\), \(m > k\). Early results about \(\chi_\beta(m,k)\) were due to Eggleton, Erdos and Skilton [1985] who determined \(\chi_\beta(m,k)\) as \(k = 1\), partially settled the case \(k = 2\), and obtained upper and lower bounds for other cases. We show that \(\chi_\beta(m, k) = k\), if \(m < 2k\); and \(\chi_\beta(m,k) = \lceil \frac{m+k+1}{2} \rceil\), if \(m \geq 2k\) and \(k\) is odd. Furthermore, complete solutions for \(k = 2\) and \(4\), and partial solutions for other even numbers \(k\) are obtained. All the optimal proper colorings presented are periodic with smallest known periods.

The nonexistence of digraphs with order equal to the Moore bound \(\mathrm{M_{d,k}} = 1+d+\ldots+ d^h\) for \(d,k > 1\) has led to the study of the problem of the existence of “almost” Moore digraphs, namely digraphs with order close to the Moore bound. In [1], it was shown that almost Moore digraphs of order \(\mathrm{M_{d,k}} – 1\), degree \(d\), diameter \(k\) (\(d, k \geq 3\)) contain either no cycle of length \(k\) or exactly one such cycle. In this paper, we shall derive some further necessary conditions for the existence of almost Moore digraphs for degree \(d\) and diameter \(k \geq 1\). As a consequence, for diameter \(k = 2\) and degree \(d\), \(2 \leq d \leq 12\), we show that there are no almost Moore digraphs of order \(\mathrm{M_{d,2}} – 1\) with one vertex in a \(2\)-cycle \(C_2\) except the digraphs with every vertex in \(C_2\).

In this note we characterize the members of the Ramsey set \(\mathcal R(2K_2,tK_2)\) of all \((2K_2,tK_2)\)-minimal graphs using factor-critical graphs. Moreover, the sets \(\mathcal R(2K_2,tK_2)\) are determined for \(t \leq 5\).