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.

It has been known for some time that the Higman-Sims graph can be decomposed into the disjoint union of two Hoffman-Singleton graphs. In this paper, we establish that the Higman-Sims graph can be edge decomposed into the disjoint union of 5 double-Petersen graphs, each on 20 vertices. It is shown that, in fact, this can be achieved in 36,960 distinct ways. It is also shown that these different ways fall into a single orbit under the automorphism group \(\text{HS}\) of the graph.

Recently, Graves, Pisanski, and Watkins have determined the growth rates of Bilinski diagrams of one-ended, 3-connected, edge-transitive planar maps. The computation depends solely on the edge-symbol \((p,q;k,l)\) that was introduced by B. Gr\”unbaum and G. C. Shephard in their classification of such planar tessellations. We present a census of such tessellations in which we describe some of their properties, such as whether the edge-transitive planar tessellation is vertex- or face-transitive, self-dual, bipartite, or Eulerian. In particular, we order such tessellations according to the growth rate and count the number of tessellations in each subclass.

We give general lower bounds and upper bounds on the maximum degree \(\Delta(G)\) of a \(3_t\)-critical graph \(G\) in terms of the order of \(G\). We also establish tighter sharp lower bounds on \(\Delta(G)\) in terms of the order of \(G\) for several families of \(3_t\)-critical graphs, such as crown-graphs, claw-free graphs, and graphs with independence number \(\alpha(G) = 2\).