A labeling of the vertices of a graph with distinct natural numbers induces a natural labeling of its edges: the label of an edge \((x,y)\) is the absolute value of the difference of the labels of \(x\) and \(y\). We say that a labeling of the vertices of a graph of order \(n\) is minimally \(k\)-equitable if the vertices are labeled with \(1, 2, \dots, n\) and in the induced labeling of its edges, every label either occurs exactly \(k\) times or does not occur at all. In this paper, we prove that Butterfly and Benes networks are minimally \(2^r\)-equitable where \(r\) is the dimension of the networks.

The method of large scale group testing has been used in the economical testing of blood samples, and in non-testing situations such as experimental designs and coding theory, for over 50 years. Some very basic questions addressing the minimum number of tests required to identify defective samples still remain unsolved, including the situation where one defective sample in each of two batches are to be found. This gives rise to an intriguing graph theoretical conjecture concerning bipartite graphs, a conjecture which in this paper is proved to be true in the case where vertices in one part of the bipartite graph have low degree.

Using the action of the linear fractional groups \( L_2(q) \), where \( q = 8, 25, 27, 29, 31 \) and \( 32 \), some \( 1 \)-designs are constructed. It is shown that subgroups of the automorphism group of \( L_2(q) \) appear as the full automorphism group of the constructed designs. In the cases \( q = 8 \) and \( 32 \), it is shown that the symmetric groups \( \mathbb{S}_9 \) and \( \mathbb{S}_{33} \), respectively, appear as the automorphism group of one of the constructed designs.

Here we consider string matching problems that arise naturally in applications to music retrieval. The \( \delta \)-Matching problem calculates, for a given text \( T_{1..n} \) and a pattern \( P_{1..m} \) on an alphabet of integers, the list of all indices \( \mathcal{I}_\delta = \{1 \leq i \leq n-m+1 : \max_{j=1}^m \{|P_j – T_{i+j-1}| \leq \delta\}\} \). The \( \gamma \)-Matching problem computes, for given \( T \) and \( P \), the list of all indices \( \mathcal{I}_\gamma = \{1 \leq i \leq n-m+1 : \sum_{j=1}^m |P_j – T_{i+j-1}| \leq \gamma\} \). In this paper, we extend the current result on the different matching problems to handle the presence of “\emph{don’t care}” symbols. We present efficient algorithms that calculate \( \mathcal{I}_\delta \), \( \mathcal{I}_\gamma \), and \( \mathcal{I}_{(\delta,\gamma)} = \mathcal{I}_\delta \cap \mathcal{I}_\gamma \) for pattern \( P \) with occurrences of “don’t cares”.

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 \)-\emph{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} \).