In 2004, Kim and Nakprasit showed that the chromatic number of \( K_2(9,4) \) is at least 11. In this note we present an 11-coloring for \( K^2(9,4) \) (the square of the Kneser graph \( K(9,4) \)). This proves that the chromatic number of \( K^2(9,4) \) is \(11\).

Let \( N \) and \( Z \) denote respectively the set of all nonnegative integers and the set of all integers. A \((p,q)\)-graph \( G = (V, E) \) is said to be additively \((a,r)\)-geometric if there exists an injective function \( f : V \to Z \) such that \( f^+(E) = \{a, ar, \dots, ar^{q-1}\} \) where \( a, r \in N \), \( r > 1 \), and \( f^+ \) is defined by \( f^+(uv) = f(u) + f(v) \) for all \( uv \in E \). If further \( f(v) \in N \) for all \( v \in V \), then \( G \) is said to be additively \((a,r)^*\)-geometric. In this paper we characterise graphs which are additively geometric and additively \(^*\)-geometric.

In this paper we find ten new weighing matrices of order \(2n\) and weight \(2n – 5\) constructed from two circulants, by forming a conjecture on the locations of the five zeros in a potential solution. Establishing patterns for the locations of zeros in sequences that can be used to construct weighing matrices seems to be a worthwhile path to explore, as it reduces significantly the computational complexity of the problem.

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.