Let \(M(d,n)\) denote the minimax number of group tests required for the identification of the \(d\) defectives in a set of \(n\) items. It was conjectured by Hu, Hwang, and Wang that \(M(d,n) = n-1\) for \(n \leq 3d\), a surprisingly difficult combinatorial problem with very little known. The best known result is \(M(d,n) = n-1\) for \(n \leq \frac{42}{16}d\) by Du and Hwang. In this note, we improve their result by proving \(M(d,n) = n – 1\) for \(d \geq 193\) and \(n \leq \frac{42}{16}d\).

In this paper, we investigate the divisibility of \(mn\) by \(am+bn+c\) for given \(a\), \(b\), and \(c\). We give the necessary and sufficient condition for the divisibility, that is, \(am + bn + c\) divides \(mn\). We then present the structure of the set of pairs \([m,n]\) that satisfies the divisibility. This structure is represented by a directed graph and we prove the necessary and sufficient condition for the graph to have a binary tree structure. In particular, for \(c = -1\), we show double binary tree structures on the set.

Let \({PG}(n,q)\) be the projective \(n\)-space over the Galois field \({GF}(q)\). A \(k\)-cap in \({PG}(n,q)\) is a set of \(k\) points such that no three of them are collinear. A \(k\)-cap is said to be complete if it is maximal with respect to set-theoretic inclusion. In this paper, using classical algebraic varieties, such as Segre varieties and Veronese varieties, some new infinite classes of caps are constructed.

We introduce Skolem arrays, which are two-dimensional analogues of Skolem sequences. Skolem arrays are ladders which admit a Skolem labelling in the sense of [2]. We prove that they exist exactly for those integers \(n = 0\) or \(1 \pmod{4}\). In addition, we provide an exponential lower bound for the number of distinct Skolem arrays of a given order. Computational results are presented which give an exact count of the number of Skolem arrays up to order \(16\).

The cyclicity of a graph is the largest integer \(n\) for which the graph is contractible to the cycle on \(n\) vertices. We prove that, for \(n\) greater than three, the problem of determining whether an arbitrary graph has cyclicity \(n\) is NP-hard. We conjecture that the case \(n = 3\) is decidable in polynomial time.

We provide a hierarchy, linearly ordered by inclusion, describing various complete sets of combinatorial objects starting with complete sets of mutually orthogonal Latin squares, generalizing to affine geometries and designs, frequency squares and hypercubes, and ending with \((t, m, s)\)-nets.

In this paper we introduce the edge-residual number \(\rho(G)\) of a graph \(G\). We give tight upper bounds for \(\rho(G)\) in terms of the eigenvalues of the Laplacian matrix of the line graph of \(G\). In addition, we investigate the relation between this novel parameter and the line completion number for dense graphs. We also compute the line completion number of complete bipartite graphs \(K_{m,n}\) when either \(m = n\) or both \(m\) and \(n\) are even numbers. This partially solves an open problem of Bagga, Beinecke and Varma [2].

We reintroduce the problem of finding square \(\pm 1\)-matrices, denoted \(c\text{-} {H}(n)\), of order \(n\), whose rows have non-zero inner product \(c\). We obtain some necessary conditions for the existence of \(c\text{-} {H}(n)\) and provide a characterization in terms of SBIBD parameters. Several new \(c\text{-} {H}(n)\) constructions are given and new connections to Hadamard matrices and \(D\)-optimal designs are also explored.

For an integer \(k \geq 1\), a vertex \(v\) of a graph \(G\) is \(k\)-geodominated by a pair \(z, y\) of vertices in \(G\) if \(d(x, y) = k\) and \(v\) lies on an \(x-y\) geodesic of \(G\). A set \(S\) of vertices of \(G\) is a \(k\)-geodominating set if each vertex \(v\) in \(V – S\) is \(k\)-geodominated by some pair of distinct vertices of \(S\). The minimum cardinality of a \(k\)-geodominating set of \(G\) is its \(k\)-geodomination number \(g_k(G)\).

A vertex \(v\) is openly \(k\)-geodominated by a pair \(x, y\) of distinct vertices in \(G\) if \(v\) is \(k\)-geodominated by \(x\) and \(y\) and \(v \neq x, y\). A vertex \(v\) in \(G\) is a \(k\)-extreme vertex if \(v\) is not openly \(k\)-geodominated by any pair of vertices in \(G\). A set \(S\) of vertices of \(G\) is an open \(k\)-geodominating set of \(G\) if for each vertex \(v\) of \(G\), either (1) \(v\) is \(k\)-extreme and \(v \in S\) or (2) \(v\) is openly \(k\)-geodominated by some pair of distinct vertices of \(S\). The minimum cardinality of an open \(k\)-geodominating set in \(G\) is its open \(k\)-geodomination number \(og_k(G)\).

It is shown that each triple \(a, b, k\) of integers with \(2 \leq a \leq b\) and \(k \geq 2\) is realizable as the geodomination number and \(k\)-geodomination number of some tree. For each integer \(k \geq 1\), we show that a pair \((a, n)\) of integers is realizable as the \(k\)-geodomination number (open \(k\)-geodomination number) and order of some nontrivial connected graph if and only if \(2 \leq a = n\) or \(2 \leq a \leq n – k + 1\).

We investigate how \(k\)-geodomination numbers are affected by adding a vertex. We show that if \(G\) is a nontrivial connected graph of diameter \(d\) with exactly \(l\) \(k\)-extreme vertices, then \(\{2, l\} \leq g_k(G) \leq og_k(G) \leq {3}g_k(G) – 2l\) for every integer \(k\) with \(2 \leq k \leq d\).

In \(1973\), Deuber published his famous proof of Rado’s conjecture regarding partition regular sets. In his proof, he invented structures called \((m, p, c)\)-sets and gave a partition theorem for them based on repeated applications of van der Waerden’s theorem on arithmetic progressions. In this paper, we give the complete proof of Deuber’s, however with the more recent parameter set proof of his partition result for \((m, p, c)\)-sets. We then adapt this parameter set proof to show that for any \(k, m, p, c\), every \(K_k\)-free graph on the positive integers contains an \((m, p, c)\)-set, each of whose rows are independent sets.