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\).

Let \(G\) be a graph. A bijection \(f\) from \(V(G) \cup E(G)\) to \(\{1,2,\ldots,|V(G)| + |E(G)|\}\) is called a magic valuation if \(f(u)+f(v)+f(uv)\) is constant for any edge \(uv\) in \(G\). A magic valuation \(f\) of \(G\) is called a supermagic valuation if \(f(V(G)) = \{1,2,\ldots,|V(G)|\}\). The following theorem is proved.For any graph \(H\), there exists a connected graph \(G\) so that \(G\) contains \(H\) as an induced subgraph and \(G\) has a supermagic valuation.

For a graph \(G\), let \(\alpha(G)\) and \(\tau(G)\) denote the independence number of \(G\) and the matching number of \(G\), respectively. Further, let \(G \times H\) denote the direct product (also known as Kronecker product, cardinal product, tensor product, categorical product, and graph conjunction) of graphs \(G\) and \(H\). It is known that \(\alpha(G \times H) \geq \max\{\alpha(G)-|H|, \alpha(H)-|G|\} =: \underline{\alpha}(G \times H)\) and that \(\tau(G \times H) \geq 2.\tau(G).\tau(H) =: \underline{\tau}(G \times H)\). It is shown that an equality/inequality between \(\alpha\) and \(\underline{\alpha}\) is independent of an equality/inequality between \(\tau\) and \(\underline{\tau}\). Further, several results are presented on the existence of a complete matching in each of the two connected components of the direct product of two bipartite graphs. Additional results include an upper bound on \(\alpha(G \times H)\) that is achievable in certain cases.

All distinct double circulant self-dual codes over \(\text{GF}(5)\), with a minimum weight which is highest among all double circulant self-dual codes, have been found for each length \(n \leq 24\). For lengths \(14\), \(16\), and \(20\), these codes are extremal. In this paper, we characterize these extremal double circulant self-dual codes. In particular, a classification of extremal double circulant self-dual codes of length \(14\) is given. We present other double circulant codes which improve the lower bounds on the highest possible minimum weight. A classification of double circulant self-dual codes with parameters \([18, 9, 7]\) and \([24, 12, 9]\) is also given.

This paper is about critical sets in Latin squares and the weaker concept of partial Latin squares with unique completion. This work involves taking two known partial Latin squares with unique completion, or critical sets in Latin squares, and using a product construction to produce new partial Latin squares with unique completion, or new critical sets in larger Latin squares.

In this paper, we prove the following result:
Let \(D\) be a disconnected oriented graph of order \(n\). If
\(d^+(u)+d^+(v) \geq n-2\) for any pair \(u,v\) of nonadjacent vertices such that \(N^+(u) \cap N^+(v) \neq \emptyset\) and \(d^-(u) + d^-(v) \geq n-2\) for any pair \(u,v\) of nonadjacent vertices such that \(N^-(u) \cap N^-(v) \neq \emptyset\), then \(D\) contains a directed Hamiltonian cycle.