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.

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.

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)\).

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.