Let \( L(m, n) \) be the largest integer such that, if each symbol in an \( m \times n \) rectangle occurs at most \( L(m, n) \) times, then the array must have a transversal. We improve the lower bound to \( L(m, n) \geq \left\lfloor \frac{m(n – m + 1) – 1}{m – 1} \right\rfloor \) for \( m > 1 \). Then we show that sporadically \( L(m, n) < \left\lfloor \frac{mn – 1}{m – 1} \right\rfloor \) in the range \( m \leq n \leq m^2 – 3m + 3 \). Define \( n_0(m) \) to be the smallest integer \( z \) such that if \( n \geq z \) then \( L(m, n) = \left\lfloor \frac{mn – 1}{m – 1} \right\rfloor \). We improve \( n_0(m) \) from \( O(m^3) \) to \( O(m^{2.5}) \). Finally, we determine \( L(4, n) \) for all \( n \).

In [1], we showed that for \( v \equiv 1 \) or \( 3 \pmod{6} \), there is an equitable \( k \)-edge coloring of \( K_v \) that does not admit any polychromatic \( STS(v) \), when \( k = 2, 3 \), and \( v – 2 \). In this paper, we extend the results to all feasible values of \( k \), where \( 2 \leq k \leq v – 2 \).

A Costas Latin square of order \( n \) is a set of \( n \) disjoint Costas arrays of the same order. Costas Latin squares are studied here from both a construction and classification point of view. A complete classification is carried out up to order \( 27 \). In this range, we verify the conjecture that there is no Costas Latin square for any odd order \( n \geq 3 \). Various other related combinatorial structures are also considered, including near Costas Latin squares (which are certain packings of near Costas arrays) and Vatican Costas squares.

Let \(G = (V,E)\) be an undirected graph and let \(\pi = \{V_1, V_2, \ldots, V_k\}\) be a partition of the vertices \(V\) of \(G\) into \(k\) blocks \(V_i\). From this partition one can construct the following digraph \(D(\pi) = (\pi, E(\pi))\), the vertices of which correspond one-to-one with the \(k\) blocks \(V_i\) of \(\pi\), and there is an arc from \(V_i\) to \(V_j\) if every vertex in \(V_j\) is adjacent to at least one vertex in \(V_i\), that is, \(V_i\) dominates \(V_j\). We call the digraph \(D(\pi)\) the domination digraph of \(\pi\). A triad is one of the 16 digraphs on three vertices having no loops or multiple arcs. In this paper we study the algorithmic complexity of deciding if an arbitrary graph \(G\) has a given digraph as one of its domination digraphs, and in particular, deciding if a given triad is one of its domination digraphs. This generalizes results for the domatic number.

A Roman dominating function on a graph \( G \) is a function \( f: V(G) \to \{0,1,2\} \) such that every vertex \( u \) with \( f(u) = 0 \) is adjacent to a vertex \( v \) with \( f(v) = 2 \). The weight of a Roman dominating function \( f \) is the value \( f(V(G)) = \sum_{u \in V(G)} f(u) \). A Roman dominating function \( f \) is an independent Roman dominating function if the set of vertices for which \( f \) assigns positive values is independent. The independent Roman domination number \( i_R(G) \) of \( G \) is the minimum weight of an independent Roman dominating function of \( G \).

We show that if \( T \) is a tree of order \( n \), then \( i_R(T) \leq \frac{4n}{5} \), and characterize the class of trees for which equality holds. We present bounds for \( i_R(G) \) in terms of the order, maximum and minimum degree, diameter, and girth of \( G \). We also present Nordhaus-Gaddum inequalities for independent Roman domination numbers.

Let \( M(b, n) \) be the complete multipartite graph with \( b \) parts \( B_0, \ldots, B_{b-1} \) of size \( n \). A \( 4 \)-cycle system of \( M(b, n) \) is said to be a \({frame}\) if the \( 4 \)-cycles can be partitioned into sets \( S_1, \ldots, S_z \) such that for \( 1 \leq j \leq z \), \( S_j \) induces a \( 2 \)-factor of \( M(b, n) \setminus B_i \) for some \( i \in \mathbb{Z}_b \). The existence of a \( C_4 \)-frame of \( M(b, n) \) has been settled when \( n = 4 \) [6]. In this paper, we completely settle the existence question of a \( C_4 \)-frame of \( M(b, n) \) for all \( b \neq 2 \) and \( n \).

A subset \( A \) of vertices of a graph \( G \) is a \( k \)-dominating set if every vertex not in \( A \) has at least \( k \) neighbors in \( A \) and a \( k \)-star-forming set if every vertex not in \( A \) forms with \( k \) vertices of \( A \) a not necessarily induced star \( K_{1, k} \). The maximum cardinalities of a minimal \( k \)-dominating set and of a minimal \( k \)-star-forming set of \( G \) are respectively denoted by \( \Gamma_k(G) \) and \( \text{SF}_k(G) \). We determine upper bounds on \( \Gamma_k(G) \) and \( \text{SF}_k(G) \) and describe the structure of the extremal graphs attaining them.

Clatworthy described the eleven group divisible designs with three groups, block size four, and replication number at most 10. With these in mind one might ask: Can each of these designs be generalized in natural ways? In two previous papers the existence of natural generalizations of four of these designs were settled. Here we essentially settle the existence of natural generalizations of five of the remaining seven Clatworthy designs.

A complete solution is obtained for the possible number of common entries between two Latin squares of different given orders. This intersection problem assumes the entries of the smaller square are also entries of the larger, and that, for comparison, the smaller square is overlayed on the larger. However, these extra restrictions do not affect the solution, apart from one small example.

Let \( G = (V, E) \) be a graph. A subset \( S \) of \( V \) is called an \({equivalence\; set}\) if every component of the induced subgraph \( (S) \) is complete. In this paper, starting with the concept of equivalence set as a seed property, we form an inequality chain of six parameters, which we call the \({equivalence\; chain}\) of \( G \). We present several basic results on these parameters and problems for further investigation.