A dominating set \( S \) in a graph \( G \) is said to be perfect if every vertex of \( G \) not in \( S \) is adjacent to just one vertex of \( S \). Given a vertex subset \( S’ \) of a side \( P_m \) of an \( m \times n \) grid graph \( G \), the perfect dominating sets \( S \) in \( G \) with \( S’ = S \cap V(P_m) \) can be determined via an exhaustive algorithm \( \ominus \) of running time \( O(2^{m+n}) \). Extending \( \ominus \) to infinite grid graphs of width \( m – 1 \), periodicity makes the binary decision tree of \( \ominus \) prunable into a finite threaded tree, a closed walk of which yields all such sets \( S \). The graphs induced by the complements of such sets \( S \) can be codified by arrays of ordered pairs of positive integers via \( \ominus \), for the growth and determination of which a speedier algorithm exists. A recent characterization of grid graphs having total perfect codes \( S \) (with just \( 1 \)-cubes as induced components), due to Klostermeyer and Goldwasser, is given in terms of \( \ominus \), which allows to show that these sets \( S \) are restrictions of only one total perfect code \( S_1 \) in the integer lattice graph \( \Lambda \) of \( \textbf{R}^2 \). Moreover, the complement \( \Lambda – S_1 \) yields an aperiodic tiling, like the Penrose tiling. In contrast, the parallel, horizontal, total perfect codes in \( \Lambda \) are in \( 1-1 \) correspondence with the doubly infinite \( \{0, 1\} \)-sequences.

Let \( G \) be a graph of size \( n \) with vertex set \( V(G) \) and edge set \( E(G) \). A \( \rho \)-\({labeling}\) of \( G \) is a one-to-one function \( f : V(G) \to \{0,1,\dots,2n\} \) such that \( \{|f(u) – f(v)| : \{u,v\} \in E(G)\} = \{x_1,x_2,\dots,x_n\} \), where for each \( i \in \{1,2,\dots,n\} \) either \( x_i = i \) or \( x_i = 2n+1-i \). Such a labeling of \( G \) yields a cyclic \( G \)-decomposition of \( K_{2n+1} \). It is conjectured by El-Zanati and Vanden Eynden that every 2-regular graph \( G \) admits a \( \rho \)-labeling. We show that the union of up to ten vertex-disjoint \( C_{4x+1} \) admits a \( \rho \)-labeling.

The Hamilton-Waterloo problem in the case of triangle-factors and Hamilton cycles asks for a \(2\)-factorization of \( K_n \), in which each \(2\)-factor is either a Hamilton cycle or a triangle-factor. Necessarily \( n \equiv 3 \pmod{6} \). The case of \( n \equiv 9 \pmod{18} \) was completely solved in 2004 by Horak, Nedela, and Rosa. In this note, we solve the problem when \( n \equiv 3 \pmod{18} \) and there are at least two Hamilton cycles. A companion paper treats the case when there is exactly one Hamilton cycle and \( n \equiv 3 \pmod{6} \).

There exist \( 3 \) near bowtie systems of order \( 7 \), \( 12 \) bowtie systems of order \( 9 \), and \( 1{,}411{,}422 \) balanced bowtie systems of order \( 13 \).

Chessboard separation problems are modifications to classic chessboard problems, such as the \( N \) Queens Problem, in which obstacles are placed on the chessboard. This paper focuses on a variation known as the \( N + k \) Queens Problem, in which \( k \) Pawns and \( N + k \) mutually non-attacking Queens are to be placed on an \( N \)-by-\( N \) chessboard. Results are presented from performance studies examining the efficiency of sequential and parallel programs that count the number of solutions to the \( N + k \) Queens Problem using traditional backtracking and dancing links. The use of Stochastic Local Search for determining the existence of solutions is also presented. In addition, preliminary results are given for a similar problem, the \( N + k \) Amazons.

In this paper, it is shown that the graph obtained by overlapping the cycle \( C_m \) (\( m \geq 3 \)) and the complete bipartite graph \( K_{3,3} \) at an edge is uniquely determined by its chromatic polynomial.

A graph \( G \) is said to be in the collection \( M_t \) if there are precisely \( t \) different sizes of maximal independent sets of vertices in \( G \). For \( G \in M_t \), and \( v \in G \), we determine the extreme values that \( x \) can assume where \( G \setminus \{v\} \) belongs to \( M_x \). For both the minimum and maximum values, graphs are given that achieve them, showing that the bounds are sharp. The effect of deleting an edge from \( G \) on the number of sizes of maximal independent sets is also considered.

The chromatic polynomial of a graph \( G \), \( P(G; \lambda) \), is the polynomial in \( \lambda \) which counts the number of distinct proper vertex \( \lambda \)-colorings of \( G \), given \( \lambda \) colors. We compute \( P(C_4 \times P_n; \lambda) \) and \( P(C_5 \times P_n; \lambda) \) in matrix form and will find the generating function for each of these sequences.

The \( n \)-cube is the graph whose vertices are all binary words of length \( n > 1 \) and whose edges join vertices that differ in exactly one entry; i.e., are at Hamming distance \( 1 \) from each other. If a word has a non-empty prefix, not the entire word, which is also a suffix, then it is said to be bordered. A word that is not bordered is unbordered. Unbordered words have been studied extensively and have applications in synchronizable coding and pattern matching. The neighborhood of an unbordered word \( w \) is the word itself together with the set of words at Hamming distance \( 1 \) from \( w \). Over the binary alphabet, the neighborhood of an unbordered word \( w \) always contains two bordered words obtained by complementing the first and last entries of \( w \). We determine those unbordered words \( w \) whose neighborhoods otherwise contain only unbordered words.

Let \( G \) be a graph with vertex set \( V \) and edge set \( E \). A labeling \( f : V \to \{0,1\} \) induces a partial edge labeling \( f^* : E \to \{0,1\} \) defined by \( f^*(xy) = f(x) \) if and only if \( f(x) = f(y) \) for each edge \( xy \in E \). The balance index set of \( G \), denoted \( \text{BI}(G) \), is defined as \( \{|f^{*-1}(0) – f^{*-1}(1)| : |f^{-1}(0) – f^{-1}(1)| \leq 1\} \). In this paper, we study the balance index sets of graphs which are \( L \)-products with cycles and complete graphs.