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.

For two vertices \( u \) and \( v \) in a connected graph \( G \), the detour distance \( D(u,v) \) between \( u \) and \( v \) is the length of a longest \( u – v \) path in \( G \). The detour diameter \( \text{diam}_D(G) \) of \( G \) is the greatest detour distance between two vertices of \( G \). Two vertices \( u \) and \( v \) are detour antipodal in \( G \) if \( D(u,v) = \text{diam}_D(G) \). The detour antipodal graph \( \text{DA}(G) \) of a connected graph \( G \) has the same vertex set as \( G \) and two vertices \( u \) and \( v \) are adjacent in \( \text{DA}(G) \) if \( u \) and \( v \) are detour antipodal vertices of \( G \). For a connected graph \( G \) and a nonnegative integer \( r \), define \( \text{DA}^r(G) \) as \( G \) if \( r = 0 \) and as the detour antipodal graph of \( \text{DA}^{r-1}(G) \) if \( r > 0 \) and \( \text{DA}^{r-1}(G) \) is connected. Then \( \{\text{DA}^r(G)\} \) is the detour antipodal sequence of \( G \). A graph \( H \) is the limit of \( \{\text{DA}^r(G)\} \) if there exists a positive integer \( N \) such that \( \text{DA}^r(G) \cong H \) for all \( r \geq N \). It is shown that \( \{\text{DA}^r(G)\} \) converges if \( G \) is Hamiltonian. All graphs that are the limit of the detour antipodal sequence of some Hamiltonian graph are determined.

For a vertex \( x \) in a graph \( G \), we define \( \Psi_1(x) \) to be the number of edges in the closed neighborhood of \( x \). Vertex \( x^* \) is a neighborhood champion if \( \Psi_1(x^*) > \Psi_1(x) \) for all \( x \neq x^* \). We also refer to such an \( x^* \) as a unique champion. For \( d \geq 4 \), let \( n_0(1,d) \) be the smallest number such that for every \( n \geq n_0(1,d) \) there exists an \( n \)-vertex \( d \)-regular graph with a unique champion. Our main result is that \( n_0(1,d) \) satisfies \( d+3 \leq n_0(1,d) < 3d+1 \). We also observe that there can be no unique champion vertex when \( d = 3 \).