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.

We study the weight distributions of the ternary codes of finite projective planes of order \(9\). The focus of this paper is on codewords of small Hamming weight. We show that there are many weights for which there are no codewords.

For a given sequence of nonincreasing numbers, \(\mathbf{d} = (d_1, \ldots, d_n)\), a necessary and sufficient condition is presented to characterize \(d\) when its realization is a unique labelled simple graph. If \(G\) is a graph, we consider the subgraph \(G’\) of \(G\) with maximum edges which is uniquely determined with respect to its degree sequence. We call the set of \(E(G) \setminus E(G’)\) the smallest edge defining set of \(G\). This definition coincides with the similar one in design theory.

A graph \(G\) without isolated vertices is said to be set-magic if its edges can be assigned distinct subsets of a set \(X\) such that for every vertex \(v\) of \(G\), the union of the subsets assigned to the edges incident with \(v\) is \(X\); such a set-assignment is called a set-magic labeling of \(G\). In this note, we study infinite set-magic graphs and characterize infinite graphs \(G\) having set-magic labelings \(f\) such that \(|f(e)| = 2\) for all \(e \in E(G)\).

A perfect \(\langle k,r \rangle\)-latin square \(A = (a_{i,j})\) of order \(n\) with \(m\) elements is an \(n \times n\) array in which each element occurs in each row and column, and the element \(a_{i,j}\) occurs either \(k\) times in row \(i\) and \(r\) times in column \(j\), or occurs \(r\) times in row \(i\) and \(k\) times in column \(j\). In 1989, Cai, Kruskal, Liu, and Shen studied the existence of perfect \(\langle k,r \rangle\)-latin squares. Here, a simpler construction of perfect \(\langle k,r \rangle\)-latin squares is given.

De Bruijn sequences had been well investigated in \(70s-80s\). In the past, most of the approaches used to generate de Bruijn sequences were based upon either finite field theory or combinatorial theory. This paper describes a simple approach for generating de Bruijn sequences as “seeds”, and then based upon the “seeds”, a simple procedure is presented to reproduce a class of de Bruijn sequences. Numerical results of the distribution of reproduced sequences are provided. Additionally, this paper also reports some recent applications of de Bruijn sequences in psychology and engineering.

A graph \(G(V, E)\) is a mod sum graph if there is a labeling of the vertices with distinct positive integers so that an edge is present if and only if the sum of the labels of the vertices incident on the edge, modulo some positive integer, is the label of a vertex of the graph. It is known that wheels are not mod sum graphs. The mod sum number of a graph is the minimum number of isolates that, together with the given graph, form a mod sum graph. The mod sum number is known for just a few classes of graphs. In this paper we show that the mod sum number of the \(n\)-spoked wheel, \(\rho(W_n)\), \(n \geq 5\), is \(n\) when \(n\) is odd and \(2\) when \(n\) is even.

Kahn (see [3]) reported that N. Alon, M. Saks, and P. D. Seymour made the following conjecture. If the edge set of a graph \(G\) is the disjoint union of the edge sets of \(m\) complete bipartite graphs, then \(\chi(G) \leq m+1\). The purpose of this paper is to provide a proof of this conjecture for \(m \leq 4\) and \(m \geq n – 3\) where \(G\) has \(n\) vertices.

In a graph \(G = (V, E)\), a set \(S\) of vertices (as well as the subgraph induced by \(S\)) is said to be dominating if every vertex in \(V \setminus S\) has at least one neighbor in \(S\). For a given class \(\mathcal{D}\) of connected graphs, it is an interesting problem to characterize the class \({Dom}(\mathcal{D})\) of graphs \(G\) such that each connected induced subgraph of \(G\) contains a dominating subgraph belonging to \(\mathcal{D}\). Here we determine \({Dom}(\mathcal{D})\) for \(\mathcal{D} = \{P_1, P_2, P_5\}\), \(\mathcal{D} = \{K_t \mid t \geq 1\} \cup \{P_5\}\), and \(\mathcal{D} =\) {connected graphs on at most four vertices} (where \(P_t\) and \(K_t\) denote the path and the complete graph on \(t\) vertices, respectively). The third theorem solves a problem raised by Cozzens and Kelleher [\(Discr. Math.\) 86 (1990), 101-116]. It turns out that, in each case, a concise characterization in terms of forbidden induced subgraphs can be given.

We use the results on \(5\)-GDDs to obtain optimal packings with block size five and index one. In particular, we prove that if \(v \equiv 2, 6, 10 \pmod{20}\), there exists an optimal packing with block size five on \(v\) points with at most \(32\) possible exceptions. Furthermore, if \(v \equiv 14, 18 \pmod{20}\), there exists an optimal packing with block size five on \(v\) points with a finite (large) number of possible exceptions.

A chromatic root is a root of the chromatic polynomial of some graph \(G\). E. Farrell conjectured in \(1980\) that no chromatic root can lie in the left-half plane, and in \(1991\) Read and Royle showed by direct computation that the chromatic polynomials of some graphs do have a root there. These examples, though, yield only finitely many such chromatic roots. Subsequent results by Shrock and Tsang show the existence of chromatic roots of arbitrarily large negative real part. We show that theta graphs with equal path lengths of size at least \(8\) have chromatic roots with negative real part.

The clique operator \(K\) maps a graph \(G\) into its clique graph, which is the intersection graph of the (maximal) cliques of \(G\). Recognizing clique graphs is a problem known to be in NP, but no polynomial time algorithm or proof of NP-completeness is known. In this note we prove that this recognition problem can be reduced to the case of graphs of diameter at most two.

The skewness of a graph \(G\) is the minimum number of edges that need to be deleted from \(G\) to produce a planar graph. The splitting number of a graph \(G\) is the minimum number of splitting steps needed to turn \(G\) into a planar graph; where each step replaces some of the edges \(\{u,v\}\) incident to a selected vertex \(u\) by edges \(\{u’,v\}\), where \(u’\) is a new vertex. We show that the splitting number of the toroidal grid graph \(C_n \times C_m\) is \(\min\{n,m\} – 2\delta_{n,3}\delta_{m,3} – \delta_{n,4}\delta_{m,3} – \delta_{n,3}\delta_{m,4}\) and its skewness is \(\min\{n, m\} – \delta_{n,3}\delta_{m,3 }- \delta_{n,4}\delta_{m,3} – \delta_{n,3}\delta_{m,4}\). Here, \(\delta\) is the Kronecker symbol, i.e., \(\delta_{i,j}\) is \(1\) if \(i = j\), and \(0\) if \(i \neq j\).

We introduce the notion of BP-spatial representation of a biconnected graph \(G = (V, E)\). We show that the spatiality degree of a BP-spatial representable graph is \(2(|E| – |V|)\). From this result, we derive the spatiality degree for planar and hamiltonian graphs.

We introduce the notion of premature partial Latin squares; these cannot be completed, but if any of the entries is deleted, a completion is possible. We study their spectrum, i.e., the set of integers \(t\) such that there exists a premature partial Latin square of order \(n\) with exactly \(t\) nonempty cells.

Given a digraph \(D\), its competition graph has the same vertex set and an edge between two vertices \(x\) and \(y\) if there is a vertex \(u\) so that \((x,u)\) and \((y,u)\) are arcs of \(D\). Motivated by a problem of communications, we study the competition graphs of the special digraphs known as semiorders. This leads us to define a condition on digraphs called \(C(p)\) and \(C^*(p)\) and to study the graphs arising as competition graphs of acyclic digraphs satisfying conditions \(C(p)\) or \(C^*(p)\).

A transversal cover is a set of \(gk\) points in \(k\) disjoint groups of size \(g\) and, ideally, a minimal collection of transversal subsets, called blocks, such that any pair of points not contained in the same group appears in at least one block. In this article we present a direct construction method for transversal covers using group divisible designs. We also investigate a particular infinite family of group divisible designs that yield particularly good covers.

For an ordered set \(A\) and \(B\) whose orders agree on its intersection, the gluing of \(A\) and \(B\) is defined to be the ordered set on the union of its underlying sets whose order is the transitive closure of the union of the orders of \(A\) and \(B\). The gluing number of an ordered set \(P\) is the minimum number of induced semichains (suborders of dimension at most two) of \(P\) whose consecutive gluing is \(P\). In this paper we investigate this parameter on some special ordered sets.

The aim of this paper is to give several characterizations for the following two classes of graphs: (i) graphs for which adding any \(l\) edges produces a graph which is decomposable into \(k\) spanning trees and (ii) graphs for which adding some \(l\) edges produces a graph which is decomposable into \(k\) spanning trees.